数据结构—LinkedList与链表

目录

一、链表

1. 链表的概念及结构

1. 单向或者双向

2. 带头或者不带头

3. 循环或者非循环

二.LinkedList的使用

 1.LinkedList概念及结构

2. LinkedList的构造

3. LinkedList的方法

三. ArrayList和LinkedList的区别


 

一、链表

1. 链表的概念及结构

        链表是一种 物理存储结构上非连续存储结构,数据元素的 逻辑顺序是通过链表中的 引用链接次序实现的
 
 
dac0ee7bff204f868a4a0462496de315.png

 

data表示数据;

next表示指针,它总是指向自身的下一个结点,对于只有一个结点的存在,这个next指针则永远指向自身,对于一个链表的尾部结点,next永远指向开头。 

ab487738a81144ac802fca2bce49559f.png

 

注意:
  1. 从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续
  2. 现实中的结点一般都是从堆上申请出来的
  3. 从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续
 
 
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:
 

1. 单向或者双向

 
48c0b21809f04ce88e79662085161bf6.png
 

2. 带头或者不带头

 
90bd97ac50d242e9a9da20300cef1b4f.png
 

3. 循环或者非循环

 
                 55eef4818cb44b7f90bce7d22df2e856.png
 

二.LinkedList的使用

 1.LinkedList概念及结构

         LinkedList的底层是双向链表结构,由于链表没有将元素存储在连续的空间中,元素存储在单独的节点中,然后通过引用将节点连接起来了,因此在在任意位置插入或者删除元素时,不需要搬移元素,效率比较高。

9f0517b501ff45368b107a2e98cd3629.png

        在集合框架中,LinkedList也实现了List接口
【说明】
 

1. LinkedList实现了List接口

2. LinkedList的底层使用了双向链表

3. LinkedList没有实现RandomAccess接口,因此LinkedList不支持随机访问

4. LinkedList的任意位置插入和删除元素时效率比较高,时间复杂度为O(1)

5. LinkedList比较适合任意位置插入的场景

2. LinkedList的构造

        7de09ddbcc5b4c4a826a9ab424ccaff3.png

代码:

public static void main(String[] args) {
// 构造一个空的LinkedList
    List<Integer> list1 = new LinkedList<>();
    List<String> list2 = new java.util.ArrayList<>();
    list2.add("JavaSE");
    list2.add("JavaWeb");
    list2.add("JavaEE");
// 使用ArrayList构造LinkedList
    List<String> list3 = new LinkedList<>(list2);
}

3. LinkedList的方法

db65c908fce7489abc9ac1c252d026ac.png

代码: 

public static void main(String[] args) {
    LinkedList<Integer> list = new LinkedList<>();
    list.add(1); // add(elem): 表示尾插
    list.add(2);
    list.add(3);
    list.add(4);
    list.add(5);
    list.add(6);
    list.add(7);
    System.out.println(list.size());
    System.out.println(list);
// 在起始位置插入0
    list.add(0, 0); // add(index, elem): 在index位置插入元素elem
    System.out.println(list);
    list.remove(); // remove(): 删除第一个元素,内部调用的是removeFirst()
    list.removeFirst(); // removeFirst(): 删除第一个元素
    list.removeLast(); // removeLast(): 删除最后元素
    list.remove(1); // remove(index): 删除index位置的元素
    System.out.println(list);
// contains(elem): 检测elem元素是否存在,如果存在返回true,否则返回false
    if(!list.contains(1)){
        list.add(0, 1);
}
    list.add(1);
    System.out.println(list);
    System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
    System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
    int elem = list.get(0); // get(index): 获取指定位置元素
    list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
    System.out.println(list);
// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
    List<Integer> copy = list.subList(0, 3); 
    System.out.println(list);
    System.out.println(copy);
    list.clear(); // 将list中元素清空
    System.out.println(list.size());
}

三. ArrayList和LinkedList的区别

        由于 ArrayList其底层是一段连续空间,当 在ArrayList 任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后 搬移,时间复杂度为 O(n),效率比较低,因此 ArrayList 不适合做任意位置插入和删除比较多的场景。因此java 集合中又引入了LinkedList,即链表结构, LinkedList 适合做任意位置插入和删除比较多的场景
 
 

ce21d264a77d4fb1a3c6425bc086d12f.png

 

 

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

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

相关文章

开启创造力之门:掌握Vue中Slot插槽的使用技巧与灵感

&#x1f3ac; 江城开朗的豌豆&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 &#x1f4dd; 个人网站 :《 江城开朗的豌豆&#x1fadb; 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! 目录 ⭐ 专栏简介 &#x1f4d8; 文章引言 一、s…

【Ubuntu】设置永不息屏与安装 dconf-editor

方式一、GUI界面进行设置 No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 20.04.6 LTS Release: 20.04 Codename: focal打开 Ubuntu 桌面环境的设置菜单。你可以通过点击屏幕右上角的系统菜单&#xff0c;然后选择设置。在设置菜单中&#xff0c;…

弱类型和强类型自定义UDAF函数

目录 使用自带的avg函数弱类型自定义UDAF函数(AVG)强类型自定义UDAF函数(AVG) 弱类型&#xff1a;3.x过期 2.x有 强类型&#xff1a;3.x 2.x没有 使用自带的avg函数 import org.apache.spark.rdd.RDD import org.apache.spark.sql.{DataFrame, SparkSession}object UserDefine…

GD32_ADC采样+DMA多通道扫描传输

GD32_ADC采样DMA多通道扫描传输 文章目录 GD32_ADC采样DMA多通道扫描传输前言一、资源介绍二、原理1.ADC连续扫描模式2.DMA传输3.ADC内部通道 三、配置1.ADC配置2.DMA配置3.注意事项 四、计算1.分压转换2.数据转换 前言 <1>、硬件平台&#xff1a;可运行软件程序的GD32单…

【计算思维】少儿编程蓝桥杯青少组计算思维题考试真题及解析B

STEMA考试-计算思维-U8级(样题) 1.浩浩的左⼿边是&#xff08; &#xff09;。 A.兰兰 B.⻉⻉ C.⻘⻘ D.浩浩 2.2时30分&#xff0c;钟⾯上时针和分针形成的⻆是什么⻆&#xff1f;&#xff08; &#xff09; A.钝⻆ B.锐⻆ C.直⻆ D.平⻆ 3.下⾯是⼀年级同学最喜欢的《⻄游记》…

人工智能基础_机器学习037_多项式回归升维实战4_使用随机梯度下降模型_对天猫双十一销量数据进行预测_拟合---人工智能工作笔记0077

上一节我们使用线性回归模型最终拟合了双十一天猫销量数据,升维后的数据. 我们使用SGDRegressor的时候,随机梯度下降的时候,发现有问题, 对吧,怎么都不能拟合我们看看怎么回事现在 可以看到上面是之前的代码 上面是对数据的准备 这里我们还是修改,使用 poly=PolynomialFeatur…

nodejs+vue电影在线预定与管理系统的设计与实现-微信小程序-安卓-python-PHP-计算机毕业设计

通过软件的需求分析已经获得了系统的基本功能需求&#xff0c;根据需求&#xff0c;将电影在线预定与管理系统功能模块主要分为管理员模块。 我国各行各业的发展在信息化浪潮的推动下也在不断进步&#xff0c;尤其是电影产业&#xff0c;在人们生活水平提高的同时&#xff0c;从…

旅拍摄影技巧澳大利亚、韩国旅行攻略

欢迎关注「苏南下」 在这里分享我的旅行和影像创作心得 刚刚在腾讯内部做了一场摄影分享课&#xff1a; 《旅拍摄影技巧&澳大利亚、韩国旅行攻略》 分享了早前去两个国家的一些旅行见闻和摄影心得。我发现&#xff1a;把自己学会的东西整理出来&#xff0c;再告诉给别人这件…

探索人工智能领域——每日30个名词详解【day3】

目录 前言 正文 总结 &#x1f308;嗨&#xff01;我是Filotimo__&#x1f308;。很高兴与大家相识&#xff0c;希望我的博客能对你有所帮助。 &#x1f4a1;本文由Filotimo__✍️原创&#xff0c;首发于CSDN&#x1f4da;。 &#x1f4e3;如需转载&#xff0c;请事先与我联系以…

c语言从入门到实战——数组指针与函数指针

数组指针与函数指针 前言1. 字符指针变量2. 数组指针变量2.1 数组指针变量是什么&#xff1f;2.2 数组指针变量怎么初始化? 3. 二维数组传参的本质4. 函数指针变量4.1 函数指针变量的创建4.2 函数指针变量的使用4.3 两段有趣的代码4.3.1 typedef关键字 5. 函数指针数组6. 转移…

【华为HCIP | 华为数通工程师】ISIS 高频题(1)

个人名片&#xff1a; &#x1f43c;作者简介&#xff1a;一名大三在校生&#xff0c;喜欢AI编程&#x1f38b; &#x1f43b;‍❄️个人主页&#x1f947;&#xff1a;落798. &#x1f43c;个人WeChat&#xff1a;hmmwx53 &#x1f54a;️系列专栏&#xff1a;&#x1f5bc;️…

机器人导航+OPENCV透视变换示例代码

透视变换又称四点变换&#xff0c;所以不能用于5边形这样的图形变换&#xff0c;不是真正的透视变换&#xff0c;但是这个方法可以把机器人看到的图像转换为俯视图&#xff0c;这样就可以建立地图&#xff0c;要不然怎么建立地图呢。 void CrelaxMyFriendDlg::OnBnClickedOk()…

【JavaSE语法】类和对象(二)

六、 封装 6.1 封装的概念 面向对象程序三大特性&#xff1a;封装、继承、多态。而类和对象阶段&#xff0c;主要研究的就是封装特性。 封装&#xff1a;将数据和操作数据的方法进行有机结合&#xff0c;隐藏对象的属性和实现细节&#xff0c;仅对外公开接口来和对象进行交互…

PCL 提取点云边界轮廓-AC方法、平面轮廓

一、概述 PCL点云边界特征检测 &#xff08;附完整代码 C&#xff09;_pcl计算点云特征值_McQueen_LT的博客-CSDN博客 在点云的边界特征检测&#xff08;网格模型的边界特征检测已经是一个确定性问题了&#xff0c;见 网格模型边界检测&#xff09;方面&#xff0c;PCL中有一…

【C++初阶】STL详解(一)string类

本专栏内容为&#xff1a;C学习专栏&#xff0c;分为初阶和进阶两部分。 通过本专栏的深入学习&#xff0c;你可以了解并掌握C。 &#x1f493;博主csdn个人主页&#xff1a;小小unicorn ⏩专栏分类&#xff1a;C &#x1f69a;代码仓库&#xff1a;小小unicorn的代码仓库&…

【Hello Go】Go语言基础类型

Go语言基础类型 基础类型命名变量变量声明变量初始化变量赋值匿名变量 常量字面常量常量定义iota枚举 基础数据类型分类 fmt包的标准输入输出格式说明输入类型转换类型取别名 基础类型 命名 Go语言中的命名遵循下面的几个规则 必须以字母或者是下划线开头不能使用Go语言中的…

Django——模板层、模型层

模板层 一. 模版语法 {{ }}: 变量相关 {% %}: 逻辑相关 1. 注释是代码的母亲 {# ... #} 2. 基本数据类型传值 int1 123 float1 11.11 str1 我也想奔现 bool1 True list1 [小红, 姗姗, 花花, 茹茹] tuple1 (111, 222, 333, 444) dict1 {username: jason, age: 18, i…

单片机的冷启动、热启动、复位

一文看懂STC单片机冷启动和复位有什么区别-电子发烧友网 单片机的冷启动、热启动和复位是不同的启动或重置方式&#xff0c;它们在系统状态和初始化方面有所不同&#xff1a; 1.冷启动&#xff08;Cold Start&#xff09;&#xff1a; 定义&#xff1a; 冷启动是指系统从完全关…

第14届蓝桥杯青少组python试题解析:22年10月选拔赛

选择题 T1. 执行print (5%3) 语句后&#xff0c;输出的结果是 ( ) 0 1 2 3 T2. 以下选项中&#xff0c;哪一个是乘法运算符?&#xff08;&#xff09; % // * ** T3. 已知x3&#xff0c;求x//2x**2的运算结果? 7.5 10 8 10.5 T4. 以下选项中&#xff0c;对下面程序的打印…

Unity地面交互效果目录

大家好&#xff0c;我是阿赵。   之前写了几篇关于地形交互、地面轨迹、脚印效果实现的博文。虽然写的篇数不多&#xff0c;但里面也包含了不少基础知识&#xff0c;比如局部UV采样、法线动态混合、曲面细分等知识&#xff0c;这些都是可以和别的效果组合在一起&#xff0c;做…