当前位置:   article > 正文

数据结构与算法之美(链表)_链表中的前驱后继

链表中的前驱后继

一、什么是链表

  • .和数组一样,链表也是一种线性表。
  • 从内存结构来看,链表的内存结构是不连续的内存空间,是将一组零散的内存块串联起来,从而进行数据存储的数据结构。
  • 链表中的每一个内存块被称为节点Node。节点除了存储数据外,还需记录链上下一个节点的地址,即后继指针next

二、为什么使用链表?

  • 插入、删除数据效率高**O(1)**级别(只需更改指针指向即可),随机访问 效率低O(n) 级别(需要从链头至链尾进行遍历)。
  • 和数组相比,内存空间消耗更大,因为每个存储数据的节点都需要额外的空间存储后继指针。

三、常用链表

1.单链表

1)每个节点只包含一个指针,即后继指针
2)单链表有两个特殊的节点,即首节点尾节点
首节点地址表示整条链表,尾节点的后继指针指向空地址null。
3)性能特点:插入删除节点的时间复杂度为O(1)查找的时间复杂度为O(n)
在这里插入图片描述
在这里插入图片描述

2.循环链表

1)除了尾节点的后继指针指向首节点的地址外均与单链表一致。
2)适用于存储有循环特点的数据,比如约瑟夫问题
在这里插入图片描述

3.双向链表

1)节点除了存储数据外,还有两个指针分别指向前一个节点地址(前驱指针prev)和下一个节点地址(后继指针next)。
2)首节点的前驱指针prev和尾节点的后继指针均指向空地址。
3)性能特点:和单链表相比,存储相同的数据,需要消耗更多的存储空间。插入、删除操作比单链表效率更高O(1)级别。
在这里插入图片描述

4.双向循环链表

首节点的前驱指针指向尾节点,尾节点的后继指针指向首节点。
在这里插入图片描述

四、数组和链表的区别

1.插入、删除和随机访问的时间复杂度

数组:插入、删除的时间复杂度是O(n),随机访问的时间复杂度是O(1)。
链表:插入、删除的时间复杂度是O(1),随机访问的时间复杂端是O(n)。

2.数组缺点

1)若申请内存空间很大,比如100M,但若内存空间没有100M的 连续空间 时,则会申请失败,尽管内存可用空间超过100M。
2)大小固定,若存储空间不足,需进行扩容,一旦扩容就要进行数据复制,而这时非常费时的。

3.链表缺点

1)内存空间消耗更大,因为需要额外的空间存储指针信息
2)对链表进行频繁的插入和删除操作,会导致频繁的内存申请和释放,容易造成内存碎片,如果是Java语言,还可能会造成频繁的GC(自动垃圾回收器)操作。

五、如何分别用链表和数组实现LRU缓冲淘汰策略?

1)什么是缓存?

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

2)为什么使用缓存?

缓存的大小是有限的,当缓存被用满时,哪些数据应该被清理出去,哪些数据应该被保留?就需要用到缓存淘汰策略。

3)什么是缓存淘汰策略?

指的是当缓存被用满时清理数据的优先顺序。

4)有哪些缓存淘汰策略?

常见的3种包括先进先出策略FIFO(First In,First Out)最少使用策略LFU(Least Frenquently Used)最近最少使用策略LRU(Least Recently Used)

5)链表实现LRU缓存淘汰策略

当访问的数据没有存储在缓存的链表中时,直接将数据插入链表表头,时间复杂度为O(1);当访问的数据存在于存储的链表中时,将该数据对应的节点,插入到链表表头,时间复杂度为O(n)。如果缓存被占满,则从链表尾部的数据开始清理,时间复杂度为O(1)。

6)数组实现LRU缓存淘汰策略

方式一:首位置保存最新访问数据,末尾位置优先清理

当访问的数据未存在于缓存的数组中时,直接将数据插入数组第一个元素位置,此时数组所有元素需要向后移动1个位置,时间复杂度为O(n);当访问的数据存在于缓存的数组中时,查找到数据并将其插入数组的第一个位置,此时亦需移动数组元素,时间复杂度为O(n)。缓存用满时,则清理掉末尾的数据,时间复杂度为O(1)。

方式二:首位置优先清理,末尾位置保存最新访问数据

当访问的数据未存在于缓存的数组中时,直接将数据添加进数组作为当前最有一个元素时间复杂度为O(1);当访问的数据存在于缓存的数组中时,查找到数据并将其插入当前数组最后一个元素的位置,此时亦需移动数组元素,时间复杂度为O(n)。缓存用满时,则清理掉数组首位置的元素,且剩余数组元素需整体前移一位,时间复杂度为O(n)。(优化:清理的时候可以考虑一次性清理一定数量,从而降低清理次数,提高性能。)

六、如何轻松的写出正确的代码

1. 理解指针或引用的含义

什么是指针?指针是一个变量,该变量中存的是其它变量的地址。将普通变量赋值给指针变量,其实是把它的地址赋值给指针变量。

2. 警惕指针丢失和内存泄漏

在插入和删除结点时,要注意先持有后面的结点再操作,否者一旦后面结点的前继指针被断开,就无法再访问,导致内存泄漏。

3. 利用哨兵简化难度

链表的插入、删除操作,需要对插入第一个结点和删除最后一个节点做特殊处理。利用哨兵对象可以不用边界判断,链表的哨兵对象是只存指针不存数据的头结点。
在这里插入图片描述

4. 重点留意边界条件处理

操作链表时要考虑链表为空、一个结点、两个结点、头结点、尾结点的情况。学习数据结构和算法主要是掌握一系列思想,能在其它的编码中也养成考虑边界的习惯。

5. 举例画图,辅助思考

对于比较复杂的操作,可以用纸笔画一画,释放脑容量来做逻辑处理(时间换空间思想),也便于完成后的检查。
在这里插入图片描述

6. 多写多练,没有捷径

孰能生巧,不管是什么算法,只有经过反复的练习,才能信手拈来。(又是废话了)

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/650579
推荐阅读
相关标签
  

闽ICP备14008679号