LinkedList 源码分析

🕗 发布于 2024-11-07 23:24 java

LinkedList 源码分析

1. LinkedList 概述

1.1 List 是什么？

List 接口是 Java 集合框架中的一个重要组成部分，作为 Collection 的子接口，它定义了一种有序集合（也称为序列）。实现该接口的类（如 ArrayList 和 LinkedList）可以通过元素的整数索引精确控制元素的插入位置，支持重复元素的存储。

1.2 LinkedList 是什么？

LinkedList 是一个基于双向链表实现的集合。它不仅支持基本的列表操作，还可以被用作堆栈、队列或双端队列。其主要特点包括：

查询速度较慢（O(n)）
插入和删除操作速度较快（O(1)）
线程不安全
效率高

2. 核心源码分析

2.1 类声明

LinkedList 类的声明如下：

public class LinkedList<E> extends AbstractSequentialList<E> 
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
    // ...
}

Deque：实现了 Deque 接口，使得 LinkedList 具备队列特性。
Cloneable：支持克隆功能。
Serializable：支持序列化。

2.2 成员变量

LinkedList 的主要成员包括：

transient Node<E> first; // 链表的头节点
transient Node<E> last;  // 链表的尾节点
transient int size;      // 链表的大小

2.3 内部私有类 Node

Node 类表示链表的节点，包含数据和指向前后节点的指针。

private static class Node<E> {
    E item;                // 数据
    Node<E> next;         // 指向下一个节点的指针
    Node<E> prev;         // 指向前一个节点的指针

    Node(Node<E> prev, E element, Node<E> next) {
        this.prev = prev;
        this.item = element;
        this.next = next;
    }
}

2.4 构造方法

LinkedList 提供多个构造方法，以便用户创建空链表或根据集合初始化链表。


/**
 * 无参构造
 */
public LinkedList() {
}

/**
 * 带参构造，创建一个包含集合 c 的 LinkedList
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

2.5 添加方法

2.5.1 add(E e)

向链表添加元素的核心方法是 linkLast：

public void add(E e) {
    linkLast(e);
}

private void linkLast(E e) {
    final Node<E> l = last; // 获取当前尾节点
    final Node<E> newNode = new Node<>(l, e, null); // 创建新节点
    last = newNode; // 更新尾节点
    if (l == null) { // 如果链表为空
        first = newNode; // 新节点既是头节点
    } else {
        l.next = newNode; // 否则，将旧尾节点的 next 指向新节点
    }
    size++;
}

2.5.2 add(int index, E element)

在指定索引处添加元素：

public void add(int index, E element) {
    Node<E> node = node(index);
    linkBefore(element, node);
}

private void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev; // 获取前驱节点
    final Node<E> newNode = new Node<>(pred, e, succ); // 创建新节点
    succ.prev = newNode; // 更新后继节点的前驱
    if (pred == null) {
        first = newNode; // 更新头节点
    } else {
        pred.next = newNode; // 更新前驱节点的后继
    }
    size++;
}

2.5.3 addAll(Collection<? extends E> c)

添加集合：将集合 c 中的所有元素添加到链表的末尾。

public boolean addAll(Collection<? extends E> c) {
    // 调用重载方法，将集合的元素添加到链表末尾
    return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    // 检查插入位置是否有效
    checkPositionIndex(index);

    // 将集合转换为数组
    Object[] a = c.toArray();
    int numNew = a.length; // 新增元素的数量
    if (numNew == 0) // 如果集合为空，直接返回 false
        return false;

    Node<E> pred, succ; // 定义前驱和后继节点
    if (index == size) { // 如果在链表末尾插入
        succ = null; // 后继节点为 null
        pred = last; // 前驱节点为当前最后一个节点
    } else { // 在中间位置插入
        succ = node(index); // 获取后继节点
        pred = succ.prev; // 获取前驱节点
    }

    // 遍历数组中的每个元素，创建新节点并插入链表
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o; // 类型转换
        Node<E> newNode = new Node<>(pred, e, null); // 创建新节点
        if (pred == null) // 如果没有前驱节点，说明链表为空
            first = newNode; // 更新头结点
        else
            pred.next = newNode; // 前驱节点的 next 指向新节点
        pred = newNode; // 更新前驱节点为新节点
    }

    // 如果后继节点为 null，更新尾结点
    if (succ == null) {
        last = pred; // 将尾结点更新为新插入的最后一个节点
    } else { // 否则，连接新节点与后继节点
        pred.next = succ; // 新节点的 next 指向后继节点
        succ.prev = pred; // 后继节点的 prev 指向新节点
    }

    size += numNew; // 更新链表大小
    modCount++; // 更新修改计数
    return true; // 返回 true，表示成功添加元素
}

2.6 获取方法

2.6.1 get(int index)

通过索引获取元素，时间复杂度为 O(n)：

public E get(int index) {
    return node(index).item; // 获取指定节点的值
}

2.7 删除方法

2.7.1 remove(int index)

根据索引删除元素：

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

private E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next; // 更新头节点
    } else {
        prev.next = next; // 更新前驱节点
    }

    if (next == null) {
        last = prev; // 更新尾节点
    } else {
        next.prev = prev; // 更新后继节点
    }
    size--;
    return element;
}

2.7.2 remove()

空参删除元素 : 删除的是第一个结点

public E remove() {
        return removeFirst();
    }

2.7.3 remove(Object o)

根据传递对象删除结点：

判断删除元素是否存在
找到该元素在链表中位置，并执行unlink()方法

public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

3. 重点内容分析

底层操作机制（添加元素）

1. 初始化链表

头结点 (first) 和 尾结点 (last)：
- 在链表创建时，first 和 last 都被初始化为 null，表示链表当前是空的。

2. 添加第一个元素

创建新节点：
- 当添加第一个元素时，会创建一个新的节点对象。
- 将 first 和 last 都指向这个新节点，因为此时链表中只有一个元素。

3. 添加第二个元素

创建第二个节点：
- 当添加第二个元素时，会创建另一个新的节点对象。
- 此时，原有的第一个节点的 next 指针会指向新创建的第二个节点。
- last 指针会更新为指向新的第二个节点。

继续添加元素的过程

每次添加新节点时：
- 新节点的 prev 指向当前的 last 节点（即链表的最后一个节点）。
- 当前 last 节点的 next 指向新节点。
- 更新 last 指向新创建的节点。

4. 性能分析

时间复杂度：
- 插入：O(1)（在头或尾），O(n)（在指定位置）
- 删除：O(n)
- 查找：O(n)
空间复杂度：O(n)，每个节点占用额外的指针空间。

5. 总结

]

继续添加元素的过程

每次添加新节点时：
- 新节点的 prev 指向当前的 last 节点（即链表的最后一个节点）。
- 当前 last 节点的 next 指向新节点。
- 更新 last 指向新创建的节点。

[外链图片转存中…(img-3jzbmisP-1730257255360)]

4. 性能分析

时间复杂度：
- 插入：O(1)（在头或尾），O(n)（在指定位置）
- 删除：O(n)
- 查找：O(n)
空间复杂度：O(n)，每个节点占用额外的指针空间。

5. 总结

LinkedList 提供了一种灵活且动态的数据存储方式，适合频繁的插入和删除操作。虽然查询效率较低，但在特定场景下，它比 ArrayList 更具优势。理解 LinkedList 的内部实现和操作机制，有助于更好地选择合适的数据结构以应对不同的编程需求。

原文地址：https://blog.csdn.net/PQ781826/article/details/143359542

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：100种算法【Python版】第54篇——无损压缩之DEFLATE算法
下一篇：基于百度飞桨paddle的paddlepaddle2.4.2等系列项目的运行

Web性能优化：从基础到高级
然而，要充分发挥性能优化的潜力，还需要持续监测和逐步优化，确保每一步都符合用户体验的要求。企业级应用通常包含复杂的业务逻辑和大量的数据交互，通过优化 CSS 和 JavaScript，避免阻塞渲染，可
阅读更多2024-11-15
HTML5+CSS前端开发【保姆级教学】＋前端介绍和软件安装
前端开发主要涉及网站和 App，用户能够从 App 屏幕或浏览器上看到东西。能够从 App 屏幕和浏览器上看到的东西都属于前端。文章适合计算机小白，大佬请绕行！
阅读更多2024-11-15
群控系统服务端开发模式-应用开发-前端角色功能开发
群控系统服务端开发模式-应用开发-前端角色功能开发
阅读更多2024-11-15
自定义反序列化过程
需求：student对象中name属性，序列化时将该属性映射为stuname，反序列化时将 Json中的NAME键值对映射到name属性中。
阅读更多2024-11-15
界面控件DevExpress WPF中文教程：TreeList视图及创建分配视图
本文主要介绍DevExpress WPF数据网格组件的TreeList视图及如何创建和分配视图教程，欢迎下载最新版组件体验！
阅读更多2024-11-15
微波无源器件 OMT1 一种用于倍频程接收机前端的十字转门四脊正交模耦合器(24-51GHz)
我们报道了一种用于天文学射电望远镜的毫米波波长接收机的一种十字转门四脊OMT的设计，制造和实测结果。此四脊OMT被直接兼容到一个四脊馈电喇叭来实现可以拓展矩形波导单模带宽的双极化低噪声接收机。使用了2
阅读更多2024-11-15
实战：深入探讨 MySQL 和 SQL Server 全文索引的使用及其弊端
MySQL 中的全文索引自 5.6 版本开始支持InnoDB引擎（在此之前，仅支持MyISAM引擎）。全文索引主要适用于CHARVARCHAR和TEXT类型字段，并提供了的查询方式，可以选择不同的查询
阅读更多2024-11-15
前端 - 使用uniapp+vue搭建前端项目（app端）
前端 - 使用uniapp+vue搭建前端项目（app端）
阅读更多2024-11-15
NFS存储基础操作
NFS 挂载主机在网络断开后卡住通常是由于默认的 NFS 挂载选项导致的。为了避免这种情况，可以使用特定的挂载选项来确保在 NFS 服务器不可用时主机不会卡住。在windows 启用和关闭Window
阅读更多2024-11-15
SpringCloud OpenFeign负载均衡远程调用跨服务调用连接池优化
Spring Cloud OpenFeign 是 Spring Cloud 的一部分，提供了一种声明式的 HTTP 客户端方式来简化服务间的通信。通过 OpenFeign，开发者可以像调用本地方法一样
阅读更多2024-11-15

LinkedList 源码分析