链表的详细介绍

目录

链表的简单定义:

链表的分类

单项带头非循环

单向不带头循环链表

实现单向非循环无头链表

定义链表:

实现链表方法

打印链表

头插法:

尾插法:

指定插入:

通过对应值删除节点:

删除所有对应值节点:

​编辑

LinkedListd的介绍

LinkedList的定义:

LinkedList的有参构造方法:

LinkedList的打印:

ArrayList和LinkedList的简单区别:


链表相对于数组优点: 插入或者删除元素的时候不需要移动其他的数据,且也不需要扩容

链表的简单定义:

链表中每个元素称为节点,每个节点由两部分组成(单向链表):数值和next域,next域存储下一个节点的地址,例如下图,可知链表在内存上不一定连续

链表的分类

单向(双向) 非循环(循环) 不带头(带头)链表,三者排列组合后可知有8种链表;

我们主要学习两种:单项不带头非循环链表(笔试和面试的考量对象)以及双向不带头非循环链表(LinkedList的底层逻辑)

简单认识一下:

单向带头非循环

头结点的数值域没有实际作用

单向不带头循环链表

这个head不是指0x112处这个节点而是只存放0x112这个地址值。

实现单向非循环无头链表

定义链表:

链表又节点和头节点组成,每个节点又由数值和next域组成,那么我们可以把节点定义做内部类‘

定义成静态内部类比较方便应用,再者为什么next的类型时ListNode呢,因为每个节点的nxet域是指向下一个节点的,因此头节点和next的类型均为ListNode;同时因为每个链表的头结点只有一个,所以应该定义在LIstNode之外。

实现链表方法

方法的实现方法有很多,一下只是讲述提供案例而已,只要能完整实现即可

在实现链表方法之前我们首先要学会如何将链表的节点连起来:

如图创建了四个节点,通过next将每个节点连起来;

所需要实现的方法:

  //头插法
        public void addFirst(MyStringLeList.ListNode node);
        //尾插法
        public void addLast(MyStringLeList.ListNode node);
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index, MyStringLeList.ListNode node);
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key);
        //删除第一次出现关键字为key的节点
        public void remove(int key);

        //删除所有值为key的节点
        public void removeAllKey(int key);
        //得到单链表的长度
        public int size();
        //清空链表
        public void clear();
        //打印链表
        public void display();

打印链表

打印链表的时候只需要判断循环的结束条件和节点的传递即可;图中把head赋给cur是为了不遗失头节点

记数链表中节点个数;判断链表中是否有某个值:

这两个方法同打印类似较为简单,不多赘述。

头插法:

注意二者赋值顺序即可。

尾插法:

首先要判断链表是否为空;同时要注意循环的判断条件是cur.next而不是cur。cur.next !=null时,cur指向是最后一个节点。

指定插入:

指定插入我们要分情况,如果越界我们会抛出异常,如果是头,尾插那直接调用方法;这里需要注意的是,如果我们需要插入第三个位置,那么应该找到第二个位置的节点,因为单向链表只能向后传递,如果找到的是第三个节点那么就无法访问到第二个节点,从而不能通过第二个节点的next去连接插入的节点。相反当找到第二个节点之后可以通过next访问第三个节点;通常我们要先连接好后面的节点再来管前面的

通过对应值删除节点:

我们要考虑链表是否为空,如果为空那么return即可,如果不为空那我们就进行删除;即将所需删除节点的前一个节点的next指向所删除节点的下一个节点(上图最后一行);因此我们首先要找到前一个节点,实现过上述方法可知想要找到当前节点那么while条件为cur.val;那么显而易见若想循环结束时cur是前一个节点,条件自然为:cur.next.val;写完后分析代码可知,这无法删除第一个节点,因此要另外写一个条件。

如果观察深入可知,起始对应值的节点并未正真删除只是之前的节点不再指向它,但是它依然存在并指向原本的下一个节点,此时我们要想真正删除,只有一个cur是不行的,因为我们一旦改变了对应值前一个节点的引用那我们就无法找到对应值的节点,因此我们的做法是再增添一个curNext去指向它,将curNext,next设置为空即可。

在上图基础上增添两行代码即可。

删除所有对应值节点:

和上个写法大致相同,有一点需要注意,此时必须将头节点值判断放在后面;因为删除节点1后,节点2又变成了头部,那么我们又需要去单独判断该头部是否需要被删除。因此我们可以先将头部后面的都整理完再回头看头部节点即可。

同时要注意判断链表是否为空。

我在刷题专栏中精选了而多道链表题并附有讲解,大家可以去检验一下自己学的如何

LinkedListd的介绍

LinkedList的定义:

链表的集合类;

LinkedList是个双向不带头非循环链表。

包含数值域,next域(指向下一个节点),prev域(指向前一个节点)

LinkedList的常见方法:

在前面已经实现过了单向链表,双向链表就会很简单,把方法过一遍就可以了;

我们实现方法时默认链表是int,这只是为了方便起见,实际上LinkedList是一个泛型类;

我们为了更好的认识LinkedList来看一下其部分源码:

LinkedList的有参构造方法:

LinkedList里的参数是Collection<? extends E>c,这里我在ArrayList有讲过:

ArrayList实现了Collection这个接口,同时我们定义的arrayList是Integer,所以满足上诉条件;简而言之就是说在实例化LinkedList时我们可以传入一个集合(已经实现过Collection接口),将这个集合类型转为LinkedList类型(LinkedList也是一种集合,即一种集合类型转为另一种集合类型)。

LinkedList的打印:

LinkedList可以用foreach打印也可以用迭代器打印,如上图,在这里不多赘述。

ArrayList和LinkedList的简单区别:

从插入,查找,修改,删除来区分

1 二者均为List接口下的两个集合,二者内部实现方面不同:ArrayList的底层是由数组实现的,通过索引访问数组元素,可以快速访问,二LinkedList的底层是由双向链表实现的,适合插入和删除元素;

2  数据访问的时间复杂度不同:ArrayList的访问时间复杂度时O(1)LinkedList时O(n)

3  空间占用,ArrayList的占用空间是连续的,但会产生空间碎片,即扩容出来的空间是多余的,而LinkedList不是连续的,但需要通过前后的引用,占用空间相对较大。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/272053.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

业财一体化是什么意思?有哪些好用的业财一体化软件?

你所在的企业是否为这些问题所困扰&#xff1f; 数据割裂&#xff1a;系统之间的数据不互通&#xff0c;财务数据与业务数据分离&#xff0c;数据统计口径不一致&#xff0c;缺乏关联性&#xff0c;管理统筹难度大。数据滞后&#xff1a;企业管理层获取数据信息的时效性低&…

绝缘电阻测试仪档位的选择技巧有哪些?这么一看就明白了!

电子绝缘电阻测试仪是电力检测领域的一款重要设备&#xff0c;他对于那些电力检测人员来说&#xff0c;是工作的设备之一&#xff0c;虽然它的使用频率相对较高&#xff0c;但是在使用绝缘电阻测试仪时&#xff0c;该如何选择合适的档位是一个关键问题。下面我们就来说说电子绝…

中国社科大与新加坡新跃社科联合培养博士—金融学和经济学差别

经济学和金融学是两个紧密联系的学科&#xff0c;但两者在研究问题上的侧重点有所不同。我在通过中国社科大与新加坡新跃社科联合培养博士项目课堂上&#xff0c;彻底分清了金融学和经济学差别。 经济学通常被归为社会科学&#xff0c;主要着眼于研究宏观上的生产、消费、以及…

谷歌大裁员,3 万员工面临被 AI 取代;网易、暴雪疑似「复合」!丨 RTE 开发者日报 Vol.113

开发者朋友们大家好&#xff1a; 这里是**「RTE 开发者日报」**&#xff0c;每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享 RTE &#xff08;Real Time Engagement&#xff09; 领域内「有话题的 新闻 」 、「有态度的 观点 」、「有意思的 数据 」、「…

Redis缓存穿透、缓存击穿、缓存雪崩介绍

一、Redis的缓存穿透 1.什么是缓存穿透&#xff1f; 缓存穿透是指&#xff1a;客户端请求的数据在缓存中和数据库中都不存在&#xff0c;这时缓存就永远不会生效&#xff0c;这些请求都打到数据库从而导致数据库压力过大。 2.出现缓存穿透的解决方案&#xff0c;以下是常用的两…

从AMI镜像恢复AWS Amazon Linux 2实例碰到的VNC服务以及Chrome浏览器无法启动的问题

文章目录 小结问题及解决VNC服务无法启动Chrome浏览器无法启动 参考 小结 将Amazon Linux 2保存为AMI (Amazon Machine Images)后&#xff0c;恢复成EC2 Instance (实例)后&#xff0c;VNC服务以及Chrome浏览器无法启动&#xff0c;进行了解决。 问题及解决 如果要将一个EC2…

Redis分布式缓存之主从哨兵分片集群

Redis主从 数据同步原理 Redis哨兵 Redis分片集群 集群伸缩&#xff1a;在集群中插入或删除某个节点 集群故障转移

HubSpot到底好不好用?

HubSpot被认为是一款强大的综合营销平台&#xff0c;然而&#xff0c;其是否适合你的业务取决于多种因素。以下是一些关于HubSpot的优点和考虑因素&#xff1a; HubSpot的优点&#xff1a; 一体化平台&#xff1a; HubSpot集成了营销、销售和服务功能&#xff0c;使得企业可以…

excel统计分析——CVM正态性检验

参考资料&#xff1a;统计推断——正态性检验&#xff08;图形方法、偏度和峰度、统计&#xff08;拟合优度&#xff09;检验&#xff09;_sm.distributions.ecdf-CSDN博客 29_张达成_从经验过程出发建立 Cramer-von Mises 统计量的性质 - 豆丁网 https://cran.r-project.org…

LeetCode 每日一题 Day 24(Hard) ||dp动态规划

1349. 参加考试的最大学生数 给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的&#xff08;不可用&#xff09;&#xff0c;就用 ‘#’ 表示&#xff1b;否则&#xff0c;用 ‘.’ 表示。 学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答…

解析d3dx9_43.dll文件,有效修复d3dx9_43.dll文件丢失

最近有小伙伴给小编反映说他的电脑老是出现d3dx9_43.dll文件丢失的问题&#xff0c;问为啥会这样&#xff1f;要怎么解决&#xff1f;那么今天小编就来给大家详细的解析这个d3dx9_43.dll文件吧&#xff0c;同时教大家如何去进行修复。 一. d3dx11_43.dll是什么文件有啥用 1.d3…

【数据库系统概论】第3章-关系数据库标准语言SQL(3)

文章目录 3.5 数据更新3.5.1 插入数据3.5.2 修改数据3.5.3 删除数据 3.6 空值的处理3.7 视图3.7.1 建立视图3.7.2 查询视图3.7.3 更新视图3.7.4 视图的作用 3.5 数据更新 3.5.1 插入数据 注意&#xff1a;插入数据时要满足表或者列的约束条件&#xff0c;否则插入失败&#x…

SpringBoot整合jwt(小白入门)

本文项目所用版本为&#xff1a; https://blog.csdn.net/weixin_39570751/article/details/133386557 代码仓库: https://gitee.com/skyblue0678/springboot-demo 目录 什么是JWT JWT依赖 写一个jwt工具类 测试一下jwt 优化&#xff1a;将过期时间配置在文件中 答疑&…

mysql根据条件修改字段

数据 sql语句 根据field2 字段情况&#xff0c;修改field1字段 update t1 tt1 set tt1.field1 ( case when tt1.field2 in (我家2) then 1111 when tt1.field2 in (你的家11) then 2222 else tt1.field2 end )结果

ros2+python,报错:`GLIBCXX_3.4.30‘ not found

在执行代码import rclpy&#xff0c;出现如下图所示报错 如报错信息所示&#xff0c;/home/shui/miniconda3/envs/ros2/bin/…/lib/libstdc.so.6中没有找到GLIBCXX_3.4.30’ 检查/home/shui/miniconda3/envs/ros2/bin/…/lib/的libstdc.so.6文件 cd /home/shui/miniconda3/e…

7. Resource database in UVM(UVM的资源数据库)

UVM集中资源数据库用于存储可配置&#xff08;configurable&#xff09;对象/object、变量/variables、虚拟接口/virtual interfaces、队列/queues、类句柄/class handles等&#xff0c;并从数据库中检索它们。这种可配置的测试平台为验证工程师提供了一定程度的自由度&#xf…

sqlmap各个命令的解释及其基本用法

各个命令的用法 -h,--help Show basic help message and exit(显示基本帮助消息并退出) -hh Show advanced help message and exit&#xff08;显示高级帮助信息并退出&#xff09; --version Show programs version number and exit&#xff08;显示程序的版本…

【Vue UI组件库】

Vue UI组件库 1 移动端常用UI组件库2 PC端常用UI组件库2.1 Element UI 1 移动端常用UI组件库 Vant&#xff1a;https://youzan.github.io/vantCube UI&#xff1a;https://didi.github.io/cube-uiMint UI&#xff1a;http://mint-ui.github.io 2 PC端常用UI组件库 Element U…

带你学C语言~指针(3)

目录 ✍0.前言 &#x1f680;1.字符指针变量 &#x1f685;2.数组指针变量 &#x1f431;‍&#x1f3cd;2.1.数组指针变量是什么 &#x1f431;‍&#x1f3cd;2.2数组指针变量怎么初始化 &#x1f6a2;3.二维数组传参的本质 &#x1f680;4.函数指针变量 ✈4.1函数指…