链表——最基本的数据结构之一 | 经典链表应用场景: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
阅读 38 讨论 0 喜欢 0

讨论

周娱

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

4601 1243936
抢先体验

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

加入组织

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

闪念胶囊

不积跬步无以至千里,越焦虑越要扎实干。

不要试图鹤立鸡群,趁早离开那群鸡!

程序员过节需要的不是美女、不是美食、不是不加班!他们需要的是写代码,一群人写、往死里写、通宵写!!那种暗流涌动的狂欢,远比虚无庸俗的食色更让他们振奋!! by芋头

面试的时候,常常会问数组和链表的区别,很多人都回答说,“链表适合插入、删除,时间复杂度 O(1);数组适合查找,查找时间复杂度为 O(1)”。 实际上,这种表述是不准确的。数组是适合查找操作,但是查找的时间复杂度并不为 O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是 O(logn)。 所以,正确的表述应该是,数组支持随机访问,根据下标随机访问的时间复杂度为 O(1)。

找一个bug就好比从一泡烂泥里找一条泥鳅,写一个bug就好比往一泡烂泥里丢一条泥鳅进去

数据结构在某种程度上和设计模式类似,都是前辈的武功套路。不同的是,设计模式是近几十年的卓越程序员的智慧结晶,而数据结构是几百上千年的无数科学家、数学家的智慧沉淀,更加具有深厚的背景。

18年元旦立下的flag要集中突击一下了.....

人生是一场马拉松,起跑的优劣对于整段路途而言并没有那么重要,笑到最后的都是一直在跑的人,也就是一辈子都在学习的人。

角色是谁并不重要,重要的是会不会抢戏~

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