C语言数据结构_链表

链表

一个假设

线性表是一种线性结构，它是具有相同类型的n(n≥0)个数据元素组成的有限序列。如果你之前没有学过链表肯定先想到的是数组这一线性结构，那我们是否可以用数组实现链表的插入 删除 等操作。 先画一个数组的内存图

访问线性结构数据:A[i] O(1) 插入:头部插入 如果需要在头部插入数据 需要把后面所有的数据后移一位 这里我们假设他们的长度允许他们往后移动 一位 这里我用红线表示,假如有n个数据那么我们就需要一定n次，耗用的时间周期为O(n) 尾部插入 这个没什么好说的,根据数组最后的索引的我们可以直接插入 但是最坏的情况是 数组的大小不足以我们在尾部 插入数据 这时候我们就需要重新创建一个更大的数组存放这些尾部增加的数据 很耗用系统内存 中间插入:假如我们要在索引3的位置插入5，后面的数据依次要后移，耗用的时间周期是O(n) 删除:删除一个数据我们需要获取这个数据的索引，然后把他后面n位的数据往前移 时间1周期是O(n) 这里我用绿线表示 附教程原图

链表

我们也看到用数组实现链表会造成很大的内存浪费和时间效率低，那我们应该如何实现链表这一功能 看图

我们申请的元素包含 1.一个数据元素 2.一个存放下一个节点的指针 C语言中可以用一个结构体来解释这两条

struct Node
{
int data;
Node*next;
}

结构体成员大小都是4字节 我们把这个结构体叫做节点 结构体第二个成员是指向节点的指针 也就是下一个节点的地址。 第一个节点我们也叫头节点 跟数组不一样的是，数组我们可以任意访问其中的元素，而链表只能通过头节点往下访问，直到找到我们需要的元素。 耗用的时间跨度:O(n) 如果要在中间插入一个元素，需要遍历到特定位置，然后将前一个节点的链接指向要插入的节点，插入节点的链接指向下一个节点

比数组插入一个元素要少移动很多位置,占用更少的内存，而且插入元素节点也不一定要在一块，可以按需创建需要的内存 删除节点亦是如此。

数组和链表的区别

要明确一个原则，每个数据结构都有自己适合的场景，而没有绝对的谁比谁好这种说法，这与数据结构的频繁操作和数据量的大小等有关。因此我将设置一些参数来比较二者的优缺点，尝试说明数组和链表各自适合的场景

• 访问元素的时间成本 数组---O(1) 链表---O(n)
• 访问元素的内存占用 比如我们现在要存放三个数 2 4 6 我们创建一个数组 int arry[5] 那么它占用的内存是5X4 = 20个字节 如果是链表话 数据部分和指针部分各占4个字节 我们需要三个节点 3X8 = 24 如果是少量数据的话数组显然内存占用比链表小。 但我们经常创建数组 其大小往往会大于其实际存储的内存，要防止溢出的危险。假如要存放的不再是一个简单四字节整型，而是一个复杂的数据结构，我们举例它占用16个字节，那么5x16 =80 而链表一个节点占用20X3 = 60 明显是链表对于存储复杂数据类型内存占用少于数组。 还有一点是，数组必须要有连续的内存，而链表则不需要，他把内存分成不连续的小块供我们使用，虽然可能会使内存碎片化(具体是什么我也不清楚，先埋个伏笔)。同时，数组创建的大小也是固定的，如果大于数组的大小，我们是没办法存放的，只能创建一个数组把元素拷贝进去，链表则不存在这种消耗内存的情况
• 列表中插入元素的成本 头部插入:如果在数组头部插入一个元素 就需要把所有元素往后移动一位 意味着他要花费的时间是O(n) 链表如果要在头部插入节点，可以直接创建一个节点然后指向指向的头节点 尾部插入:如果在数组尾部插入，假如数组空间是足够的，那么就可以直接在最后一个元素后面加入O(1) 如果空间是不够的，则需要把数组元素赋值到一个更大的内存中去，O(n) 链表在后面插入一个节点，需要遍历到最后一个 因此是O(n) 中间插入:数组--O(n) 链表--O(n)