数据结构与算法之 - LinkedList

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

缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,如常见的:CPU缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。常见的缓存策略有三种:先进先出策略FIFO(First In First Out)、最少使用策略LFU(Least Frequently Used)、最近最少使用策略LRU(Least Recently Used)。

如何用链表实现LRU缓存淘汰策略呢?

思路:维护一个有序单链表,越靠近链表尾部的节点是越早访问的。当有一个新的数据被访问时,我们从链表头顺序遍历链表。

1. 如果此数据之前已经被缓存在链表中,我们遍历得到这个数据对应的节点,并将其从原来的位置删除,
    然后再插入到链表的头部。
2. 如果此数据没有在链表的缓存中,有可以分为两种情况:

    * 如果此时缓存未满,则直接将数据插入到链表的头部。

    * 如果此时数据已满,则链表尾节点删除,将新的数据插入到链表的头部。

缓存访问时间复杂度,因为不管缓存有没有满,我们都需要遍历一遍链表,所以这种基于链表的实现思路,缓存访问的时间复杂度为O(n).

实际上,我们可以引入散列表(Hash table)来记录每个数据的位置,将缓存访问的时间复杂度降到O(1)。

链表回文问题的应用:

如果一个字符串是通过单链表来存储,那该如何来判断一个回文串呢?对应的时间空间复杂度多少?

思路:

  1. 使用快慢两个指针定位中间节点的位置,快指针步长为2,慢指针步长为1,慢指针遍历的同时对前半部分进行逆序,当快指针遍历到尾节点的时候,慢指针正好是中间节点(这里要区分奇偶的情况)
    1.1 奇数情况,中点位置不需要矫正
    1.2 偶数情况,使用偶数定位中点,要确定返回上中位数或下中位数
    1.2.1 如果是返回上中位数,后半部分串头取next
    1.2.2 如果是返回下中位数,后半部分串头即是当前节点位置,但前半部分串尾要删除掉当前节点。
  2. 中心点新开一个指针往回走,慢指针继续向前。
  3. 每次遍历判断两个节点是否为回文,当慢指针遍历完整个链表,就可以判断这是回文,否则提前退出。
  4. 恢复现场

总的时间复杂度指针遍历一遍为O(n),空间复杂度因为只开辟了三个指针,所以为O(1)。