链表经典应用场景：LRU缓存算法。
缓存淘汰策略常见的有三种：

• 先进先出策略（FIFO）
• 最少使用策略（LFU）
• 最近最少使用策略LRU

链表

链表与数据不同的之处在于，内存不是连续的，可以将分散的内存块串联起来使用。
链表结构大概有三种：单链表，双向链表，循环链表

单链表

单链表，摘自极客时间

链表需要有头节点与尾节点。单链表中头结点表示：链表的基地址；尾节点志向的地址是空地址NULL。

数组进行插入语删除操作的时候，为了保证内存的连续性，需要做数据的搬移操作，时间复杂度是O(N)；
链表中插入删除操作，不需要保证内存的连续性，插入与删除是十分快速的。
但是随机访问效率就特别低，需要从头结点开始查找。随机查找的时间复杂度就是O(N)。

循环链表

相对于单链表来说，尾节点指向头结点即可。
最著名的是 约瑟夫环问题.

双向链表

双向链表支持两个 方向，在一个实体中有指向上一个节点，也有指向下一个节点的指针。

双向链表，来自极客时间

缺点：
占用的空间多，浪费存储空间

优点：
操作上更加灵活，插入与删除操作更加简单与高效。

• 删除给定的某个值节点： 需要从头开始遍历，时间复杂度是O(1),主要耗时是查找时间是O(N).
• 对于删除给定的指针指向的节点： 找到要删除的节点，要删除前一个节点，或者向前面插入一个节点。都是十分方便的不需要再查询。

双向循环链表

把循环链表与双向链表组合在一起形成。

实现LRU缓存淘淘算法

思路：

1. 单向链表存储数据，每次从头遍历数据，如果存在那么删除原先的位置，再把数据插入到头部即可。
2. 如果此数据不存在缓存表中，缓存没有满，直接插入到链表的头部。满了，就删除尾节点，再插入到头部指针。