数据结构与算法：链表（如何利用链表实现LRU缓存淘汰算法）

一、数组和链表区别

数组需要一块连续的内存空间，对内存要求比较高。
链表通过指针将一组零散的内存块串联起来
数组随机访问效率高，插入删除操作为了保持内存数据的连续性，需要做大量搬移操作
链表插入和删除效率高，查找需要遍历链表
数组因为使用连续内存空间，可以借助cpu缓存机制，预读数组中数据
链表不是连续存储，所以cpu缓存不友好，没有办法预读

二、单链表

链表是通过指针将零散的内存块串联起来，我们把内存块称为链表的节点。为了将所有节点串联起来，每个链表的节点除存储数据外，还需要记录链上的下一个节点的地址（后继指针next）

单链表中有两个节点比较特殊（头节点和尾节点）
**头节点：**记录链表的基地址，有了它，我们可以遍历得到整条链表
**尾节点：**指针不是指向下一个地址，而是只想空地址null，表示是这个链表上最后一个节点
单链表的插入和删除：

三、循环链表

和单链表唯一的区别就是，单链表尾节点指向空地址null，循环链表尾节点指针指向头节点，当要处理数据具有环形特点时，采用循环链表

四、双向链表

单链表只有一个方向，后继指针指向后面的节点。而双链表有两个方向，不知后继指针next指向后面的节点，还有前驱节点prev指向前面的节点

五、双向循环链表

六、如何利用链表实现LRU缓存淘汰算法

缓存：一种提高数据读取性能的技术。
缓存大小有限，所以当缓存被用满时需要及时根据缓存淘汰策略进行清理
常见策略有三种：先进先出（FIFO）、最少使用策略（LFU）、最近最少使用策略（LRU）
基本思路：采用有序单链表，越靠近链表尾部的节点是越以前访问的。当有一个新的数据被访问时，从链表头开始顺序遍历链表。
1.如果此数据之前已经缓存在链表中，我们遍历得到这个数据对应的节点，将数据从原位置中删除后，再添加到链表头部
2.如果此数据没有缓存再链表中，分两种情况：
如果此时内存满时，将尾节点删除，新的节点插入到链表的头部
如果内存未满，直接插入到链表头部
因为不管缓存有没有满，我们都需要遍历一遍链表，所以这种基于链表的实现思路，缓存访问的时间复杂度为 O(n)。实际上，我们可以继续优化这个实现思路，比如引入散列表（Hash table）来记录每个数据的位置，将缓存访问的时间复杂度降到 O(1)。