源码角度简单介绍LinkedList

LinkedList是一种常见的数据结构，但是大多数开发者并不了解其底层实现原理，以至于存在很多误解，在这篇文章中，将带大家一块深入剖析LinkedList的源码，并为你揭露它们背后的真相。首先想几个问题，例如：

  1. LinkedList 的底层是基于什么数据结构实现的？
  2. LinkedList 的插入和删除操作时间复杂度是否都是 O(1) ?
  3. LinkedList 和 ArrayList 相比，哪种结构存储数据的时候更占内存？
  4. LinkedList 真的不支持随机访问吗？
  5. LinkedList 是线程安全的吗？

接下来一块分析一下 LinkedLis t的源码，看完 LinkedList 源码之后，可以轻松解答上面几个问题 

简介 

LinkedList底层是基于双向链表实现的，内部有三个属性，size用来存储元素个数，first指向链表头节点，last指向链表尾节点。

public class LinkedList<E>extends AbstractSequentialList<E>implements List<E>, Deque<E>, Cloneable, java.io.Serializable {// 元素个数transient int size = 0;// 头节点transient Node<E> first;// 尾节点transient Node<E> last;
}

 头尾节点都是由Node节点组成，Node节点表示双向链表，内部结构如下：

private static class Node<E> {// 存储元素数据E item;// 后继节点，指向下一个元素LinkedList.Node<E> next;// 前驱节点，指向上一个元素LinkedList.Node<E> prev;// 构造函数Node(LinkedList.Node<E> prev, E element, LinkedList.Node<E> next) {this.item = element;this.next = next;this.prev = prev;}
}

再看一下LinkedList的继承类图，还是很清晰的：

 LinkedList实现了List接口，提供了集合操作的常用方法，当然也包含随机访问的方法，只不过没有相ArrayList那样实现RandomAccess接口，LinkedList提供的随机访问的方法时间复杂度并不是常量级别的。

public interface List<E> extends Collection<E> {// 查询方法int size();boolean isEmpty();boolean contains(Object o);Iterator<E> iterator();Object[] toArray();<T> T[] toArray(T[] a);// 修改方法boolean add(E e);boolean remove(Object o);// 批量修改方法boolean containsAll(Collection<?> c);boolean addAll(Collection<? extends E> c);boolean addAll(int index, Collection<? extends E> c);boolean removeAll(Collection<?> c);boolean retainAll(Collection<?> c);default void replaceAll(UnaryOperator<E> operator) {}default void sort(Comparator<? super E> c) {}void clear();// 比较方法boolean equals(Object o);int hashCode();// 随机访问方法E get(int index);E set(int index, E element);void add(int index, E element);E remove(int index);// 搜索方法int indexOf(Object o);int lastIndexOf(Object o);// 迭代方法ListIterator<E> listIterator();ListIterator<E> listIterator(int index);java.util.List<E> subList(int fromIndex, int toIndex);
}

LinkedList还实现了Deque接口，Deque是 double ended queue 的缩写，读音是 ['dek] ，读错就尴尬了。 Deque是双端队列，可以在头尾进行插入和删除操作，兼具栈和队列的性质。 内部结构如下：

public interface Deque<E> extends Queue<E> {// 基础方法void addFirst(E e);void addLast(E e);boolean offerFirst(E e);boolean offerLast(E e);E removeFirst();E removeLast();E pollFirst();E pollLast();E getFirst();E getLast();E peekFirst();E peekLast();boolean removeFirstOccurrence(Object o);boolean removeLastOccurrence(Object o);// 队列方法boolean add(E e);boolean offer(E e);E remove();E poll();E element();E peek();// 栈方法void push(E e);E pop();// 集合方法boolean remove(Object o);boolean contains(Object o);public int size();Iterator<E> iterator();Iterator<E> descendingIterator();
}

Deque为什么提供了这么多增删查的方法？为了满足不同的使用场景。比如Deque队列已经满了，再往里面添加元素，addFirst() 方法会抛出异常，offerFirst() 方法会返回false

初始化

LinkedList只有一个构造方法，无参构造方法，并不能像ArrayList那样指定长度。

List<Integer> list = new LinkedList<>();
//构造方法
public LinkedList() {
}

添加元素

添加元素的方法根据位置区分，共有三种，在头部添加、在尾部添加和在任意位置添加。

在头部添加 addFirst/push offerFirst 在尾部添加 addLast add/offer/offerLast 在任意位置添加 add(index, e)

先看一下使用的最多的add(e)方法底层实现：

// 添加元素
public boolean add(E e) {// 在末尾添加元素linkLast(e);return true;
}// 在末尾添加元素
void linkLast(E e) {// 1. 获取尾节点final LinkedList.Node<E> l = last;// 2. 初始化新节点final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);// 3. 追加到末尾last = newNode;if (l == null) {first = newNode;} else {l.next = newNode;}size++;modCount++;
}

可以看到add(e

// 添加元素
public void push(E e) {// 在头部添加元素addFirst(e);
}// 在头部添加元素
public void addFirst(E e) {linkFirst(e);
}// 在头部添加元素，底层私有实现
private void linkFirst(E e) {// 1. 获取头节点final LinkedList.Node<E> f = first;// 2. 初始化新节点final LinkedList.Node<E> newNode = new LinkedList.Node<>(null, e, f);// 3. 追加到头部first = newNode;if (f == null) {last = newNode;} else {f.prev = newNode;}size++;modCount++;
}

)方法是尾部添加元素，再看一个从头部添加元素的push()。

最后看一个在任意位置添加到方法add(index, e)的底层实现：

// 在下标index位置添加元素
public void add(int index, E element) {// 检查下标是否越界checkPositionIndex(index);// 如果index等于链表的最后一个元素，则添加到末尾if (index == size) {linkLast(element);} else {// 添加到指定位置前面（先找到index位置的元素）linkBefore(element, node(index));}
}// 在当前元素前面添加新元素
void linkBefore(E e, LinkedList.Node<E> succ) {final LinkedList.Node<E> pred = succ.prev;// 创建新节点，并将新节点插入到当前节点之前final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ);succ.prev = newNode;if (pred == null) {first = newNode;} else {pred.next = newNode;}size++;modCount++;
}

再看一下检查下标是否越界的方法底层实现：

/ 检查下标是否越界
private void checkElementIndex(int index) {if (!isElementIndex(index)) {throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
}// 判断下标是否越界
private boolean isElementIndex(int index) {return index >= 0 && index < size;
}

查询元素

查询元素的方法跟位置区分，共有三种，查询头节点、查询尾节点和查询任意位置元素。

方法含义 如果不存在则返回null 如果不存在则抛异常 

查询头部 peek/peekFirst getFirst/element 

查询尾部 peekLast getLast 

查询任意位置 - get

看一下从头查询的element()方法的底层实现：

// 查询元素
public E element() {return getFirst();
}// 获取第一个元素
public E getFirst() {final LinkedList.Node<E> f = first;if (f == null) {throw new NoSuchElementException();}return f.item;
}

再看一个查询尾节点的方法getLast()的底层实现：

// 获取最后一个元素
public E getLast() {final LinkedList.Node<E> l = last;if (l == null) {throw new NoSuchElementException();}return l.item;
}

再看一个查询任意位置的方法get(index)的底层实现：

// 查询下标是index位置的元素
public E get(int index) {// 检查下标是否越界checkElementIndex(index);// 返回对应下标的元素return node(index).item;
}// 返回对应下标的元素
LinkedList.Node<E> node(int index) {// 判断下标是否落在前半段if (index < (size >> 1)) {// 如果在前半段，则从头开始遍历LinkedList.Node<E> x = first;for (int i = 0; i < index; i++) {x = x.next;}return x;} else {// 如果在后半段，则从尾开始遍历LinkedList.Node<E> x = last;for (int i = size - 1; i > index; i--) {x = x.prev;}return x;}
}

 可见LinkedList的也支持随机访问，只不过时间复杂度是O(n)。

删除元素 

删除元素的方法按照位置区分，也分为三种，分别是删除头节点、删除尾节点和删除任意位置节点。

方法含义  返回布尔值（如果不存在，返回false） 返回旧值（如果不存在则抛异常）

 从头部删除 remove(o)/removeFirstOccurrence  remove/poll/pollFirst/removeFirst/pop 

从尾部删除 removeLastOccurrence pollLast/removeLast 

从任意位置删除 - remove(index) 

先看一个从头开始删除的方法remove()的底层实现： 

// 删除元素
public E remove() {// 删除第一个元素return removeFirst();
}// 从头删除元素
public E removeFirst() {final LinkedList.Node<E> f = first;if (f == null) {throw new NoSuchElementException();}// 调用实际的删除方法return unlinkFirst(f);
}// 删除第一个元素
private E unlinkFirst(LinkedList.Node<E> f) {final E element = f.item;final LinkedList.Node<E> next = f.next;// 断开头节点与后继节点的连接f.item = null;f.next = null;first = next;if (next == null) {last = null;} else {next.prev = null;}size--;modCount++;return element;
}

 再看一个从最后一个节点开始删除的方法removeLast()的底层实现：

// 删除最后一个元素
public E removeLast() {final LinkedList.Node<E> l = last;if (l == null) {throw new NoSuchElementException();}// 实际的删除逻辑return unlinkLast(l);
}// 删除最后一个元素
private E unlinkLast(LinkedList.Node<E> l) {final E element = l.item;// 断开与前一个节点的连接final LinkedList.Node<E> prev = l.prev;l.item = null;l.prev = null;last = prev;if (prev == null) {first = null;} else {prev.next = null;}size--;modCount++;return element;
}

再看一个从任意位置的节点开始删除的方法remove(index)的底层实现：

// 删除下标是index位置的元素
public E remove(int index) {// 检查下标是否越界checkElementIndex(index);// 删除下标对应的元素（先找到下标对应的元素）return unlink(node(index));
}// 删除下标对应的元素
E unlink(LinkedList.Node<E> x) {final E element = x.item;// 1. 备份当前节点的前后节点final LinkedList.Node<E> next = x.next;final LinkedList.Node<E> prev = x.prev;// 2. 断开与前驱节点的连接if (prev == null) {first = next;} else {prev.next = next;x.prev = null;}// 3. 断开与后继节点的连接if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;
}

 总结

学完了LinkedList的核心方法的源码，现在可以很容易回答文章开头的几个问题了。

  1. LinkedList的底层是基于什么数据结构实现的？

答案：双向链表。

  1. LinkedList的插入和删除操作时间复杂度是否都是 O(1) ?

答案：不是，在头尾操作的时间复杂度是O(1)，在其他位置操作的时间复杂度是O(n)。

  1. LinkedList和ArrayList相比，哪种结构存储数据的时候更占内存？

答案：由于LinkedList的每个节点还包含前后节点的引用，所以会占用更多的空间。

  1. LinkedList真的不支持随机访问吗？

答案：LinkedList支持随机访问，比如get(index)和get(o)方法，不过它们的时间复杂度是O(n)。

  1. LinkedList是线程安全的吗？

答案：LinkedList不是线程安全的，内部没有提供同步机制来保证线程安全。并发修改的时候可能导致数据错乱，在遍历过程中修改会抛出ConcurrentModificationException异常。 想要线程安全，其中一种方式是初始化List的时候使用 Collections.synchronizedList() 修饰。这样LinkedList所有操作都变成同步操作，性能较差。还有一种性能较好，又能保证线程安全的方式是使用 CopyOnWriteArrayList

// 第一种方式，使用 Collections.synchronizedList() 修饰
List<Integer> list = Collections.synchronizedList(new LinkedList<>());// 第二种方式，使用 CopyOnWriteArrayList
List<Integer> list = new CopyOnWriteArrayList<>();

同样因为 LinkedList有队列的相关属性，也可以当做队列来使用，并且可以实现简单的LRU算法来进行数据淘汰的方式。

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【启扬方案】启扬储能管理平板助力储能电站实现智能且高效化运行

【启扬方案】启扬储能管理平板助力储能电站实现智能且高效化运行

在储能领域&#xff0c;储能电站扮演着重要角色&#xff0c;储能电站技术的应用贯穿于电力系统发电、输电、配电、用电的各个环节。实现电力系统削峰填谷、可再生能源发电波动平滑与跟踪计划处理、高效系统调频&#xff0c;增加供电的可靠性。 但随着储能电⼒系统建设发展得越来…
阅读更多...
java开发的智能聊天机器人_超级AI_支持自动绘画功能

java开发的智能聊天机器人_超级AI_支持自动绘画功能

支持Web、Android、IOS、H5等多终端应用。它使用OpenAI的ChatGPT模型实现智能聊天机器人&#xff0c;并支持绘图自动生成Vincent图。未来还将接入国内大型AI模型&#xff0c;如文心一言、统一千问、MOSS等模型&#xff0c;并不断更新以满足用户需求。 AI大脑软件中的AI绘画功能…
阅读更多...
GNN 学习笔记

GNN 学习笔记

稍微看一下之后备用。 【图神经网络综述】GNN原理&#xff0b;落地应用实现框架全解_gnn实现-CSDN博客 GNN相比CNN最大的区别在于数据结构&#xff0c;CNN一般作用在二维、三维数据里&#xff0c;如图像、表格数据等&#xff0c;可以进行卷积操作。而GNN作用在一个由节点和边…
阅读更多...
Baumer工业相机堡盟工业相机如何通过BGAPISDK获取相机的各种信息如SN/ID等等（C#）

Baumer工业相机堡盟工业相机如何通过BGAPISDK获取相机的各种信息如SN/ID等等（C#）

Baumer工业相机堡盟工业相机如何通过BGAPISDK获取相机的各种信息如SN/ID等等&#xff08;C#&#xff09; Baumer工业相机Baumer工业相机通过SDK获取相关生产信息的技术背景通过SDK获取相机信息的代码分析获取Baumer工业相机相关信息Baumer工业相机相关参数信息获取的测试 Baume…
阅读更多...
2. 如何通过公网IP端口映射访问到设备的vmware虚拟机的ubuntu服务器

2. 如何通过公网IP端口映射访问到设备的vmware虚拟机的ubuntu服务器

文章目录 1. 主机设备是Windows 11系统2. 安装vmware虚拟机3. 创建ubuntu虚拟机&#xff08;据说CentOS 7 明年就不维护了&#xff0c;就不用这个版本的linux了&#xff09;4. 安装nginx服务:默认端口805. 安装ssh服务:默认端口226. 设置主机 -> ubuntu的端口映射7. 设置路由…
阅读更多...
kafka配置多个消费者groupid kafka多个消费者消费同一个partition（java）

kafka配置多个消费者groupid kafka多个消费者消费同一个partition（java）

目录 1- 单播模式&#xff0c;只有一个消费者组2- 广播模式&#xff0c;多个消费者组3- Java实践 kafka是由Apache软件基金会开发的一个开源流处理平台。kafka是一种高吞吐量的分布式发布订阅消息系统&#xff0c;它可以处理消费者在网站中的所有动作流数据。 kafka中partition…
阅读更多...
【Spark精讲】Spark作业执行原理

【Spark精讲】Spark作业执行原理

基本流程 用户编写的Spark应用程序最开始都要初始化SparkContext。 用户编写的应用程序中&#xff0c;每执行一个action操作&#xff0c;就会触发一个job的执行&#xff0c;一个应用程序中可能会生成多个job执行。一个job如果存在宽依赖&#xff0c;会将shuffle前后划分成两个…
阅读更多...
Redis系列之简单实现watchDog自动续期机制

Redis系列之简单实现watchDog自动续期机制

在分布锁的实际使用中&#xff0c;可能会遇到一种情况&#xff0c;一个业务执行时间很长&#xff0c;已经超过redis加锁的时间&#xff0c;也就是锁已经释放了&#xff0c;但是业务还没执行完成&#xff0c;这时候其它线程还是可以获取锁&#xff0c;那就没保证线程安全 项目环…
阅读更多...
指针浅谈(三）

指针浅谈(三）

在指针浅谈(二)http://t.csdnimg.cn/SKAkD中我们讲到了const修饰指针、指针运算、野指针、assert断言和传址调用的内容&#xff0c;今天我们继续学习有关数组名、指针访问数组、一维数组传参的本质相关的内容&#xff0c;内容比较深入&#xff0c;如果觉得哪里讲解的不行&#…
阅读更多...
微服务实战系列之通信

微服务实战系列之通信

前言 掰个指头数一数&#xff0c;博主的“微服务实战系列”从无到有&#xff0c;从零走到了十五。如果比作时钟&#xff0c;刚好走过了一刻度。 当初为什么要做这个系列&#xff0c;博主想了又想&#xff0c;私以为作为当下软件领域的几个“hot spot”之一&#xff0c;又乘着…
阅读更多...
机器学习---Adaboost算法

机器学习---Adaboost算法

1. Adaboost算法介绍 Adaboost是一种迭代算法&#xff0c;其核心思想是针对同一个训练集训练不同的分类器&#xff08;弱分类器&#xff09;&#xff0c;然 后把这些弱分类器集合起来&#xff0c;构成一个更强的最终分类器&#xff08;强分类器&#xff09;。Adaboost算法本身…
阅读更多...
《地理信息系统原理》笔记/期末复习资料（10. 空间数据挖掘与空间决策支持系统）

《地理信息系统原理》笔记/期末复习资料（10. 空间数据挖掘与空间决策支持系统）

目录 10. 空间数据挖掘与空间决策支持系统 10.1. 空间数据挖掘 10.1.1. 空间数据挖掘的概念 10.1.2. 空间数据挖掘的方法与过程 10.1.3. 空间数据挖掘的应用 10.2. 空间决策支持系统 10.2.1. 空间决策支持系统的概念 10.2.2. 空间决策支持系统的结构 10.2.3. 空间决策…
阅读更多...
理解排序算法：冒泡排序、选择排序与归并排序

理解排序算法：冒泡排序、选择排序与归并排序

简介&#xff1a; 在计算机科学中&#xff0c;排序算法是基础且重要的概念。本文将介绍三种常见的排序方法&#xff1a;冒泡排序、选择排序和归并排序。我们将探讨它们的工作原理、特点和适用场景&#xff0c;以帮助读者更好地理解和选择合适的排序方法。 冒泡排序 冒泡排序是…
阅读更多...
【面试经典150 | 二叉树】从前序与中序遍历序列构造二叉树

【面试经典150 | 二叉树】从前序与中序遍历序列构造二叉树

文章目录 写在前面Tag题目来源题目解读解题思路方法一&#xff1a;递归 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于本题涉及到的数据结构等内容…
阅读更多...
QT作业4

QT作业4

实现一个闹钟&#xff0c;当输入时间后&#xff0c;点击启动到达时间后循环播报三遍&#xff0c;便签内容 头文件&#xff1a; #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTextToSpeech> //文本转语言类 #include <QTimerEvent> //定…
阅读更多...
Android : BottomNavigation底部导航_简单应用

Android : BottomNavigation底部导航_简单应用

示例图&#xff1a; 1.先创建底部导航需要的图片 res → New → Vector Asset 创建三个矢量图 图片1 baseline_home.xml <vector android:height"24dp" android:tint"#000000"android:viewportHeight"24" android:viewportWidth"24…
阅读更多...
Axure电商产品移动端交互原型，移动端高保真Axure原型图（RP源文件手机app界面UI设计模板）

Axure电商产品移动端交互原型，移动端高保真Axure原型图（RP源文件手机app界面UI设计模板）

本作品是一套 Axure8 高保真移动端电商APP产品原型模板&#xff0c;包含了用户中心、会员成长、优惠券、积分、互动社区、运营推广、内容推荐、商品展示、订单流程、订单管理、售后及服务等完整的电商体系功能架构和业务流程。 本模板由一百三十多个界面上千个交互元件及事件组…
阅读更多...
基于Qt的蓝牙Bluetooth在ubuntu实现模拟

基于Qt的蓝牙Bluetooth在ubuntu实现模拟

​# 前言 Qt 官方提供了蓝牙的相关类和 API 函数，也提供了相关的例程给我们参考。笔者根据 Qt官方的例程编写出适合我们 Ubuntu 和 gec6818开发板的例程。注意 Windows 上不能使用 Qt 的蓝牙例程，因为底层需要有 BlueZ协议栈，而 Windows 没有。Windows 可能需要去移植。笔者…
阅读更多...
数据挖掘目标(Kaggle Titanic 生存测试)

数据挖掘目标(Kaggle Titanic 生存测试)

import numpy as np import pandas as pd import matplotlib.pyplot as plt import seaborn as sns1.数据导入 In [2]: train_data pd.read_csv(r../老师文件/train.csv) test_data pd.read_csv(r../老师文件/test.csv) labels pd.read_csv(r../老师文件/label.csv)[Su…
阅读更多...
HTML中常用表单元素使用（详解！）

HTML中常用表单元素使用（详解！）

Hi i,m JinXiang ⭐ 前言 ⭐ 本篇文章主要介绍HTML中常用表单元素使用以及部分理论知识 &#x1f349;欢迎点赞 &#x1f44d; 收藏 ⭐留言评论 &#x1f4dd;私信必回哟&#x1f601; &#x1f349;博主收将持续更新学习记录获&#xff0c;友友们有任何问题可以在评论区留言 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023