链表

链表也是一种很常用的数据结构，可分为单向链表、循环链表、双向链表。

单向链表

链表节点中只有一个后继指针next，指向下一个节点。
只能从链表头部向链表尾部遍历。

循环链表

在单向链表的基础上增加了一个前驱指针prev，可以指向上一个节点。
链表的遍历方向可以从头部到尾部，也可以从尾部到头部。

双向链表

在循环链表的基础上，头节点的前驱指针prev指向尾节点，尾节点的后继指针next指向头节点。
链表的遍历方向可从头到尾的方向，也可从尾到头的方向，一直循环下去。

缓存的淘汰策略

缓存有三种淘汰策略：先进先出（FIFO）策略、最少使用（LFU）策略、最近最少（LRU）使用策略。

1. 先进先出（FIFO）策略
   先存入缓存的数据先被淘汰。

2. 最少使用（LFU）策略
   访问次数最少的数据先被淘汰。

3. 最近最少（LRU）使用策略
   最近最少被访问的数据先被淘汰，可使用双向链表结构来实现。

我们来研究下LRU策略的简单实现： 维护一个有序的双向链表，越靠近链表尾部的节点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1. 如果此数据之前已经存在链表中，把这个数据所在节点移动到链表头部。
2. 如果此数据不在链表中，分为如下两种情况：
   • 如果此时缓存还有空间，把此节点插入到链表头部。
   • 如果此时缓存已经满了，则删除链表尾部节点，把新数据插入到链表头部。

链表 VS 数组性能

时间复杂度	数组	链表
插入和删除	O(n)	O(1)
随机访问	O(1)	O(n)

扩展

Redis中提供了多种缓存的淘汰策略，其中就包括：先进先出（FIFO）策略、最近最少（LRU）使用策略，感兴趣的同学可以去了解下：Using Redis as an LRU cache