数据结构与算法第三讲 - 链表
本讲内容
链表定义和分类
链表和数组比较
链表操作
写链表代码的技巧
简单算法题
链表定义和分类
定义：通过指针把零散的内存空间串联起来存储数据
思想：空间换时间
对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。
分类：单链表，循环链表，双向链表，双向循环链表
单链表
循环链表是一种特殊的单链表，单链表尾指针指向null，循环链表尾指针指向头节点
循环链表
双向链表
单链表是单向的，每个节点只有一个指针，而双向链表每个节点有两个指针，所以占用的空间更大，但是它的操作相比于单链表更灵活高效。
接下来我们看下主要高效在什么地方？
删除操作：
- 删除结点中“值等于某个给定值”的结点；
- 删除给定指针指向的结点。
第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过我前面讲的指针操作将其删除。尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。根据时间复杂度分析中的加法法则，删除值等于给定值的结点对应的链表操作的总时间复杂度为 O(n)。
第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。
对于单链表，需要从头遍历找到该节点的前向节点指针，然后指向删除操作，删除操作时间复杂度O(1)，但是遍历节点的时间复杂度为 O(n)，所以根据复杂度计算的加法原则，总时间复杂度为 O(n)
对于双向链表，找到的节点包含前向节点的指针，因此不需要再进行遍历，找到前向节点O(1)，删除节点O(1)，所以总时间复杂度为 O(1)
双向循环链表
链表和数组比较
| 分类 | 内存 | 优点 | 缺点 |
|---|---|---|---|
| 数组 | 连续内存，可以随机读取 | 结构简单，使用容易，可以利用CPU的缓存 | 1. 大小固定，为避免越界一般会超额申请，即使有容器类的数组，但是在扩容时，会先拷贝现有的数据，性能比较差 |
| 链表 | 零散内存，需要通过指针进行连接和取值 | 插入删除操作时间复杂度O(1)，频繁的插入删除会导致内存碎片多，需要进行垃圾回收 | 占用空间多 |
image.png
链表操作
-
插入和删除
单链表的插入和删除
-
查找
写链表代码技巧
技巧一：理解指针或引用的含义
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。
示例：
p->next=q。这行代码是说，p 结点中的 next 指针存储了 q 结点的内存地址。
p->next=p->next->next。这行代码表示，p 结点的 next 指针存储了 p 结点的下下一个结点的内存地址。
技巧二：警惕指针丢失和内存泄漏
示例：
单链表的插入
单链表的插入
p->next = x; // 将p的next指针指向x结点；
x->next = p->next; // 将x的结点的next指针指向b结点；
以上代码会导致指针丢失，b节点后的节点无法访问
插入结点时，一定要注意操作的顺序
正确写法：
x->next = p->next; // 将x的结点的next指针指向b结点；
p->next = x; // 将p的next指针指向x结点；
删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。当然，对于像 Java 这种虚拟机自动管理内存的编程语言来说，就不需要考虑这么多了。
注：什么是内存泄漏？
内存泄露 memory leak，是指程序在申请内存后，无法释放已申请的内存空间，一次内存泄露危害可以忽略，但内存泄露堆积后果很严重，无论多少内存，迟早会被占光。
memory leak会最终会导致out of memory(内存溢出)！
技巧三：利用哨兵简化实现难度
- 为什么要引入哨兵？
针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。
单链表插入
其他节点插入
x->next = p->next; // 将x的结点的next指针指向b结点；
p->next = x; // 将p的next指针指向x结点；
第一个节点的插入
if (head == null) { head = new_node;}
单链表删除
其他节点删除
p->next = p->next->next;
最后一个节点删除
if (head->next == null) { head = null;}
如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表。
带头链表
哨兵结点是不存储数据的。因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑了。
技巧四：重点留意边界条件处理
要实现没有 Bug 的链表代码，一定要在编写的过程中以及编写完成之后，检查边界条件是否考虑全面，以及代码在边界条件下是否能正确运行。
常需检查的边界情况：
- 如果链表为空时，代码是否能正常工作？
- 如果链表只包含一个结点时，代码是否能正常工作？
- 如果链表只包含两个结点时，代码是否能正常工作？
- 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
技巧五：举例画图，辅助思考
技巧六：多写多练，没有捷径
- 单链表反转
- 链表中环的检测
- 两个有序的链表合并
- 删除链表倒数第 n 个结点
- 求链表的中间结点
简单算法题
如何实现LRU缓存淘汰算法？
