Java

技术体系来充实自己的技术栈的同学。

与此同时本专栏的所有文章也都会准备充足的代码示例和完善的知识点梳理因此也十分适合零基础的小白和要准备工作面试的同学学习。

当然我也会在必要的时候进行相关技术深度的技术解读相信即使是拥有多年

Java

作为一个双向链表提供了高效的插入和删除操作特别适用于频繁进行元素增删的场景。

对于很多开发者而言深入理解

LinkedList

的特性和工作原理是提高代码性能和优化数据处理逻辑的关键。

本文将对

LinkedList

进行全面的介绍和解析帮助读者掌握其使用方法、内部原理以及源码实现。

文章目录

的元素在内存中不是连续存放的。

每个元素称为节点都包含两部分数据一部分是存储的数据另一部分是指向前一个节点和后一个节点的链接指针。

LinkedList

的优点在于插入和删除元素时效率很高。

因为链表的数据结构使得它只需要修改前后节点的指针即可而不需要像

ArrayList

的随机访问效率不高每次查找某个元素都需要从头开始遍历链表直到找到目标元素。

这使得

LinkedList

接口这意味着它还可以被当作队列Queue、双端队列Deque使用提供了更加丰富的方法如

addFirst(),

也是非线程安全的。

如果在多线程环境中使用需要外部同步或者考虑使用

java.util.concurrent

由于其结构的特点适合于数据量不大但插入和删除操作频繁的场景而不适合大量的随机访问操作。

2、LinkedList

是基于链表数据结构实现的它包含一系列的节点Node每个节点包括三个部分前一个节点的引用previous储存的元素data和下一个节点的引用next。

这种数据结构支持高效的元素插入和删除操作。

public

AbstractSequentialListEimplements

ListE,

构造一个包含指定集合元素的链表这些元素按集合的迭代器返回的顺序排列。

**

param

的插入的实现并不复杂其插入式主要会有两种场景一种是在链表的末尾插入另一种是在指定节点之前插入一个新节点二者的实现都是通过创建一个新节点并更新其前驱和后继节点的引用唯一的区别就是linkBefore

linkAfter

AbstractSequentialListEimplements

ListE,

在链表末尾链接一个新的节点linkLast(e);return

true;}/***

size)linkLast(element);elselinkBefore(element,

node(index));}/***

AbstractSequentialListEimplements

ListE,

方法即通过更新前驱和后继节点的引用移除指定节点并返回其存储的元素实现的。

public

AbstractSequentialListEimplements

ListE,

{checkElementIndex(index);return

param

AbstractSequentialListEimplements

ListE,

检查索引是否在范围内checkElementIndex(index);//

node(index);//

检查是否发生并发修改checkForComodification();//

lastReturned

的查询即获取指定索引处的元素。

它的实现同前面的其他方法获取索引处元素一样依赖

node(int

AbstractSequentialListEimplements

ListE,

{checkElementIndex(index);return

param

作为一个双端队列Deque使用支持在队列的头部和尾部进行插入和删除操作。

下面是对

LinkedList

方法将元素添加到链表的尾部poll()获取并移除此队列的头部如果队列为空则返回

unlinkFirst(NodeE

方法移除并返回链表的第一个元素remove()获取并移除此队列的头部如果队列为空则抛出

unlinkFirst(NodeE

NoSuchElementExceptionpeek()获取但不移除此队列的头部如果队列为空则返回

first.item如果链表为空返回

null。

element()获取但不移除此队列的头部如果队列为空则抛出

NoSuchElementException。

实现返回链表的第一个元素

first.item如果链表为空抛出

AbstractSequentialListEimplements

ListE,

AbstractSequentialListEimplements

ListE,

队列Queue也是一种操作受限的线性表只允许在表的一端进行插入而在表的另一端进行删除。

向队列中插入元素称为入队或进队删除元素称为出队或离队。

这和我们日常生活中的排队是一致的最早排队的也是最早离队的。

其操作的特性是先进先出First

First

FIFO故又称为先进先出的线性表。

基本上一个队列就是一个先入先出FIFO的数据结构

在Java

是基于动态数组实现的支持随机访问按索引访问元素非常快时间复杂度为

是基于双向链表实现的不支持高效的随机访问按索引访问元素需要从头或尾开始遍历时间复杂度为

的插入和删除操作需要进行数组元素的移动除非插入和删除操作在列表末尾进行所以插入和删除元素的时间复杂度为

的插入和删除操作只需要改变节点的引用所以在列表中间插入和删除元素的时间复杂度为

O(1)前提是已经获取到了要插入位置的节点。

内存占用ArrayList

的内存占用相对较低因为它只需要存储元素数据和数组的引用。

LinkedList

更适合随机访问场景LinkedList

指针改为指向前一个节点。

由于节点没有引用其前一个节点因此必须事先存储其前一个节点。

在更改引用之前还需要存储后一个节点。

最后返回新的头引用。

class

将当前节点的下一个节点指向前一个节点完成反转curr.next

prev;//

在索引1的位置添加多个元素removeAll(Collection?

LinkedListString

list.removeAll(Collections.singleton(b));

移除所有

list.retainAll(Arrays.asList(a,

b));

list.containsAll(Arrays.asList(a,

b));

计算1在链表中出现的次数disjoint(Collection?

c1,