链表

发表于

链表

开篇思考:thinking:

链表是如何实现LRU(Least Recently Used)缓存淘汰算法？

知识扩展

缓存：提高数据读取性能的技术，常见的缓存有CPU缓存、数据库缓存、浏览器缓存等。

  • :yum:为什么要使用缓存？缓存的大小有限，当缓存用满时，就要将一些数据内清理出去，一些数据保留下来，这就要用缓存淘汰策略来决定。
  • 常见的缓存策略有：先进先出策略FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）

关于链表

链表与数组：

数组是一块连续的空间，当内存中没有连续的，足够大的空间时，即使内存剩余空间大于所申请空间时，仍然会申请失败。链表并不需要连续的内存空间，它会通过“指针”将零散的内存块串联起来使用。

常见的链表结构

单链表
循环链表
  • 一种特殊的单链表，与单链表的区别在于尾节点，循环链表的尾节点指针是指向链表的头结点，首尾相连
  • 循环链表处理的数据具有环形结构特点时，就比较适合，例如约瑟夫问题
双向链表
  • 双向链表需要额外的两个空间来存储后继节点和前驱节点地址。所以会比单链表占用更多的内存空间。

双向链表和单链表比较：

  • 删除操作
    • 删除节点中“值等于某个给定值”的节点
      • 单链表与双向链表时间复杂度都为O(n)
    • 删除给定指针指向的节点
      • 双向链表时间复杂度为O(1)
  • 插入操作（同上）

牺牲空间换取时间，在java中的LinkedHashMap就是使用双向链表

数组与链表

数组不支持动态扩容，当空间不足时，只能申请更大的一块空间将原数组拷贝进去，非常耗时，而链表没有大小的限制，天然的支持动态扩容。

链表的缺点：链表中的每个节点都需要额外的空间存储一份指向下一个节点的指针，内存消耗会翻倍，并且当对链表频繁的进行插入和删除操作时，会导致频繁的内存申请与释放，容易造成内存碎片，如果是Java语言，就可能会导致频繁的GC（GarBage Collection）

  • 当使用数组时，CPU在从内存读取数据时，会先把读取到的数据加载到CPU中。而CPU每次从内存读取数据时并不是每次访问特定的地址，而是一次读取一个数据块，并将其保存在CPU缓存中，在下次访问数据时就会先从CPU缓存开始查询，如果占不到才会再次从内存中读取。这样就实现了比内存访问速度更快的机制，CPU缓存就是为了弥补内存访问速度过慢与CPU执行速度快之间的差异而引入的。

关于链表实现LRU缓存淘汰算法

:ballot_box_with_check:思路：维护一个有序单链表，越靠近链表尾部节点就是越早之前被访问的。当有一个新的数据被访问时，就从表头开始顺序遍历链表。

  1. 如果次数据之前已经被缓存到链表中，则便利得到这个数据对应的节点，并将其从原来的位置删除，然后再插入到链表的头部。
  2. 如果此数据没有在缓存链表中，可以分为两种情况
    • 如果此时缓存未满，则将此节点直接插入到链表的头部
    • 如果此时缓存已满，则链表尾节点删除，将新的数据插入到链表的头部

时间复杂度：不论缓存有没有满，都需要遍历一遍链表，所以该思路缓存方寸的时间复杂度为O(n)，

  • 优化扩展：可以引用散列表（Hash table)来记录每个数据的位置，将缓存访问的时间复杂度将为O(1)

数组实现LRU缓存淘汰策略

  1. 首位置保存最新访问数据，末尾位置优先清理
    • 当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；
    • 当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。
    • 缓存用满时，则清理掉末尾的数据，时间复杂度为O(1)。
  2. 首位置优先清理，末尾位置保存最新访问数据
    • 当访问的数据未存在于缓存的数组中时，直接将数据添加进数组，当前只有一个元素时间复杂度为O(1)；
    • 当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时也需移动数组元素，时间复杂度为O(n)。
    • 缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。
      • 优化扩展：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。

:jack_o_lantern:练习：如何判断一个字符串（使用单链表存储）是否是回文字符串？

思路一：

  • 使用快慢指针找到中间节点
  • 创建临时链表，遍历后半部分链表，并将后半部分节点数据头插入临时链表
  • 将链表前半部分与临时链表比较，判断是否为回文字符串
  • 删除临时链表

时间复杂度为O(n)，空间复杂度为O(n)

思路二：

  • 使用快慢指针找到链表中间节点
  • 记录中间节点，将中间节点之后的节点逆置
  • 前半部分与后半部分比较，判断是否为回文字符串
  • 最后将后半部分链表逆置复原

时间复杂度为O(n)，空间复杂度为O(1)