您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

谈谈对链表的理解

时间:2022-10-04 10:01:31  来源:今日头条  作者:掂掂三生有幸

✨最近有一些粉丝问了我个问题,我平时是怎样学习一门新的技术的,文章开始之前我先来分享一下我的制胜法宝。

博主学习方法

“三刷”官方文档或源码是我高效学习一门新的技能的制胜法宝

1刷从头看到尾,扫清知识盲点,搞清楚概念;

2刷必须手敲,而且要写注释和总结;

3刷先只写注释,不看文档实现功能,遇到问题再和文档比较,加深理解。

前言

上篇我们总结了对数组的理解,这篇再谈谈对链表的理解。

本篇文章主要分析如下几个问题:

  1. 链表和数组相比有哪些不同点?它的优点是什么?
  2. 链表有哪些类别?它们各自的优缺点是什么?
  3. 如何使用链表实现LRU算法?

链表相对于数组而言,是两种不同的内存组织方式,链表不需要连续的内存空间,天然支持动态扩容,而且不像数组扩容那样需要搬运数据。链表大小等于实际使用大小,不存在浪费空间的现象。链表适合插入和删除操作,时间复杂度为O(1),但是并不意味着适合非常频繁地插入和删除,因为那样会导致频繁地申请内存和释放内存,容易造成内存碎片,从而提高GC的频率。

✨✨单向链表

每一块内存区域称为一个节点,每个节点有两块区域,数据域保存节点数据,指针域指向下一个节点的地址。其中,头节点是整个链表的基地址,通过它可以遍历整个链表;尾节点的指针值为空,不指向任何地址。

单链表比较适合插入和删除操作,时间复杂度为O(1),注意此处不包含查找到该元素的时间,但是查询操作效率较低,时间复杂度为O(n);

 

单链表结构示意

✨✨✨双向链表

每一块内存区域称为一个节点,每个节点有三块区域,前指针域指向上一个节点的地址,数据域保存节点数据,后指针域指向下一个节点的地址。和单向链表相比,存储相同多的数据,双向链表需要的存储空间更多。

双向链表的插入、删除和查询操作都要比单向链表的相同操作的效率更高:

  • 插入
  • 如果需要在第k个节点处插入一个新的节点,那么单链表需要找到前一个节点,时间复杂度为O(n),而双向链表只需要往前遍历一个节点就能找到,时间复杂度为O(1)。
  • 删除
  • 如果是需要删除给定的元素,那么就只能从第一个节点开始遍历,这种情况两种链表的时间复杂度是一样的;但是如果是给定需要删除元素的指针,那么单链表因为要找到前一个元素p,使得p.next指向待删除元素的下一个节点,所以时间复杂度为O(n),而双向链表则只需要往前遍历一个节点就能找到,时间复杂度为O(1)。
  • 查询
  • 对于有序链表,每次查找元素k,双向链表可以根据和当前节点的值得大小比较来决定往前遍历还是往后遍历,而单链表只能往后或者从头结点重新开始遍历。

因此,即便双向链表比较占用空间,但这是一种空间换时间的设计思想,使用场景反而比单向链表更多。

 

双向链表结构示意

✨✨✨✨循环链表

循环链表是一种特殊的单链表,区别是其尾节点的指针域不是空,而是指向头节点。其优点就是从链表尾部到链表头部比较方便,当我们需要处理环形结构的数据时,就比较合适。

 

循环链表结构示意

当然,将双向链表和循环链表组合起来,就能形成一个双向循环链表,这个用得不多,不赘述。

 

双向循环链表结构示意

✨✨✨✨✨使用链表实现LRU

常见的缓存淘汰策略有三种,FIFO(先进先出Firt In First Out)、LFU(最少使用Least Frequently Used)、LRU(最近最少使用Least Recently Used)。

  • 对于当前数据,遍历链表,如果在链表中已经存在了,那么删除该节点,并在链表头插入该数据;
  • 如果在链表中不存在,判断当前链表是否小于最大长度,如果没有,直接插入到头部;
  • 如果已经等于最大长度,那么删除尾节点后,再插入到头部;
  • 该算法的时间复杂度为O(n),因为无论如何,都要遍历一次链表;


Tags:链表   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
一:链表是什么 1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。 2、结点包括两个部...【详细内容】
2022-10-07  Tags: 链表  点击:(1)  评论:(0)  加入收藏
✨最近有一些粉丝问了我个问题,我平时是怎样学习一门新的技术的,文章开始之前我先来分享一下我的制胜法宝。✨博主学习方法“三刷”官方文档或源码是我高效学习一门新的技能的...【详细内容】
2022-10-04  Tags: 链表  点击:(0)  评论:(0)  加入收藏
0. 学习目标在顺序存储方式中,根据数据元素的序号就可随机存取表中任何一个元素,但同时在插入和删除运算需要移动大量的元素,造成算法效率较低。解决此缺陷的一个办法是:对线性...【详细内容】
2022-07-29  Tags: 链表  点击:(62)  评论:(0)  加入收藏
一:链表是什么 1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。 2、结点包括两个部...【详细内容】
2022-07-04  Tags: 链表  点击:(1)  评论:(0)  加入收藏
遵从所有教材以及各类数据结构相关的书书籍,我们先从线性表开始入门。今天这篇文章更偏概念,是关于有线性表的一个知识点的汇总。上文说过,物理结构是用于确定数据以何种方式存...【详细内容】
2021-07-19  Tags: 链表  点击:(161)  评论:(0)  加入收藏
当我们在聊到链表反转的时候,一定说的都是单链表,双链表本身就具有前驱指针 Prev 和后续指针 next,无需进行翻转。单链表反转,反转后的效果如下: 看起来很简单,只需要将单链表所...【详细内容】
2021-01-12  Tags: 链表  点击:(264)  评论:(0)  加入收藏
问题描述输入两个链表,找出它们的第一个公共节点。如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入:intersectVal = 8,listA = [4,1,8,4,5],listB = [5,0,1,8,4,5],skipA...【详细内容】
2020-10-19  Tags: 链表  点击:(212)  评论:(0)  加入收藏
给定一个带有头节点的单链表,如何将其逆序,也就是说head->a->b->c,变为head->c->b->a?难点:这个需要了解链表的结构,每一个链表除了存储自身的元素之外,还会存储下一个结点的地址,...【详细内容】
2020-09-29  Tags: 链表  点击:(163)  评论:(0)  加入收藏
数组作为一个顺序储存方式的数据结构,可是有大作为的,它的灵活使用为我们的程序设计带来了大量的便利;...【详细内容】
2020-08-31  Tags: 链表  点击:(77)  评论:(0)  加入收藏
什么是链表?当你用一个数组存放数据时就需要给它定义一个长度,如果定一个未知的数据,你就需要扩大数组的范围,有时如果由于某种特殊原因,数据增加,有需要重新修改程序,扩大数组的存...【详细内容】
2020-08-11  Tags: 链表  点击:(243)  评论:(0)  加入收藏
▌简易百科推荐
一:链表是什么 1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。 2、结点包括两个部...【详细内容】
2022-10-07  legendarykk  CSDN  Tags:链表   点击:(1)  评论:(0)  加入收藏
一、什么是递归?自己调用自己,当业务逻辑符合以下三个条件的时候,就可以考虑使用递归来实现。 一个问题可以分解为多个子问题; 当前问题与其子问题除了数据规模不同外,求解思路...【详细内容】
2022-10-07  掂掂三生有幸    Tags:递归算法   点击:(1)  评论:(0)  加入收藏
✨最近有一些粉丝问了我个问题,我平时是怎样学习一门新的技术的,文章开始之前我先来分享一下我的制胜法宝。✨博主学习方法“三刷”官方文档或源码是我高效学习一门新的技能的...【详细内容】
2022-10-04  掂掂三生有幸  今日头条  Tags:链表   点击:(0)  评论:(0)  加入收藏
最经典最常用的排序算法有:冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序和桶排序。这些排序算法可以按照时间复杂度分为三类: O(n^2)—&mdash...【详细内容】
2022-10-01  掂掂三生有幸  今日头条  Tags:排序算法   点击:(1)  评论:(0)  加入收藏
简介布隆过滤器(BloomFilter)是一种用于判断元素是否存在的方式,它的空间成本非常小,速度也很快。但是由于它是基于概率的,因此它存在一定的误判率,它的Contains()操作如果返回tru...【详细内容】
2022-09-13  java保佑我发大财  今日头条  Tags:布隆过滤器   点击:(32)  评论:(0)  加入收藏
1、A GPU accelerated Genetic Algorithm for the Construction of Hadamard Matrices Andras Balogh, Raven Ruiz这篇论文使用遗传算法来构建Hadamard矩阵。 生成随机矩...【详细内容】
2022-09-06  deephub  今日头条  Tags:遗传算法   点击:(48)  评论:(0)  加入收藏
导读:ClickHouse已经成为行业主流且热门的开源引擎。随着业务数据量扩大,场景覆盖变广泛,在复杂query场景下,ClickHouse容易存在查询异常问题,影响业务正常推进。本次主要分享字...【详细内容】
2022-09-05  互联共商     Tags:ClickHouse   点击:(32)  评论:(0)  加入收藏
我们知道悲观锁在高并发的场景下,激烈的锁竞争会造成线程阻塞,大量阻塞线程会导致系统上下文切换,增加系统的性能开销。那么有没有可能实现一种非阻塞的锁机制来保证线程的安全...【详细内容】
2022-08-28  互联网资讯看板  网易  Tags:乐观锁   点击:(38)  评论:(0)  加入收藏
0 | 0001100 10100010 10111110 10001001 01011100 00 | 10001 | 1 1001 | 0000 00000000twitter在把存储系统从MySQL迁移到Cassandra的过程中由于Cassandra没有顺序ID生成...【详细内容】
2022-08-20  梦幻随风    Tags:snowflake   点击:(43)  评论:(0)  加入收藏
雪花算法SnowFlake 算法,是 Twitter 开源的分布式 id 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 id。在分布式系统中的应用十分广泛,且ID 引入...【详细内容】
2022-08-16  雪地大懒猫    Tags:雪花算法   点击:(59)  评论:(0)  加入收藏
站内最新
站内热门
站内头条