看容易理解“链表”，实现“ LRU缓存消除算法”

前面的部分学习了“链接列表”和“时间和空间复杂性”的概念. 本节将结合``循环列表''，``双向链接列表''和``利用空间的设计思想''来设计一个非常有趣的缓存消除策略: LRU缓存消除算法.

三种最常见的链表结构

循环链表的概念

如上所示: 单链接列表的尾节点指针指向一个空地址链表的实现，指示这是最后一个节点. 循环链表的尾节点指针指向链表的头节点.

因此，循环链表是特殊的单链表. 它和单个链表之间的唯一区别是尾节点. 它像一个环一样首尾相连，因此被称为“循环链表”.

循环链表的特征

与单链表相比，圆形链表的优点是从链端到链头更方便. 当要处理的数据具有环形结构时，适合使用圆形链表.

双向链表概念

双向链接列表也称为双向链接列表. 这是一种链表. 它的链接方向是双向的. 每个数据节点都包含两个指向直接后继者和直接前任者的指针.

因此，从双向链表中的任何节点开始，您都可以轻松访问其前任节点和后继节点.

在双向链表数据结构中，将有两个更重要的参数: pre和next.

单链表和双链表的比较

双向链表的功能

双向链表的基本操作

1. 添加元素.

与单链列表相比，双链列表可以实现O（1）时间复杂度，而单链列表则需要O（n）时间复杂度.

双向链表的其他元素包括头插值和尾插值.

头部插值和尾部插值

头插入方法: 链接列表的左侧称为链接列表的头部，右侧称为链接列表的尾部. 头部插入方法是固定右侧，并将每个新元素添加到左侧头部.

尾部插入方法: 链表的左侧被称为链表的头部，而右侧被称为链表的尾部. 尾部插值方法是固定左侧，每个新添加的内容都位于链表右侧的末尾.

2. 查询元素

查询元素

双向链表的灵活性是要知道链表中的元素结构可以开始向左或向右遍历以找到所需的元素结构. 因此，对于有序的链表，双链表的按值查询效率要高于单链表. 因为我们可以记录最后搜索的位置p，所以每次查询时，根据要搜索的值与p大小之间的关系，我们可以决定是向前搜索还是向后搜索，因此平均而言，我们只需要查找一半数据.

3. 删除元素

在实际的软件开发中，从链接列表中删除数据仅是两种情况:

删除元素

对于双向链表，双向链表中的节点已保存了先前节点的指针，并且删除时无需像单个链表那样遍历. 因此，对于第二种情况，删除单个链表的时间复杂度为O（n），而双链表的时间复杂度仅为O（1）.

双向循环链表

双向循环链表

如图所示，双循环链表的概念很容易理解: “双链表” +“循环链表”的组合.

缓存消除策略

缓存是一项可以提高数据读取性能的技术. 它广泛用于硬件设计和软件开发，例如常见的CPU缓存，缓存，浏览器缓存等.

缓存的大小是有限的. 当缓存已满时，应清除哪些数据并保留哪些数据？这需要确定缓存消除策略. 共有三种策略: 先进先出策略FIFO（先进先出），最少使用的策略LFU（最少使用）和最近最少使用的策略LRU（最近最少使用）.

LRU缓存策略已在各种语言的第三方框架中广泛使用. 程序员Xiao Wu已经接触Java的“ Mybatis”，iOS的“ YYCache”和“ Lottie”等.

LRU缓存消除算法:

LRU是最近最少使用的策略的缩写. 它基于对数据的历史访问记录来消除数据. 核心思想是“如果最近访问过数据，那么将来被访问的可能性也会更高. ”

LRU概念

链接列表实现LRU

使用双重链接列表连接缓存的所有位置. 当一个位置被击中时，将链接列表的位置调整为链接列表头的位置. 新添加的缓存直接添加到链接列表的头部.

通过这种方式，在执行了多个Cache操作之后，最近命中的内容将移至链接列表的开头，但不会命中，但要移至链接列表的后面，链接列表的末尾表示最近的链接已使用的缓存.

当需要替换内容时，链接列表的最后一个位置是命中最少的位置. 我们只需要删除链表的最后一部分即可.

链接列表实现LRU的演示

如果此数据之前已被缓存在链表中，则遍历获取与该数据相对应的节点，将其从原始位置删除，然后将其插入链表的头部. 如果此数据不在缓存列表中链表的实现，则可以分为两种情况:

链接列表实现LRU

从中可以发现，如果缓存空间足够大，则存储了足够的数据，并且在缓存中命中数据的可能性越大，代码执行速度就越快. 这是时间空间的设计思想.

对于程序开发，时间复杂度和空间复杂度可以相互转换. 简而言之，它是:

作者简介: 哈尔滨工业大学炉渣的作家程序员Xiao Wu，目前正在学习算法，开源项目“ LeetCodeAnimation” 5500星，GitHub连续第一个月的趋势列表. 欢迎大家关注我的微信公众号: 五分钟内学习算法，一起学习，共同进步！

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-278824-1.html