- 底层的储存结构
- 数组：连续的内存空间
- 链表：通过「指针」将一组零散的内存块串联
[配图]
- 单链表
- 结点
- 头结点
- 尾结点
- 后继指针
next - 插入与删除操作，只需考虑相邻结点的指针改变，时间复杂度O(1)
- 随机访问性能没有数组好，时间复杂度O(n)
- 结点
[配图]
- 循环链表
- 尾结点指向链表的头结点
- 约瑟夫问题
[配图]
- 双向链表
- 实际开发中较为常用
- 支持两个方向
- 有一个后继指针 next 指向后面的结点
- 还有一个前驱指针 prev 指向前面的结点
- 删除、插入操作优势，时间复杂度O(1)
- 双向链表有什么优势？适合解决哪种问题？
- 有序链表按值查找效率更高
- 删除、查找操作
- 典型的以空间换时间的设计思想
[配图]
- 双向·循环列表
[配图]
- 数组
- 简单易用、连续内存空间可利用 CPU 缓存机制，访问效率更高
- 缺点是大小固定，一经声明就要占用整块连续空间
- 对内存使用非常苛刻，更适合用数组，避免额外消耗和内存碎片
- 链表
- 在内存中不连续，对 CPU 缓存机制不友好，无法有效预读
- 本身没有大小限制，天然支持动态扩容
- 每个结点需要额外的内存空间，频繁插入、删除易造成内存碎片
维护一个有序单链表，越靠近链表尾部的节点是越早之前访问的，当有一个新的数据被访问时，从链表头开始顺序遍历链表
-
如果此数据之前已经被缓存在链表中了，遍历得到这个数据对应的结点，并将其从原有位置删除，插入到链表的头部
-
如果此数据没有在缓存链表中，又分为两种情况：
-
若缓存未满，则将此结点直接插入链表头部
-
若缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部
-
Tips: 后续采用散列表 HashMap 优化
-
通过一些测试用例可以节省一些时间 使用链表时不易调试。因此，在编写代码之前，尝试几个不同的示例来验证是很有帮助的。
-
可以同时使用多个指针 有时，当一个链表问题不易解决时，可能需要同时使用多个结点指针。记住需要个跟踪的结点，并采用几个不同的结点指针。指针应当采用有意义的变量名。
-
很多时候，需要额外跟踪记录当前结点的前序结点 单链表无法追溯前一个结点，因此，�许多时候储存前一个结点时，也要同时储存前一个结点。这和双链表不同。