数据结构与算法之美-链表

前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。

1. 链表

链表和数组都是非常基础的数据结构，通常也会放到一块来比较，通过和数组对比，我们来了解一下链表的概念。

链表和数组最根本的区别是底层的存储结构不同。

数组是需要一块连续的内存空间来存储的，对内存的要求比较高。比如我们申请一个 100MB 大小的数组，当内存中没有连续的、足够大的存储空间时，及时内存剩余空间 > 100MB，仍然会申请失败。

链表则相反，它并不是连续的，而是通过指针将一组零散的内存块串了起来，所以在和上面相同的场景下，如果申请的是 100MB 大小的链表，则不会有任何问题。

两者的区别如下图所示：

image.png

2. 链表的分类

最常见的有三种：单链表、双向链表、循环链表。

2.1 单链表

上面👆有提到，链表通过指针将一组零散的内存块串联在一起。这些个零散的内存块，我们称为链表的结点，那为了将这些结点串联起来，每个链表的结点除了存储数据之外，还需要记录下一个结点的地址，我们把这个记录下个结点地址的指针叫做后继指针 next，如下图所示：

image.png

在链表中，第一个结点称为头结点，最后一个结点称为尾节点。头结点用来记录链表的基地址，有了头结点，就可以遍历整条链表。尾结点的 next 指针指向一个空地址 NULL，标明这是链表的最后一个结点。

2.1.1 链表的插入和删除

链表也支持数据的查找、插入和删除操作，和数组不同，在链表中插入或者删除一个数据，我们并不需要考虑内存的连续性，因为链表的存储空间本身就不是连续的，所以链表中的插入和删除都是比较快速的，如下图：

image.png

我们只需要考虑相邻结点的指针改变就行，时间复杂度为 O(1)。

2.1.2 链表的随机访问

相对于数组的插入和删除，链表的表现是比较高效的，但是对于随机访问第 k 个元素，就没有数组那么高效了。链表需要一个结点一个结点的区遍历，直到找到相应的节点。

链表就相当于是一个队伍，队伍的每个人只需要直到后面的人是谁就行了，所以我们想知道第 k 位的人时，就需要从第一个人开始，一个一个的往下数，所以时间复杂度为 O(n) 。

2.2 循环链表

顾名思义，循环链表就是一个循环的单链表，和单链表唯一的区别就是循环链表的尾结点的 next 指针指向了头结点，首尾相连了，如下图所示：

image.png

和单链表相比，循环链表的优点是从链表尾到链表头很方便，当要处理的数据具有环形结构时，适合使用循环链表。

2.3 双向链表

单链表只有一个方向，只有一个后继指针 next 指向后面的节点。但是双向链表支持两个方向，除了这个后继指针之外，还有一个前继指针 prev 指向前面的结点，如下图所示：

image.png

从上图中可以看出，双向链表占用的空间比单链表更多，虽然两个指针比较浪费空间，但是可以支持双向遍历。

从结构上来看，双向链表相比于单链表可以支持 O(1) 时间复杂度的情况下找到前驱节点，因此在某种情况下，双向链表的插入和删除等操作比单链表更简单，高效。

比如，删除操作。从链表中删除一个数据无外乎两种情况：

• 删除结点中“值等于某个给定值”的结点
• 删除给定指针指向的结点

对于第一种情况，不管是单链表还是双向链表，为了查找值等于给定值的结点，都需要从头结点开始依次遍历对比，直到找到值等于给定值的结点，然后再通过指针操作将其删除。

删除操作的时间复杂度是 O(1)，但是遍历查找的时间则是主要的耗时点，对应的时间复杂度为 O(n)，根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。

对于第二种情况，我们已经找到了要删除的结点，但是删除某个节点 q 需要知道其前驱结点，但是单链表查找前驱结点，又得从头开始遍历。对于双向链表来说，这种情况就很 easy 了，因为双向链表中的结点已经保存了前驱结点的指针。这种情况下，单链表删除需要 O(n) 的时间复杂度，双向链表只需要在 O(1)的时间复杂度内就搞定了。

双向链表其实涉及到了一个空间换时间的设计思想，当内存空间充足的时候，我们可以选择空间复杂度相对较高、时间复杂度相对很低的算法或数据结构。缓存的设计就是利用了这种思想，我们把数据提前加载在内存中，虽然比较会耗费内存空间，但是每次数据查询的速度就会提高了。

总结：对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。

2.5 双向循环链表

这玩意就是双向链表和循环链表的结合体，如下图所示：

image.png

3. 链表和数组性能PK

链表和数组的内存存储结构不同，它们的插入、删除、随机访问操作的时间复杂度相反，如下图所示：

image.png

数组：

• 简单易用，内存连续
• 大小固定，需要占用整块连续内存空间

链表：

• 对 CPU 缓存不友好，无法有效预读
• 大小没有限制，支持动态扩容

4. 用链表实现 LRU 缓存淘汰算法

大概思路：
当有一个新的数据被访问时，从链表头部开始顺序遍历链表
1.如果这个数据之前已经被缓存在链表中了，就将这个数据对应的结点从原来位置删除，然后插入到链表的头部
2.如果数据没有在缓存链表中：
2.1 如果此时缓存未满，将此结点直接插入到链表的头部
2.2 如果此时缓存满了，将链表尾结点删除，将新的数据插入链表的头部

这种缓存访问的时间复杂度为 O(n)。

5. 写链表相关代码的技巧

5.1 理解指针或者引用的含义

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

比如 p->next = q，p 节点中的 next 指针存储了 q 结点的内存地址。

5.2 警惕指针丢失和内存泄漏

插入或者删除节点时要注意操作的顺序和手动释放内存空间。

5.3 利用哨兵简化实现难度

针对于链表的插入、删除操作，需要对插入的第一个结点和删除最后一个结点的情况进行特殊处理。

这种情况可以引入哨兵结点，不管链表是否为空，head 指针都会一直指向这个哨兵结点。有哨兵结点的链表叫做带头链表。

image.png

从上图中可以发现，哨兵结点是不存储数据的，所以插入第一个节点和插入其他节点，都可以统一为相同的代码实现逻辑了。

5.4 重点留意边界条件处理

• 链表为空时
• 只包含一个结点时
• 只包含两个结点时
• 代码逻辑在处理头结点和为结点时
  等等

5.5 举例画图，辅助思考

可以举例画图

6. 练习操作

• 单链表的基础操作：
  链表构建、指定位置添加结点、指定位置删除节点、打印链表、头插法、尾插法

• 单链表反转：
  迭代方法&递归方法实现

• 环的检测
  快慢指针

• 两个有序链表合并
  递归&迭代（增加虚拟头结点）

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

• 求链表的中间结点
  快慢指针

• 判断链表是否为回文链表