数据结构——链表

链表也是一种数据结构，相比较于数组，略显复杂。链表和数组都是非常基础、非常常用的数据结构。

成都创新互联公司专注于企业营销型网站、网站重做改版、鄠邑网站定制设计、自适应品牌网站建设、H5网站设计、商城系统网站开发、集团公司官网建设、外贸网站制作、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为鄠邑等各大城市提供网站开发制作服务。

1. 数组与链表的区别
   从底层的存储结构上看，二者申请的内存空间不一样：

数组需要一块连续的内存空间来存储，对内存要求较高。

链表不需要一块连续的内存空间，它通过"指针"将一组零散的内存块串联起来。

例如，当我们申请一个100MB大小的数组，当内存空间中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于100MB，仍然会申请失败。但如果我们申请的是100MB大小的链表时，就可以申请成功。

2. 三种常见的链表结构
   链表结构有很多种，但最常见的主要有如下三种：

单链表

双向链表

循环链表

2.1 单链表
链表通过指针将一组零散的内存块串联在一起，我们将内存块称为链表的“结点”。为了将所有的结点串联在一起，每个链表的结点除了要存储数据之外，还需要记录链上的下一个结点的地址，这个结点地址的指针叫作“后继指针next”。

单链表中有两个结点比较特殊，分别是第一个结点和最后一个结点。我们习惯性的把第一个结点叫作头结点，最后一个结点叫作尾结点。

头结点用来记录链表中的基地址，可以根据头结点遍历得到整个链表。

尾结点的指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。

在链表中进行数据的插入和删除操作要比数组中高效。因为在数组中进行插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据移动，时间复杂度是O(n)。而在链表中存储空间本身就不是连续的，不需要为了保持内存的连续性而移动大量的数据。

在链表的插入和删除操作中，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是O(1)。

链表中数据的插入和删除比数组高效，但当需要随机访问第k个数据时，就没有数组高效。因为链表中的数据不是连续存储的，无法像数组那样，根据首地址和下标，通过寻址公式直接计算出对应的内存地址，而是需要根据指针一个结点一个结点依次遍历，直到找到对应的结点。

2.2 循环链表
循环链表的本质是一种特殊的单链表，与单链表的区别就是在尾结点。单链表中的尾结点指针指向空地址，表示这就是最后的结点。而循环链表的尾结点指针指向链表的头结点。
与单链表相比，循环链表的优点是从链尾到链头比较方便。当需要处理的数据具有环形结构特点时，就适合用循环链表处理。比如著名的“约瑟夫问题”。

2.3 双向链表
单链表中只有一个方向，结点只有一个后继指针next指向后面的结点。而双向链表中，有两个方向，每个结点不仅有一个后继指针指向后面的结点，还有一个前驱指针prev指向前面的结点。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以当存储同样多的数据时，双向链表要比单链表占用更多的内存空间。

虽然双向链表中有两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。

从双向链表从结构上看，可以支持O(1)时间复杂度的情况下找到前驱结点，因此在某些情况下，双向链表的插入、删除操作比单链表更简单、高效。其实，前面说的单链表的插入、删除操作的时间复杂度是O(1)是有先决条件的。

2.4 单链表与双向链表删除、插入操作比较
删除操作

从链表中删除一个数据，一般都是如下两个情况：

删除结点中“值等于某个给定值”的结点

删除给定指针指向的结点

第一种情况中：

我们需要先找到值等于给定值的结点，找到结点后，再做删除操作。

这种情况下，单链表或双向链表都需要从头结点开始一个一个依次的遍历对比，直到找到值等于给定值的结点。此时单链表和双向链表查找的时间复杂度均是O(n)，删除的时间复杂度是均O(1)，根据时间复杂度分析中的加法法则，删除值等于给定值的结点的对应的链表操作总的时间复杂度是O(n)。且这种情况下单链表与双向链表是同等高效。

第二种情况中：

虽然我们可以根据指针直接找到要删除的结点，但删除某个结点q需要知道它的前驱结点，而单链表中并不支持直接获取前驱结点，此时为了找到前驱结点，我们还需要从头结点开始遍历单链表，直到p–>next=q，才说明p是q的前驱结点。

但在这种情况下，双向链表就有优势了，因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样再从头遍历一遍。所以这种情况下，单链表删除操作的时间复杂度是O(n)，而双向链表的时间复杂度是O(1)。

插入操作

同理，在插入操作中，按照删除操作的分析思路，可以知道双向链表的时间复杂度是O(1)；单向链表的时间复杂度是O(n)。

双向链表除了删除、插入操作上有优势上外，还有对于一个有序链表。双向链表的按值查询效率也比单链表高一些。

因为在双向链表中，可以记录上次查找的位置p，后面每次查找时，可以根据要查找的值与p位置对应值的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

java中LinkedHashMap底层用到的就是双向链表这种数据结构。

在我们平时开发的过程中有“用空间换时间”和“用时间换空间”的设计思想：

当内存空间充足时，如果追求代码的执行速度，就会选择空间复杂度相对较高，时间复杂度相对较低的算法或数据结构。

如果内存紧缺，就会选择空间复杂度相对较低，时间复杂度相对较高的算法或数据结构。

如果整合循环链表和双向链表，那就组合成了“双向循环链表”。

3. 数组与链表性能比较
   通过前面的学习知道，数组与链表的内存存储有区别，因此二者的插入、删除、随机访问操作的时间复杂度正好相反。

当然，不能仅用时间复杂度的高低去决定使用数组还是链表，还要看情况而定。

数组简单易用，申请的是连续内存空间，可以借助CPU的缓存机制，预读数组中的数据，这样随机访问的效率会更高。而链表中的内存空间不是连续的，因此不能使用CPU缓存机制，没办法有效预读。

数组最大的缺点就是大小固定，一经声明就要占用整块连续内存空间，如果申请的内存空间过大，当系统没有足够大的连续内存空间时，就会导致内存不足(out of memory)。如果声明的数组过小，则可能出现不够用的情况。这时则需要去申请一个更大的内存空间，将原数组中的数据拷贝过去，非常耗时。链表本身没有大小的限制，支持动态扩容。这也是数组与链表之间最大的区别。

如果代码对内存的使用要求非常高，那建议用数组。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，会导致频繁的内存申请和释放，容易造成内存碎片。如果是在java中，就有可能回导致频繁的GC。

所以在实际开发过程中，针对不同类型的项目，要根据具体情况，权衡是用数组还是链表。

4. 写链表代码的技巧
   前面讲了链表的基本知识，但要写好链表代码并不是那么简单的事，下面讲几点写链表代码的技巧。如果能熟练掌握这几个技巧，然后多练习，相信以后也能很轻松的写出链表代码。

4.1 理解指针或引用的意义
有些语言中有“指针”的概念，比如C语言、C++；有些语言中没有指针，取而代之的是“引用”，比如java、Python。其实，不管是“指针”还是“引用”它们的意思都是一样的，都是存储所指对象的内存地址。

对于指针或引用可以理解为：将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针。或者说：指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

例如链表代码一：

p->next = q

这行代码的意思是：p结点中的next指针存储了q结点的内存地址。

链表代码二：

p->next=p->next->next

表示：p结点的next指针存储了p结点的下下一个结点的内存地址。

掌握指针或引用的概念是看懂链表代码的前提。

4.2 利用哨兵简化实现难度
在上面单链表的结点p后面插入一个新的结点，只需要下面两行代码就行了：

new_node->next = p->next
p->next = new_node

但当我们向一个空链表中插入一个结点时，光上面的两行代码就不行了，需要先进行特殊处理下：

if (head == null) {
head = new_node;
}

其中，head表示链表的头结点。因此可以发现对于单链表的插入操作，第一个结点和其他结点的插入逻辑是不一样的。

再看下单链表结点的删除操作。如果要删除结点p的后继结点，那么一行代码就行了：

p->next = p->next->next;

但如果要删除的是链表中的最后一个结点，前面的删除代码就不行了，同样需要先进行特殊处理：

if (head->next == null) {
head = null;
}

从上面的分析可知，针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特别处理。这样在代码实现的时候不仅会显得繁琐，还容易出错。此时如果我们引入哨兵结点，那么在任何时候，不管链表是不是空，head指针都会一直指向这个哨兵结点。我们将有哨兵结点的链表叫作“带头链表”，没有哨兵结点的链表叫作“不带头链表”。

哨兵结点是不存储数据的。因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以用相同的代码实现逻辑。

使用这种哨兵简化了编程难度。在插入排序、归并排序和动态规划中都有运用。

为了加深理解，举一个C语言代码的例子：

代码一：

// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
int find(char* a, int n, char key) {
// 边界条件处理，如果 a 为空，或者 n<=0，说明数组中没有数据，就不用 while 循环比较了
if(a == null || n <= 0) {
return -1;
}

int i = 0;
// 这里有两个比较操作：iwhile (i < n) {
if (a[i] == key) {
return i;
}
++i;
}

return -1;
}

代码二：

// 在数组 a 中，查找 key，返回 key 所在的位置
// 其中，n 表示数组 a 的长度
// 我举 2 个例子，你可以拿例子走一下代码
// a = {4, 2, 3, 5, 9, 6} n=6 key = 7
// a = {4, 2, 3, 5, 9, 6} n=6 key = 6
int find(char* a, int n, char key) {
if(a == null || n <= 0) {
return -1;
}

// 这里因为要将 a[n-1] 的值替换成 key，所以要特殊处理这个值
if (a[n-1] == key) {
return n-1;
}

// 把 a[n-1] 的值临时保存在变量 tmp 中，以便之后恢复。tmp=6。
// 之所以这样做的目的是：希望 find() 代码不要改变 a 数组中的内容
char tmp = a[n-1];
// 把 key 的值放到 a[n-1] 中，此时 a = {4, 2, 3, 5, 9, 7}
a[n-1] = key;

int i = 0;
// while 循环比起代码一，少了 iwhile (a[i] != key) {
++i;
}

// 恢复 a[n-1] 原来的值, 此时 a= {4, 2, 3, 5, 9, 6}
a[n-1] = tmp;

if (i == n-1) {
// 如果 i == n-1 说明，在 0...n-2 之间都没有 key，所以返回 -1
return -1;
} else {
// 否则，返回 i，就是等于 key 值的元素的下标
return i;
}
}

对比上面的两段代码，在字符串a很长的时候，代码二运行会更快一点，因为在两段代码中执行次数最多的就是while循环部分。而在第二段代码中，我们通过一个哨兵a[n-1]=key，成功的省掉了一个比较语句i

4.3 重点留意边界条件处理
在写链表代码中，在边界条件下也很容易出现bug，平时我们可以从如下几个方面去检查链表代码边界条件是否正确：

如果链表为空时，代码是否还能正常工作？

如果链表只包含了一个结点，代码是否还能正常工作？

如果链表中只包含两个结点，代码是否能正常工作？

代码逻辑在处理头结点和尾结点时，是否还能正常工作？

在写完链表代码后，可以从如上几点去考虑下那些边界条件。这样才能更好的保证代码的健壮性。