链表
2021-02-25 本文已影响0人
一只木鸟
链表通过指针将一组零散的内存块串联起来。
链表类型
单链表：
image.png
双向链表：
image.png
循环链表：
image.png
时间复杂度
插入删除：O(1)
访问元素：O(n)
数据和链表对比：
- 数据在内存空间连续，可以借助CPU的缓存机制，访问的效率更高，链表在内存中不连续，对CPU缓存不友好。
- 数组大小固定，链表动态扩容。
- 链表的插入删除时间复杂度O(1)，随机访问的时间复杂度O(n)；数组的插入删除时间复杂度O(n)，根据下标随机访问的时间复杂度O(1)，根据元素值访问的时间复杂度O(n)。
- 链表额外存储指针，相对数组，比较耗费内存。
如何基于链表实现 LRU 缓存淘汰算法
思路：维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
- 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
- 如果此数据没有在缓存链表中，又可以分为两种情况：
- 如果此时缓存未满，则将此结点直接插入到链表的头部。
- 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
