链表——最基本的数据结构之一 | 经典链表应用场景:LRU 缓存淘汰算法


和数组相同,链表也是一种线性表结构。作为非常基础、非常常用的两种数据结构,数组和链表经常被拿来比较。

链表定义

  1. 链表是一种线性表数据结构;
  2. 从底层存储结构上看,链表不需要一整块连续的存储空间,而是通过“指针”将一组零散的内存块串联起来使用;
  3. 链表中的每个内存块被称为链表的“结点”,每个结点除了要存储数据外,还需要记录上(下)一个结点的地址。

链表特点

  1. 插入、删除数据效率高,只需要考虑相邻结点的指针改变,不需要搬移数据,时间复杂度是 O(1)。
  2. 随机查找效率低,需要根据指针一个结点一个结点的遍历查找,时间复杂度为O(n)。
  3. 与内存相比,链表的空间消耗大,因为每个结点除了要存储数据本身,还要储存上(下)结点的地址。

常用的链表类型

链表结构五花八门,常用的有三种:单链表、循环链表、双向链表和双向循环列表。

单链表

单链表结构示意图
如图所示:

  1. 单链表的每个节点只包含一个后继指针;
  2. 单链表的头结点尾结点比较特殊,头结点用来记录链表的基地址,是链表遍历的起点,尾结点的后继指针不指向任何结点,而是指向一个空地址NULL
  3. 单链表的插入、删除操作时间复杂度为O(1),随机查找时间复杂度为O(n)。

单链表操作示意图

循环链表

循环列表是一种特殊的单链表,它跟单链表唯一的区别就在于它的尾结点又指回了链表的头结点,首尾相连,形成了一个环,所以叫做循环链表。
循环链表结构示意图
与单链表相比,循环链表的优点是从链尾到链首比较方便,适用于处理具有环形结构的数据问题,比如著名的约瑟夫问题。

双向链表

双向链表中的每个结点具有两个方向指针,后继指针(next)指向后面的结点,前驱指针(prev)指向前面的结点。
双向链表也有两个特殊结点,首节点的前驱指针和尾结点的后继指针均指向空地址NULL
双向链表结构示意图
与单链表相比,储存同样的数据,双向链表会占用更多的内存空间。虽然多占用了空间,但是双向链表在处理根据已知结点查找上一节点、有序链表查找等问题上,都表现的更灵活高效。

双向循环链表

双向循环链表结构示意图

链表&数组对比

链表&数组性能对比

数组缺点

  1. 数组必须占用整块、连续的内存空间,如果声明数组过大,可能回导致“内存不足”。
  2. 数组不够灵活,一旦需要扩容,会重新申请连续整块空间,并需要把原数组的数据全部拷贝到新申请的空间。

链表缺点

  1. 内存空间消耗更大,用于储存结点指针信息。
  2. 对链表进行频繁的插入、删除操作会导致频繁的内存申请、释放,容易造成内存碎片,如果是JAVA语言,还有可能会导致频繁的GC(Garbage Collection,垃圾回收)。

经典的链表应用场景: LRU 缓存淘汰算法

缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
缓存空间的大小有限,当缓存空间被用满时,哪些数据应该被清理出去,哪些数据应该被保留?这就需要缓存淘汰策略来决定。常见的缓存清理策略有三种:先进先出策略FIFO(First In, First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略LRU(Least Recently Used)。
如何用链表来实现LRU缓存淘汰策略呢?
思路:维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头部开始顺序遍历链表。

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

如果此时缓存未满,可直接在链表头部插入新节点存储此数据;
如果此时缓存已满,则删除链表尾部节点,再在链表头部插入新节点。

本文发表于2018年10月24日 22:07
阅读 1792 讨论 0 喜欢 0

日韩化妆品代购 正品保证 假一赔十

刀架在脖子上让发的,走过路过看一下8....

讨论

周娱

君子和而不同
按照自己的方式,去度过人生

7286 2566110
抢先体验

扫码体验
趣味小程序
文字表情生成器

加入组织

扫码添加周娱微信
备注“加入组织”
邀请进开发群

闪念胶囊

这个世界上,别人只会看你现在的样子而不是以后的样子。你以后的样子只有自己才相信。如果没有执行力,一切都是虚妄。

对普通人来说,人和人相处其实最重要的是感觉。感觉不好,你说什么都没用,怎么解释都没用,越说越错,反正最后不好的锅都往你身上扣。所谓“说你行你就行,不行也行。说你不行,你就不行,行也不行”就是这个意思。狼要吃人根本不需要理由,你也同样叫不醒装睡的人。遇到这种情况,早点闪人才是上策。不过大部分人的问题是没有闪人的心态,能力,和资源。

考985不牛逼,考上才牛逼。创业不牛逼,创业成功才牛逼。这个社会上很多人把目标当成牛逼的资本,牛逼哄哄的,死活不听劝,然后做的一塌糊涂,给别人添麻烦,让别人帮他料理后事,对此只能呵呵。

当你尝到用生气解决问题的甜头后,你就懒得再用其他方式了。你却忽略了,生气是鸩毒啊,剂量用够了,你的关系也玩完了。

年轻的时候你只搞事业不谈恋爱,等你事业有成了,钱相对自由了,你可能已经没有荷尔蒙了。

如果你经常雇佣比你矮小的人,将来我们就会变成矮人国,变成一家侏儒公司。相反,如果你每次都雇用比你高大的人,日后我们必能成为一家巨人公司。

如果一个人有充裕的时间去完成一项工作,那么他就会放慢节奏或者增加其他不必要的工作,直到花光所有的时间。

天空不是人类休息的地方,人类应该去亲近海洋。

一个人的正直程度,取决于他肯为原则付出的牺牲。

Copyright © 2016 - 2018 Cion.
All Rights Reserved.
备案:鲁ICP备16007319号.