链表的内存结构是不连续的内存空间，将一组零散的内存块串联起来进行数据存储的数据结构。
引子：缓存淘汰策略
- 先进先出FITO(First In,First Out)
- 最少使用LFU(Least Frequently Used)
- 最近最少使用LRU(Least Recently Used)
常见链表结构
- 单链表
->(数据+后继指针next)->
首结点地址表示整条链表，尾结点的后继指针指向空地址null - 双向链表
->(前驱指针prev+数据+后继指针next)->
首结点的前驱指针prev和尾结点的后继指针均指向空地址null- 给定数据值删除对应结点,需要从头到尾遍历时间复杂度O(n);
- 给定结点地址删除结点,单链表需要从头到尾遍历前驱结点时间复杂度O(n),双向链表可以直接找到前驱结点时间复杂度O(1)。
- 循环链表
尾结点的后继指针指向链表的首结点的地址
- 双向循环链表
实现链表
- 理解指针或引用的含义(所指或引用对象的内存地址)
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针；指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。 - 警惕指针丢失和内存泄漏
插入结点时，一定要注意操作的顺序；删除结点时，一定要记得手动释放内存空间。 - 利用哨兵简化实现难度
针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。利用哨兵解决边界问题，不直接参与业务逻辑。
引入哨兵结点，在任何时候，不管链表是不是空，head指针都会一直指向这个哨兵结点，哨兵结点不存储数据。 - 重点留意边界条件处理
链表为空、链表只包含一个结点、链表只包含两个结点、代码逻辑在处理头结点和尾结点等情况时，是否能正常工作。 - 举例画图，辅助思考
- 多写多练，没有捷径
单链表反转、链表中环的检测、两个有序的链表合并、删除链表倒数第n个结点、求链表的中间结点
链表or数组
| 时间复杂度 | 数组 | 链表 |
|---|---|---|
| 插入操作 | O(n) | O(1) |
| 随机访问 | O(1) | O(n) |
与数组相比，链表除了存储数据，需要消耗更多的内存空间，存储后继指针。
对链表进行频繁的插入和删除操作，会导致频繁的内存申请和释放，容易造成内存碎片。
数组需要连续的内存空间。有利有弊，便于借助CPU缓冲机制于都数组中的数据；不能充分利用不连续的内存空间。
数组大小固定，若存储空间不足需要进行扩容，一旦扩容需要进行数据复制，非常耗时。
链表实现LRU算法
维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有有一个新的数据被访问时，从链表头开始顺序遍历链表。
- 数据之前已经被缓存在链表中了，将遍历得到的对应结点从原来的位置删除，然后再插入到链表的头部。
- 数据没有在缓存链表中，若缓存未满，将结点直接插入到链表的头部；若缓存已满，将链表尾结点删除，将新数据结点插入链表的头部。
数组实现LRU算法
维护一个有序数组，越靠近数组尾部的元素是越早访问的，当有一个新的数据被访问时，从数组第一个元素开始遍历数组
- 数据在数组中，将当前数据对应元素前的元素后移一位，并将当前数据放入头部。
- 数据不在数组中，若缓存未满，将当前数组所有元素后移一位，将数据放入头部；若缓存已满，先删除数组最后一个元素，将数组所有元素后移一位，将数据放入头部。
扩展
单链表判断回文字符串
快慢指针，链表反转