第三讲-链表

数组VS链表

1539653994749.png

​ 从图中我们看到，数组需要一块连续的内存空间来存储，对内存的要求比较高。如果我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，即便内存的剩余总可用空间大于 100MB，仍然会申请失败。而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用，所以如果我们申请的是 100MB 大小的链表，根本不会有问题。

1539654697427.png

​ 不过，数组和链表的对比，并不能局限于时间复杂度。而且，在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。

​ 数组简单易用，在实现上使用的是连续的内存空间，可以借助 CPU 的缓存机制，预读数组中的数据，所以访问效率更高。而链表在内存中并不是连续存储，所以对 CPU 缓存不友好，没办法有效预读。

​ 数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。

​ 你可能会说，我们 Java 中的 ArrayList 容器，也可以支持动态扩容啊？之前讲过，当我们往支持动态扩容的数组中插入一个数据时，如果数组中没有空闲空间了，就会申请一个更大的空间，将数据拷贝过去，而数据拷贝的操作是非常耗时的。

​ 我举一个稍微极端的例子。如果我们用 ArrayList 存储了了 1GB 大小的数据，这个时候已经没有空闲空间了，当我们再插入数据的时候，ArrayList 会申请一个 1.5GB 大小的存储空间，并且把原来那 1GB 的数据拷贝到新申请的空间上。听起来是不是就很耗时？

​ 除此之外，如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。

​ 所以，在我们实际的开发中，针对不同类型的项目，要根据具体情况，权衡究竟是选择数组还是链表。

链表基本知识

单链表

头结点：第一个结点，用来记录链表的基地址

尾结点：最后一个节点，不是指向下一个结点，而是指向一个空地址NULL。

循环链表

跟单链表唯一的区别就在尾结点，

单链表的尾结点指向空地址，而循环链表的尾结点指针指向链表的头结点。

和单链表相比，循环链表的优点是从链尾到链头比较方便，处理环形数据尤为适用。

双向链表

单向链表只有一个后继指针指向下一个结点，而双向链表除了有指向后继指针还有前驱指针指向前一个结点。

因此，双向链表需要额外的两个空间来存放后继结点和前驱结点的地址，这就导致如果存储同样多的数据，双向链表要比单向链表占用更多的内存空间。

使用空间换时间的思想，我们就会发现在以下几种情况中，双向链表比单向链表更适用：

• 删除结点中“值等于某个给定值”的结点；
• 删除给定指针指向的结点。
• 按值查询

正确编写链表代码小tips

1，理解指针或引用的含义

​ C语言中称为指针，java中称为引用。

​ 指针的定义：将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

如代码：

p->next=q   //p 结点中的 next 指针存储了 q 结点的内存地址

p->next=p->next->next  //p 结点中的 next 指针存储了 p 结点的下下一个节点的内存地址

2，警惕指针丢失和内存泄露

1539655252512.png

​ 如图所示，我们希望在结点 a 和相邻的结点 b 之间插入结点 x，假设当前指针 p 指向结点 a。如果我们将代码实现变成下面这个样子，就会发生指针丢失和内存泄露。

p->next = x;  // 将 p 的 next 指针指向 x 结点；
x->next = p->next;  // 将 x 的结点的 next 指针指向 b 结点；

初学者经常会在这儿犯错。p-next 指针在完成第一步操作之后，已经不再指向结点 b 了，而是指向结点 x。第 2 行代码相当于将 x 赋值给 x-next，自己指向自己。因此，整个链表也就断成了两半，从结点 b 往后的所有结点都无法访问到了。

​ 对于有些语言来说，比如 C 语言，内存管理是由程序员负责的，如果没有手动释放结点对应的内存空间，就会产生内存泄露。所以，我们插入结点时，一定要注意操作的顺序，要先将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。所以，对于刚刚的插入代码，我们只需要把第 1 行和第 2 行代码的顺序颠倒一下就可以了。

​ 同理，删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。当然，对于像 Java 这种虚拟机自动管理内存的编程语言来说，就不需要考虑这么多了。

3，利用哨兵简化实现难度

首先，我们先来回顾一下单链表的插入和删除操作。如果我们在结点 p 后面插入一个新的结点，只需要下面两行代码就可以搞定。

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

但是，当我们要向一个空链表中插入第一个结点，刚刚的逻辑就不能用了。我们需要进行下面这样的特殊处理，其中 head 表示链表的头结点。所以，从这段代码，我们可以发现，对于单链表的插入操作，第一个结点和其他结点的插入逻辑是不一样的。

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

我们再来看单链表结点删除操作。如果要删除结点 p 的后继结点，我们只需要一行代码就可以搞定。

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

但是，如果我们要删除链表中的最后一个结点，前面的删除代码就不 work 了。跟插入类似，我们也需要对于这种情况特殊处理。写成代码是这样子的：

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

由此，针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理，所以，我们进入哨兵结点。

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

1539655807084.png

4，重点留意便捷条件的处理

检查链表代码是否正确的边界条件有这样几个：

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

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

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

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

5，举例画图，辅助思考

如图：

1539656044442.png

6，多写多练，没有捷径

练习题目推荐：

• 单链表反转

• 链表中环的检测

• 两个有序的链表合并

• 删除链表倒数第n个结点

• 求链表的中间结点