数据结构：链表(1)
王争数据结构笔记（06）
1、三种常见的缓存淘汰策略:先进先出策略FIFO,最少使用策略(Least Frequently Used,LFU),最近最少使用策略(Least Recently Used,LRU).
2、数组利用连续的内存空间进行存储，对内存的要求较高。链表则是通过指针零散的内存块串接起来。如图1所示。
图片来源：王争数据结构第六课
3、三种常见的链表：单链表，双向链表和循环链表。
4、单链表的第一个节点叫做头结点，记录链表的基地址。尾结点的指针不会记录下一个结点的地址，而是空地址NULL。
由于链表的存储并不连续，所以插入和删除对于链表来说非常容易，操作对应的时间复杂度为O(1)。相反，链表随机访问需要O(n)的时间复杂度。
5、循环链表是特殊的单链表，将单链表置空的尾结点指向链表的头结点，形成首尾相连的结构。这种结构对于处理环形结构特点的数据具有优势。
6、双向链表同时具有后继指针和前驱指针，构成两个方向。虽然占据了更多的存储空间，但是支持了双向遍历。
7、单链表和双链表比较
| 目的 | 单链表 | 双向链表 |
| 删除结点中值等于某个给定值 | 删除O(1)+遍历查询O(n)=O(n) | 删除O(1)+遍历查询O(n)=O(n) |
| 删除给定指针指向的结点 | O(n) | O(1) |
8、数组，链表比较（1）
| 时间复杂度 | 数组 | 链表 |
| 插入，删除 | O(n) | O(1) |
| 随机访问 | O(1) | O(n) |
9、数组：1）借助CPU缓存机制，访问效率更高。
2）如果数组过大，可能连续的内存空间不足。
链表：1）在内存区间不是连续存储，对缓存不友好，无法预读。
2）支持动态扩容，没有大小限制。