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

谈谈对链表的理解

时间: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:链表   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,不构成投资建议。投资者据此操作,风险自担。如有任何标注错误或版权侵犯请与我们联系,我们将及时更正、删除。
▌相关推荐
C++实现链表:原理、代码与解析
链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。与数组不同,链表不是连续的内存空间,而是通过指针链接在一起。下面我们将深入探讨如何...【详细内容】
2023-12-22  Search: 链表  点击:(112)  评论:(0)  加入收藏
一文搞定双链表,让你彻底弄懂线性表的链式实现
前言前面有很详细的讲过线性表(顺序表和链表),当时讲的链表以单链表为主,但在实际应用中双链表有很多应用场景,例如大家熟知的LinkedList。双链表与单链表区别单链表和双链表都...【详细内容】
2023-11-08  Search: 链表  点击:(249)  评论:(0)  加入收藏
如何在C++程序中创建链表
引言:链表是一种常用的数据结构,它在C++程序中的应用非常广泛。本文将介绍如何在C++程序中创建链表,并提供了一些基本的链表操作示例。通过本文的学习,读者将了解链表的概念、创...【详细内容】
2023-08-16  Search: 链表  点击:(268)  评论:(0)  加入收藏
关于链表的理解
一:链表是什么 1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。 2、结点包括两个部...【详细内容】
2022-10-07  Search: 链表  点击:(335)  评论:(0)  加入收藏
谈谈对链表的理解
✨最近有一些粉丝问了我个问题,我平时是怎样学习一门新的技术的,文章开始之前我先来分享一下我的制胜法宝。✨博主学习方法“三刷”官方文档或源码是我高效学习一门新的技能的...【详细内容】
2022-10-04  Search: 链表  点击:(275)  评论:(0)  加入收藏
Python数据结构之链表详解
0. 学习目标在顺序存储方式中,根据数据元素的序号就可随机存取表中任何一个元素,但同时在插入和删除运算需要移动大量的元素,造成算法效率较低。解决此缺陷的一个办法是:对线性...【详细内容】
2022-07-29  Search: 链表  点击:(336)  评论:(0)  加入收藏
「PHP数据结构」线性表?顺序表?链表?别再傻傻分不清楚
遵从所有教材以及各类数据结构相关的书书籍,我们先从线性表开始入门。今天这篇文章更偏概念,是关于有线性表的一个知识点的汇总。上文说过,物理结构是用于确定数据以何种方式存...【详细内容】
2021-07-19  Search: 链表  点击:(362)  评论:(0)  加入收藏
单链表翻转的三种方式!
当我们在聊到链表反转的时候,一定说的都是单链表,双链表本身就具有前驱指针 Prev 和后续指针 next,无需进行翻转。单链表反转,反转后的效果如下: 看起来很简单,只需要将单链表所...【详细内容】
2021-01-12  Search: 链表  点击:(408)  评论:(0)  加入收藏
找出两个链表的第一个公共节点
问题描述输入两个链表,找出它们的第一个公共节点。如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入:intersectVal = 8,listA = [4,1,8,4,5],listB = [5,0,1,8,4,5],skipA...【详细内容】
2020-10-19  Search: 链表  点击:(374)  评论:(0)  加入收藏
七道经典的关于链表的笔试题目
给定一个带有头节点的单链表,如何将其逆序,也就是说head->a->b->c,变为head->c->b->a?难点:这个需要了解链表的结构,每一个链表除了存储自身的元素之外,还会存储下一个结点的地址,...【详细内容】
2020-09-29  Search: 链表  点击:(268)  评论:(0)  加入收藏
▌简易百科推荐
小红书、视频号、抖音流量算法解析,干货满满,值得一看!
咱们中国现在可不是一般的牛!网上的网友已经破了十个亿啦!到了这个互联网的新时代,谁有更多的人流量,谁就能赢得更多的掌声哦~抖音、小红书、、视频号,是很多品牌必争的流量洼地...【详细内容】
2024-02-23  二手车小胖说    Tags:流量算法   点击:(15)  评论:(0)  加入收藏
雪花算法详解与Java实现:分布式唯一ID生成原理
SnowFlake 算法,是 Twitter 开源的分布式 ID 生成算法。其核心思想就是:使用一个 64 bit 的 long 型的数字作为全局唯一 ID。在分布式系统中的应用十分广泛,且 ID 引入了时间戳...【详细内容】
2024-02-03   一安未来  微信公众号  Tags:雪花算法   点击:(51)  评论:(0)  加入收藏
程序开发中常用的十种算法,你用过几种?
当编写程序时,了解和使用不同的算法对解决问题至关重要。以下是C#中常用的10种算法,每个算法都伴随着示例代码和详细说明。1. 冒泡排序 (Bubble Sort):冒泡排序是一种简单的比...【详细内容】
2024-01-17  架构师老卢  今日头条  Tags:算法   点击:(45)  评论:(0)  加入收藏
百度推荐排序技术的思考与实践
本文将分享百度在推荐排序方面的思考与实践。在整个工业界的推广搜场景上,特征设计通常都是采用离散化的设计,需要保证两方面的效果,一方面是记忆,另一方面是泛化。特征都是通过...【详细内容】
2024-01-09  DataFunTalk  微信公众号  Tags:百度推荐   点击:(77)  评论:(0)  加入收藏
什么是布隆过滤器?如何实现布隆过滤器?
以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?布隆过滤器(Blo...【详细内容】
2024-01-05  Java中文社群  微信公众号  Tags:布隆过滤器   点击:(87)  评论:(0)  加入收藏
面向推荐系统的深度强化学习算法研究与应用
随着互联网的快速发展,推荐系统在各个领域中扮演着重要的角色。传统的推荐算法在面对大规模、复杂的数据时存在一定的局限性。为了解决这一问题,深度强化学习算法应运而生。本...【详细内容】
2024-01-04  数码小风向    Tags:算法   点击:(96)  评论:(0)  加入收藏
非负矩阵分解算法:从非负数据中提取主题、特征等信息
非负矩阵分解算法(Non-negativeMatrixFactorization,简称NMF)是一种常用的数据分析和特征提取方法,主要用于从非负数据中提取主题、特征等有意义的信息。本文将介绍非负矩阵分解...【详细内容】
2024-01-02  毛晓峰    Tags:算法   点击:(64)  评论:(0)  加入收藏
再谈前端算法,你这回明白了吗?
楔子 -- 青蛙跳台阶一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(...【详细内容】
2023-12-28  前端爱好者  微信公众号  Tags:前端算法   点击:(108)  评论:(0)  加入收藏
三分钟学习二分查找
二分查找是一种在有序数组中查找元素的算法,通过不断将搜索区域分成两半来实现。你可能在日常生活中已经不知不觉地使用了大脑里的二分查找。最常见的例子是在字典中查找一个...【详细内容】
2023-12-22  小技术君  微信公众号  Tags:二分查找   点击:(78)  评论:(0)  加入收藏
强化学习算法在资源调度与优化中的应用
随着云计算和大数据技术的快速发展,资源调度与优化成为了现代计算系统中的重要问题。传统的资源调度算法往往基于静态规则或启发式方法,无法适应动态变化的环境和复杂的任务需...【详细内容】
2023-12-14  职场小达人欢晓    Tags:算法   点击:(165)  评论:(0)  加入收藏
站内最新
站内热门
站内头条