2.2. 链表：LRU缓存淘汰算法
缓存淘汰策略：
- 最优替换算法 OPT（Optimal）：淘汰未来不常用的，不可能实现
- 先进先出策略 FIFO（First In，First Out）：淘汰旧的
- 最少使用策略 LFU（Least Frequently Used）：淘汰一直不常用的
- 最近最少使用策略 LRU（Least Recently Used） ：淘汰最近不常用的
链表（Linked list）：
- 线性表数据结构
- 零散的内存块以指针串联
- 相同的数据类型
链表结构类型：
- 单链表
- 双向链表
- 循环链表
-
单链表
- 头结点存放链表的基地址，后继指针 next → 下一个结点的地址
- 尾结点的后继指针 next → 空地址 NULL
单链表
总结 - 数组和链表：
- 内存分布
数组与链表的内存分布
- 时间复杂度
| 时间复杂度 | 数组 | 单链表/循环链表 | 双向链表 |
|---|---|---|---|
| 随机访问 | O(1) | O(n) | O(n) |
| 插入删除 | O(n) | O(1) | O(1) |
