链表经典应用场景：LRU缓存算法。
缓存淘汰策略常见的有三种：
- 先进先出策略（FIFO）
- 最少使用策略（LFU）
- 最近最少使用策略LRU
链表
链表与数据不同的之处在于，内存不是连续的，可以将分散的内存块串联起来使用。
链表结构大概有三种：单链表，双向链表，循环链表
单链表
单链表，摘自极客时间
链表需要有头节点与尾节点。单链表中头结点表示：链表的基地址；尾节点志向的地址是空地址NULL。
数组进行插入语删除操作的时候，为了保证内存的连续性，需要做数据的搬移操作，时间复杂度是O(N)；
链表中插入删除操作，不需要保证内存的连续性，插入与删除是十分快速的。
但是随机访问效率就特别低，需要从头结点开始查找。随机查找的时间复杂度就是O(N)。
循环链表
相对于单链表来说，尾节点指向头结点即可。
最著名的是 约瑟夫环问题.
双向链表
双向链表支持两个 方向，在一个实体中有指向上一个节点，也有指向下一个节点的指针。
双向链表，来自极客时间
缺点：
占用的空间多，浪费存储空间
优点：
操作上更加灵活，插入与删除操作更加简单与高效。
- 删除给定的某个值节点： 需要从头开始遍历，时间复杂度是O(1),主要耗时是查找时间是O(N).
- 对于删除给定的指针指向的节点： 找到要删除的节点，要删除前一个节点，或者向前面插入一个节点。都是十分方便的不需要再查询。
双向循环链表
把循环链表与双向链表组合在一起形成。
实现LRU缓存淘淘算法
思路：
- 单向链表存储数据，每次从头遍历数据，如果存在那么删除原先的位置，再把数据插入到头部即可。
- 如果此数据不存在缓存表中，缓存没有满，直接插入到链表的头部。满了，就删除尾节点，再插入到头部指针。
