• 底层的储存结构
  • 数组：连续的内存空间
  • 链表：通过「指针」将一组零散的内存块串联

[配图]

• 单链表
  • 结点
    • 头结点
    • 尾结点
  • 后继指针next
  • 插入与删除操作，只需考虑相邻结点的指针改变，时间复杂度O(1)
  • 随机访问性能没有数组好，时间复杂度O(n)

[配图]

• 循环链表
  • 尾结点指向链表的头结点
  • 约瑟夫问题

[配图]

• 双向链表
  • 实际开发中较为常用
  • 支持两个方向
    • 有一个后继指针 next 指向后面的结点
    • 还有一个前驱指针 prev 指向前面的结点
  • 删除、插入操作优势，时间复杂度O(1)
  • 双向链表有什么优势？适合解决哪种问题？
    • 有序链表按值查找效率更高
    • 删除、查找操作
    • 典型的以空间换时间的设计思想

[配图]

• 双向·循环列表

[配图]

• 数组
  • 简单易用、连续内存空间可利用 CPU 缓存机制，访问效率更高
  • 缺点是大小固定，一经声明就要占用整块连续空间
  • 对内存使用非常苛刻，更适合用数组，避免额外消耗和内存碎片
• 链表
  • 在内存中不连续，对 CPU 缓存机制不友好，无法有效预读
  • 本身没有大小限制，天然支持动态扩容
  • 每个结点需要额外的内存空间，频繁插入、删除易造成内存碎片

维护一个有序单链表，越靠近链表尾部的节点是越早之前访问的，当有一个新的数据被访问时，从链表头开始顺序遍历链表

1. 如果此数据之前已经被缓存在链表中了，遍历得到这个数据对应的结点，并将其从原有位置删除，插入到链表的头部

2. 如果此数据没有在缓存链表中，又分为两种情况：

   1. 若缓存未满，则将此结点直接插入链表头部

   2. 若缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部

Tips: 后续采用散列表 HashMap 优化

1. 通过一些测试用例可以节省一些时间 使用链表时不易调试。因此，在编写代码之前，尝试几个不同的示例来验证是很有帮助的。

2. 可以同时使用多个指针 有时，当一个链表问题不易解决时，可能需要同时使用多个结点指针。记住需要个跟踪的结点，并采用几个不同的结点指针。指针应当采用有意义的变量名。

3. 很多时候，需要额外跟踪记录当前结点的前序结点 单链表无法追溯前一个结点，因此，�许多时候储存前一个结点时，也要同时储存前一个结点。这和双链表不同。