当前位置：首页 > 编程日记 > 正文

什么是LinkedList？什么时候使用它呢？Java LinkedList结构、用法及源码解析

编程日记 2024-01-28 20:30:00

前言：我们学习java时都知道ArrayList实现List接口，LinkedList也实现List接口，但我们平时用的时候LinkedList却很少被用到。那么，LinkedList什么时候该用到呢？内部又是如何实现的呢？本文对此进行详细说明，希望能够助君更上一层楼。

我们在使用ArrayList（动态数组）时有个明显的缺点，就是当容量接近满值的时候，会进行扩容，JDK默认扩容为1.5倍，那么，当数据量极大时，就会造成内存空间的大量浪费！

能否用到多少就申请多少内存？

`没错LinkedList（链表）可以办到这一点。`

相信计算机专业的同学一定在数据结构课上学到过链表这种数据结构，链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的，内存结构如下：
在这里插入图片描述

上图可以看出，我们的LinkedList每一个节点都有一个地址空间，用来存储我们下一个节点的地址，虽然地址并不连续，但数据的存储并不会受到任何影响。

`在真正的设计中，为了查询、添加、删除的方便，我们的链表还需要有头尾指针以及前驱指针`

那么，让我们归结一下，链表首先需要一个头指针，指向头结点。一个尾节点，存储尾节点。然后每个节点都需要一个存储它的内部元素的属性，一个指针指向他的前驱，一个节点指向他的后继。

接着，我们先写一下节点的类 👇

private static class Node<E> {E element;Node<E> prev;Node<E> next;public Node(Node<E> prev, E element, Node<E> next) {this.prev = prev;this.element = element;this.next = next;}

我们的节点是LinkedList的属性，所以将节点放入我们的LinkedList中，如下👇

public class LinkedList<E> extends AbstractList<E> {private Node<E> first;private Node<E> last;private static class Node<E> {E element;Node<E> prev;Node<E> next;public Node(Node<E> prev, E element, Node<E> next) {this.prev = prev;this.element = element;this.next = next;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();if (prev != null) {sb.append(prev.element);} else {sb.append("null");}sb.append("_").append(element).append("_");if (next != null) {sb.append(next.element);} else {sb.append("null");}return sb.toString();}}@Overridepublic void clear() {size = 0;first = null;last = null;}@Overridepublic E get(int index) {return node(index).element;}@Overridepublic E set(int index, E element) {Node<E> node = node(index);E old = node.element;node.element = element;return old;}@Overridepublic void add(int index, E element) {rangeCheckForAdd(index);// size == 0// index == 0if (index == size) { // 往最后面添加元素Node<E> oldLast = last;last = new Node<>(oldLast, element, null);if (oldLast == null) { // 这是链表添加的第一个元素first = last;} else {oldLast.next = last;}} else {Node<E> next = node(index); Node<E> prev = next.prev; Node<E> node = new Node<>(prev, element, next);next.prev = node;if (prev == null) { // index == 0first = node;} else {prev.next = node;}}size++;}@Overridepublic E remove(int index) {rangeCheck(index);Node<E> node = node(index);Node<E> prev = node.prev;Node<E> next = node.next;if (prev == null) { // index == 0first = next;} else {prev.next = next;}if (next == null) { // index == size - 1last = prev;} else {next.prev = prev;}size--;return node.element;}@Overridepublic int indexOf(E element) {if (element == null) {Node<E> node = first;for (int i = 0; i < size; i++) {if (node.element == null) return i;node = node.next;}} else {Node<E> node = first;for (int i = 0; i < size; i++) {if (element.equals(node.element)) return i;node = node.next;}}return ELEMENT_NOT_FOUND;}/*** 获取index位置对应的节点对象* @param index* @return*/private Node<E> node(int index) {rangeCheck(index);if (index < (size >> 1)) {Node<E> node = first;for (int i = 0; i < index; i++) {node = node.next;}return node;} else {Node<E> node = last;for (int i = size - 1; i > index; i--) {node = node.prev;}return node;}}@Overridepublic String toString() {StringBuilder string = new StringBuilder();string.append("size=").append(size).append(", [");Node<E> node = first;for (int i = 0; i < size; i++) {if (i != 0) {string.append(", ");}string.append(node);node = node.next;}string.append("]");return string.toString();}

相比较我们的ArrayList，LinkedList是否有什么特别的优点吗？

我们的每种数据结构设计出来都有其特别的使用之处。总结一下：

数组（ArrayList）的随机访问速度非常快，但是指定位置添加、删除操作时需要将后续元素全部顺移。
LinkedList则恰恰相反，我们在使用链表做指定位置的添加删除操作时，所需的操作非常少，但随机访问速度却非常慢。

基于这些属性，我们在使用中该如何选择呢？

如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择
如果频繁在头部进行添加、删除操作，建议选择使用双向链表
如果有频繁的（在任意位置）添加、删除操作，建议选择使用双向链表
如果有频繁的查询操作（随机访问操作），建议选择使用动态数组

所以，我们在应聘岗位的时候，会有一则`能够在不同情境使用不同的数据结构`

选择最合适的数据结构进行使用是非常重要的！

以上！！

https://www.dkcj.cn/info/990.html

Myeclipse中修改项目默认编码还是乱码？一步永久解决！

在myeclipse中修改默认编码后发现项目还是乱码？ 点击Windows选择Preferences 如下图👇 点击General->Content Types->text->选择你要修改的文件类型->选择你要修改的编码格式 （比如我这里是jsp页面乱码）如下图&#…

编程日记2024/01/28 20:00:00

Myeclipse中项目没有代码错误提示，jsp页面无编译迹象？如何解决

在使用Myeclipse开发项目时，发现jsp页面中嵌入的java代码没有编译的迹象，错误的get方法没有报错，没有报错信息我们如何知道我们开发的内容是正确的呢？ 接下来就演示一下如何解决👉 第一步，点击Project 选择…

编程日记2024/01/28 19:30:00

伍六七带你学算法入门篇 ——最大子序和

力扣 53. 最大子序和难度简单给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大&#xf…

编程日记2024/01/28 19:00:00

伍六七带你学算法入门篇——最后一个单词的长度

难度简单给定一个仅包含大小写字母和空格 ’ ’ 的字符串 s，返回其最后一个单词的长度。如果字符串从左向右滚动显示，那么最后一个单词就是最后出现的单词。如果不存在最后一个单词，请返回 0 。说明：一个单词是指仅由字母组…

编程日记2024/01/28 18:30:00

伍六七带你学算法动态规划 ——不同路径

力扣 62. 不同路径难度中等一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不…

编程日记2024/01/28 18:00:00

但是，我们常常会切断这个链条，只记住最终的结论，忘记了支撑结论的一系列事实、论据、逻辑，从而，任由这个落单的、孤零零的「结论」不断飘摇，不断泛化和极端化。像我在之前的文章里，以及智识营里，都提出过一些比较颠覆性的观点，就经常能看到「难以置信」「感觉自己的世界被颠覆了」「我需要时间去理解和接受」的留言……大脑难以记住复杂的事实，所以，我们会倾向于把事实「压缩」成一个高密度的观点。例如：当你阅读我的文章时，一定不要只记住我给出的「根本原因」和「做法」，也要同时记住「这些原因是怎么来的」「这些做法背后的原理」。

编程日记2024/01/28 17:48:05

伍六七带你学算法——被忽视的数学公式

中学时候学习那么多的数学，却没有人告诉我们这些数学公式我们以后会用到哪里？疑惑了十好几年，直到，你进入it行业，它的舞台来了！ 在力扣上有一道中度难度的题，题目是这样的👇 &#…

编程日记2024/01/28 17:30:00

设置linux初始root密码

简单一步设置linux第一个root密码 sudo passwd root #输入当前账户密码 #输入准备设置的root密码 #确认密码如下所示：👇

编程日记2024/01/28 17:00:00

伍六七带你学算法——栈的使用

大家都知道栈这种数据结构，它有非常多的应用场景。但如果我们不经常接触这些应用场景的话，就可能不太熟悉栈的用法。目录smd1.栈的创建和使用JAVA Stack类：2.栈的实际应用示范解题如下👇1.栈的创建和使用 JAVA Stack类&#xff…

编程日记2024/01/28 16:30:00

最优的去重处理——HashSet去重

算法与数据结构是密不可分的，我们使用不同的数据结构和算法的组合就是我们解决问题的答案。本篇我将就HashSet的特性和使用进行介绍。 HashSet有哪些特性呢？ HashSet继承了Set接口，Set接口有如下特性： 1.元素的无序性 &#xff…

编程日记2024/01/28 16:00:00

什么是原码、反码、补码？什么是按位与？范围数字按位与！

前言：学过计算机基础的大家都知道什么是二进制，什么是“与”运算，这里先给大家复习一下。举一个简单的例子： 5的二进制表示是0101（补齐4位） 7的二进制表示是0111（补齐4位） 那么5&a…

编程日记2024/01/28 15:30:00

不占用多余空间实现值的交换——异或运算

首先什么是异或运算？ ^规则： 0 ^ x x x ^ x 0那么 a 与 b 交换值如何做呢？？？三行代码👇 a a ^ b; b a ^ b; a a ^ b;第一步 a a ^ b 第二步 b （a ^ b）^ b a ^ 0 a …

编程日记2024/01/28 15:00:00

通用解题法——回溯算法（理解+练习）

积累算法经验，积累解题方法——回溯算法，你必须要掌握的解题方法！ 什么是回溯算法呢？ 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时&#xff…

编程日记2024/01/28 14:30:00

linux vi编辑器中的复制粘贴快捷键

在使用vi有时会想直接复制一行数据，然后粘贴若干行进行修改复制一行数据的方法把光标放到要复制的一行前面，然后按两下yy字母键 yy # 复制光标所在的那一行然后把光标放到要复制到的地方去，按键盘的p字母键 p # 将已复制的数据粘贴到…

编程日记2024/01/28 14:00:00

二进制与十进制的小数位怎么转？

二进制转十进制 (0.001)2 ->十进制从小数点后第一位开始，依次乘2的-1次方 02-1 02-2 12-3 这里已经把上面的小数点后三位全部乘完然后将结果相加，0 0 0.125 0.125 所以，(0.001)2 的十进制为0.125 十进制转二进制 0.125 -> 二进…

编程日记2024/01/28 13:30:00

作为一个java程序员，常用的linux命令（越攒越多）

本篇记录我在工作中不断遇到的常用的linux命令，并进行总结，时常更新！ 1. 升级服务时先停止服务，然后进行替换 linux中杀进程时候，如果你是知道它所占用的端口号的话，可以通过 netstat -tunpl | grep 端口…

编程日记2024/01/28 13:00:00

使用JPA进行update操作时，报org.springframework.beans.factory.BeanCreationException: Error creating bean with

使用JPA进行update操作时，报org.springframework.beans.factory.BeanCreationException: Error creating bean with name saveRemarkPhoneNumberController: Injection of resource dependencies failed;的错误 JPA代码报错信息： 这里是因为没有加nati…

编程日记2024/01/28 12:30:00

使用JPA进行Update操作 @Query注解的用法，JPL

使用jpa进行update操作有两种，第一种就是先查询，set，再进行save更新。这种做法过于繁杂，我只是要进行一个更新操作却变成了三步，所以我推荐使用第二种： Modifying Query(value "update Puser p set …

编程日记2024/01/28 12:00:00

Excel如何设置单元格行高，办公入门

在使用Excel做设计文档时，遇到一个问题，一组报文放入一个单元格，但因为只显示一行，我的信息就成了下面这个样子👇 但里面的数据其实是这样的👇 如何让它能够全部显示呢？ 选中这个单元格&#x…

编程日记2024/01/28 11:30:00

通过正则表达式校验手机号码，拿走即用！

校验手机号码 2021/01/06更新，电信新增了191号段 1. 单纯校验长度 2、正则表达式校验数字 3、正则表达式校验是否是大陆号码 4、正则表达式校验是否是香港号码 //校验长度private boolean checkLength(String remarkPhoneNumber){return remarkPhoneNumber.leng…

编程日记2024/01/28 11:00:00

rancher部署项目Validation failed in API: Deployment.apps“”must be no more than 63 characters问题原因及解决方法

Validation failed in API: Deployment.apps “xxxxxxxxxx-x x x x x x x x x” is invalid: [metadata.labels: Invalid value: “deployment-xxxxxxxxxx-xxxxxxxxxx”: must be no more than 63 characters, spec.selector.matchLabels: Invalid value: “deployment-xxxxxxx…

编程日记2024/01/28 10:30:00

我们在使用ArrayList（动态数组）时有个明显的缺点，就是当容量接近满值的时候，会进行扩容，JDK默认扩容为1.5倍，那么，当数据量极大时，就会造成内存空间的大量浪费！

能否用到多少就申请多少内存？

没错LinkedList（链表）可以办到这一点。

上图可以看出，我们的LinkedList每一个节点都有一个地址空间，用来存储我们下一个节点的地址，虽然地址并不连续，但数据的存储并不会受到任何影响。

在真正的设计中，为了查询、添加、删除的方便，我们的链表还需要有头尾指针以及前驱指针

那么，让我们归结一下，链表首先需要一个头指针，指向头结点。一个尾节点，存储尾节点。然后每个节点都需要一个存储它的内部元素的属性，一个指针指向他的前驱，一个节点指向他的后继。

接着，我们先写一下节点的类 👇

我们的节点是LinkedList的属性，所以将节点放入我们的LinkedList中，如下👇

我们的每种数据结构设计出来都有其特别的使用之处。总结一下：

数组（ArrayList）的随机访问速度非常快，但是指定位置添加、删除操作时需要将后续元素全部顺移。

基于这些属性，我们在使用中该如何选择呢？

如果频繁在尾部进行添加、删除操作，动态数组、双向链表均可选择

如果有频繁的（在任意位置）添加、删除操作，建议选择使用双向链表

所以，我们在应聘岗位的时候，会有一则能够在不同情境使用不同的数据结构

选择最合适的数据结构进行使用是非常重要的！

相关文章：

`没错LinkedList（链表）可以办到这一点。`

`在真正的设计中，为了查询、添加、删除的方便，我们的链表还需要有头尾指针以及前驱指针`

所以，我们在应聘岗位的时候，会有一则`能够在不同情境使用不同的数据结构`