算法学习笔记：链表（上），如何实现LRU缓存淘汰算法
数组在插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移，所以时间复杂度是O(n)，而链表在插入和删除时，不需要做搬移，因为链表的存储空间本身就是不连续的，时间复杂度为O(1)。
但也因为链表是非连续存储的，所以无法像数组那样通过寻址公式可以直接计算出对应的内存地址，需要根据节点一个个依次遍历，直到找到相应的节点，链表的随机访问的性能就没有数组好，需要O(n)的时间复杂度。
- 单链表
第一个节点叫头节点，最后一个节点叫尾节点，最后一个节点指向一个空地址NULL。
- 循环列表
循环列表是一种特殊的单链表，它跟单链表的区别在尾节点指针，循环列表的尾节点指针指向链表的头节点，形成环状。约瑟夫问题就特别适合用循环列表。
- 双向链表
双向链表有两个方向的指针，有一个后继指针next指向后面的节点，还有一个前驱指针prev指向前面的节点。需要额外的两个空间来存储后继节点和前去节点的地址。实际开发中，更常用的是双向链表，例如：在删除给定指针指向的节点时，双向链表支持查找前驱节点，时间复杂度为O(1)，而单向链表需从头开始遍历链表，时间复杂度为O(n)。
LinkedHashMap的实现上也使用了双向链表这种数据结构。实际上，这是一种空间换时间的思想。
如何实现LRU缓存淘汰算法
- 思路
维护一个有序的单链表，越靠近链表尾部的节点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的节点，并将其从原来的位置删除，然后在插入到链表的头部。
如果此数据没有在缓存链表中，又可以分为两种情况：
- 如果此时缓存未满，则将此节点直接插入到链表的头部；
- 如果此时缓存已满，则链表尾部节点删除，将新的数据节点插入链表的头部。
不管缓存有没有满，我们都需要遍历一遍链表，所以基于链表的实现思路，缓存访问的时间复杂度为O(n)。
实际上，我们可以继续优化这个思路，比如引入散列表(Hash Table)来记录每个数据的位置，将缓存访问的时间复杂度降到O(1)。
以上是 算法学习笔记：链表（上），如何实现LRU缓存淘汰算法 的全部内容， 来源链接： utcz.com/z/515388.html
