LinkedList 是 Java 集合框架中基于双向链表实现的 List 接口，同时实现了 Deque 接口，因此它不仅可以作为列表使用，还可以作为队列、栈等数据结构使用。与 ArrayList 相比，LinkedList 在元素插入和删除操作上更高效（因为插入元素只需要断开链表连接，然后建立与前一个和后一个节点的连接），但随机访问性能较差（需要从链表头开始遍历查找）。
链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点组成，每个结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表有多种类型，包括单链表、双链表、单向循环链表和双向循环链表。其中，单链表是最基本的形式，每个结点只包含一个指向下一个结点的指针。双链表则在每个结点中增加了一个指向前一个结点的指针，使得可以在链表中双向遍历。
单链表是链表数据结构中最基础、最简单的形态，核心特征是每个节点仅通过一个「后继指针」连接下一个节点，形成单向串联的线性结构。它虽功能不如双向链表灵活，但胜在结构简洁、内存开销小，是理解复杂链表（双向、循环）及树、图等数据结构的基础。如下图：
单向循环链表是单向链表的进阶形态，核心改造是将单向链表中「尾节点的 next 指针从 null 改为指向头节点」，形成一个闭合的环形结构。这种设计保留了单向链表“单指针串联” 的简洁性，同时新增了 “循环遍历”、“首尾快速访问” 等特性，适合环形场景需求。如下图：
双链表（又称双向链表）是链表数据结构的重要形态，核心设计是每个节点同时包含「前驱指针」和「后继指针」—— 前者指向当前节点的前一个节点，后者指向后一个节点。这种双指针结构让双链表同时支持 “正向遍历” 和 “反向遍历”，在节点插入、删除等操作上更灵活，是很多高级数据结构（如 Java LinkedList、浏览器历史记录）的底层实现。如下图：
双向循环链表是双链表的进阶形态，核心设计是在双链表 “前驱 + 后继双指针” 的基础上，让头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点，形成一个完全闭合的环形结构。这种设计同时融合了 “双向遍历” 和 “循环访问” 的优势，消除了链表的 “首尾边界”，在环形场景中灵活性远超普通双链表或单向循环链表。如下图：
LinkedList 类提供了两个构造方法，分别如下：
构造一个空的 LinkedList 实例，初始化后链表中不包含任何元素，底层双向链表的头节点（first）和尾节点（last）均为null，size 为 0。此构造方法执行效率高，时间复杂度为 O(1)，定义如下：
public LinkedList() {
}构造一个包含指定集合元素的 LinkedList 实例，元素顺序与集合迭代器返回的顺序一致。此构造方法通过先调用无参构造创建空链表，再将集合中所有元素批量添加到链表中实现初始化。适合需要基于已有集合快速创建链表的场景，定义如下：
/**
* @param c 包含要放入此链表中的元素的集合
* @throws NullPointerException 如果指定的集合为null（由addAll方法抛出）
* @SuppressWarnings("this-escape") 抑制"this引用在构造方法中逸出"的警告
* （因addAll方法内部会使用this，但实际不会导致线程安全问题）
*/
@SuppressWarnings("this-escape")
public LinkedList(Collection<? extends E> c) {
this(); // 调用无参构造初始化空链表
addAll(c); // 将集合c中的所有元素添加到链表中
}
以下是一个 LinkedList 示例，演示了其常用方法的用法，包括添加、删除、访问、修改等操作：
package com.hxstrive.java_collection.linkedList;
import java.util.Deque;
import java.util.LinkedList;
public class LinkedListDemo {
public static void main(String[] args) {
// 1. 创建LinkedList（可作为List或Deque使用）
LinkedList<String> linkedList = new LinkedList<>();
// 2. 添加元素
linkedList.add("元素1"); // 尾部添加
linkedList.addFirst("头部元素"); // 头部添加
linkedList.addLast("尾部元素"); // 尾部添加
linkedList.add(2, "插入的元素"); // 指定位置插入
System.out.println("添加元素后: " + linkedList);
// 输出: [头部元素, 元素1, 插入的元素, 尾部元素]
// 3. 访问元素
System.out.println("第一个元素: " + linkedList.getFirst()); // 头部元素
System.out.println("索引2的元素: " + linkedList.get(2)); // 插入的元素
System.out.println("最后一个元素: " + linkedList.getLast()); // 尾部元素
System.out.println("元素1的索引: " + linkedList.indexOf("元素1")); // 1
// 4. 修改元素
linkedList.set(1, "修改后的元素1");
System.out.println("修改后: " + linkedList);
// 输出: [头部元素, 修改后的元素1, 插入的元素, 尾部元素]
// 5. 删除元素
linkedList.removeFirst(); // 删除头部元素
linkedList.removeLast(); // 删除尾部元素
linkedList.remove(1); // 删除指定索引元素
System.out.println("删除后: " + linkedList); // [修改后的元素1]
// 6. 作为队列(Queue)使用 (FIFO: 先进先出)
Deque<String> queue = new LinkedList<>();
queue.offer("队列元素1"); // 入队
queue.offer("队列元素2");
System.out.println("队首元素: " + queue.peek()); // 查看队首
System.out.println("出队元素: " + queue.poll()); // 出队
System.out.println("队列剩余: " + queue); // [队列元素2]
// 7. 作为栈(Stack)使用 (LIFO: 后进先出)
Deque<String> stack = new LinkedList<>();
stack.push("栈元素1"); // 入栈
stack.push("栈元素2");
System.out.println("栈顶元素: " + stack.peek()); // 查看栈顶
System.out.println("出栈元素: " + stack.pop()); // 出栈
System.out.println("栈剩余: " + stack); // [栈元素1]
// 8. 其他常用方法
linkedList.addAll(queue); // 添加另一个集合的所有元素
System.out.println("添加队列元素后: " + linkedList); // [修改后的元素1, 队列元素2]
System.out.println("是否包含指定元素: " + linkedList.contains("队列元素2")); // true
System.out.println("链表大小: " + linkedList.size()); // 2
linkedList.clear(); // 清空链表
System.out.println("清空后是否为空: " + linkedList.isEmpty()); // true
}
}LinkedList（链表）是一种常见的数据结构，用于存储一系列元素。与数组不同，链表中的元素在内存中不是连续存储的，而是通过指针（或引用）相互连接。
在 LinkedList 中，通过 Node 内部静态类来表示链表中的一个节点，定义如下：
// 私有静态内部类，用于表示双向链表中的单个节点
// 泛型参数<E>表示节点中存储的数据类型
private static class Node<E> {
// 节点中存储的实际数据元素
E item;
// 指向下一个节点的引用（后继节点）
Node<E> next;
// 指向前一个节点的引用（前驱节点）
Node<E> prev;
// 节点的构造方法
// 参数说明：
// prev - 当前节点的前驱节点
// element - 当前节点要存储的数据元素
// next - 当前节点的后继节点
Node(Node<E> prev, E element, Node<E> next) {
this.item = element; // 初始化数据元素
this.next = next; // 初始化后继节点引用
this.prev = prev; // 初始化前驱节点引用
}
}如下图：
在 LinkedList 中，通过 addFirst() 方法将元素插入到链表的头部，代码如下：
/**
* 将指定元素插入到链表的开头（头部）
*
* 此方法通过调用linkFirst()来实现具体的插入逻辑，
* 时间复杂度为O(1)，是一种高效的头部插入操作
*
* @param e 要添加到链表头部的元素
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* 私有辅助方法：将元素e链接为链表的第一个元素
*
* 该方法负责处理头部插入的具体逻辑，包括创建新节点、
* 调整节点间的引用关系以及维护链表的基本属性
*
* @param e 要插入到链表头部的元素
*/
private void linkFirst(E e) {
// 保存当前链表的头节点引用到局部变量f
final Node<E> f = first;
// 创建新节点：
// - 前驱节点为null（因为要成为第一个节点）
// - 节点存储的元素为e
// - 后继节点为原来的头节点f
final Node<E> newNode = new Node<>(null, e, f);
// 将新节点设置为链表新的头节点
first = newNode;
// 检查原头节点是否为null（判断链表是否为空）
if (f == null)
// 如果原链表为空，新节点同时成为尾节点
last = newNode;
else
// 如果原链表非空，将原头节点的前驱指针指向新节点
f.prev = newNode;
// 链表的元素数量加1
size++;
// 修改计数器加1，用于支持迭代器的快速失败机制
// （当迭代过程中检测到modCount变化时，会抛出ConcurrentModificationException）
modCount++;
}
在 LinkedList 中，通过 addLast() 方法将元素插入到链表的尾部，代码如下：
/**
* 将指定元素追加到链表的末尾（尾部）
* <p>此方法功能与{@link #add}方法相同
* @param e 要添加到链表尾部的元素
*/
public void addLast(E e) {
linkLast(e);
}
/**
* 将元素e链接为链表的最后一个元素（尾部插入的具体实现）
*
* 该方法负责处理尾部插入的核心逻辑，包括创建新节点、
* 调整节点间的引用关系以及维护链表的基本属性
*
* @param e 要插入到链表尾部的元素
*/
void linkLast(E e) {
// 保存当前链表的尾节点引用到局部变量l
final Node<E> l = last;
// 创建新节点：
// - 前驱节点为原来的尾节点l
// - 节点存储的元素为e
// - 后继节点为null（因为要成为最后一个节点）
final Node<E> newNode = new Node<>(l, e, null);
// 将新节点设置为链表新的尾节点
last = newNode;
// 检查原尾节点是否为null（判断链表是否为空）
if (l == null)
// 如果原链表为空，新节点同时成为头节点
first = newNode;
else
// 如果原链表非空，将原尾节点的后继指针指向新节点
l.next = newNode;
// 链表的元素数量加1
size++;
// 修改计数器加1，用于支持迭代器的快速失败机制
// （当迭代过程中检测到modCount变化时，会抛出ConcurrentModificationException）
modCount++;
}
在 LinkedList 中，通过 add() 方法将元素插入到链表的尾部，代码如下：
/**
* 将指定元素追加到链表的末尾
*
* <p>此方法功能与{@link #addLast}方法完全相同
*
* @param e 要追加到链表中的元素
* @return {@code true}（按照{@link Collection#add}接口的规定返回true）
*/
public boolean add(E e) {
// 调用linkLast方法将元素添加到链表尾部
linkLast(e);
// 始终返回true，因为LinkedList允许添加null元素且添加操作总是成功的
return true;
}
在 LinkedList 中，通过 removeFirst() 方法删除链表的头部元素，代码如下：
/**
* 移除并返回链表中的第一个元素（头部元素）
*
* @return 从链表中移除的第一个元素
* @throws NoSuchElementException 如果链表为空时调用此方法
*/
public E removeFirst() {
// 获取当前链表的头节点
final Node<E> f = first;
// 如果头节点为null（链表为空），抛出异常
if (f == null)
throw new NoSuchElementException();
// 调用私有辅助方法unlinkFirst移除头节点并返回其元素
return unlinkFirst(f);
}
/**
* 私有辅助方法：解除非空头节点f的链接（即移除头节点）
* 注意：此方法假设传入的节点f是非空的且是当前的头节点
*
* @param f 要移除的头节点（必须非空）
* @return 被移除节点中存储的元素
*/
private E unlinkFirst(Node<E> f) {
// 断言：确保f是头节点且非空（代码中未实际执行，仅作为开发提示）
// assert f == first && f != null;
// 获取要移除节点中的元素（用于返回）
final E element = f.item;
// 获取要移除节点的下一个节点（新的头节点候选）
final Node<E> next = f.next;
// 将移除节点的数据域和指针域置为null，帮助垃圾回收（GC）
f.item = null;
f.next = null; // 断开与下一个节点的连接，便于GC回收
// 将下一个节点设为新的头节点
first = next;
// 检查新头节点是否为null（即原链表是否只有一个节点）
if (next == null)
// 如果原链表只有一个节点，移除后链表为空，尾节点也置为null
last = null;
else
// 如果原链表有多个节点，将新头节点的前驱指针置为null
next.prev = null;
// 链表长度减1
size--;
// 修改计数器加1，支持迭代器的快速失败机制
modCount++;
// 返回被移除节点中的元素
return element;
}
在 LinkedList 中，通过 removeLast() 方法删除链表的尾部元素，代码如下：
/**
* 移除并返回链表中的最后一个元素（尾部元素）
*
* @return 从链表中移除的最后一个元素
* @throws NoSuchElementException 如果链表为空时调用此方法
*/
public E removeLast() {
// 获取当前链表的尾节点
final Node<E> l = last;
// 如果尾节点为null（链表为空），抛出异常
if (l == null)
throw new NoSuchElementException();
// 调用私有辅助方法unlinkLast移除尾节点并返回其元素
return unlinkLast(l);
}
/**
* 私有辅助方法：解除非空尾节点l的链接（即移除尾节点）
* 注意：此方法假设传入的节点l是非空的且是当前的尾节点
*
* @param l 要移除的尾节点（必须非空）
* @return 被移除节点中存储的元素
*/
private E unlinkLast(Node<E> l) {
// 断言：确保l是尾节点且非空（代码中未实际执行，仅作为开发提示）
// assert l == last && l != null;
// 获取要移除节点中的元素（用于返回）
final E element = l.item;
// 获取要移除节点的前一个节点（新的尾节点候选）
final Node<E> prev = l.prev;
// 将移除节点的数据域和指针域置为null，帮助垃圾回收（GC）
l.item = null;
l.prev = null; // 断开与前一个节点的连接，便于GC回收
// 将前一个节点设为新的尾节点
last = prev;
// 检查新尾节点是否为null（即原链表是否只有一个节点）
if (prev == null)
// 如果原链表只有一个节点，移除后链表为空，头节点也置为null
first = null;
else
// 如果原链表有多个节点，将新尾节点的后继指针置为null
prev.next = null;
// 链表长度减1
size--;
// 修改计数器加1，支持迭代器的快速失败机制
modCount++;
// 返回被移除节点中的元素
return element;
}
在 LinkedList 中，通过 remove() 方法将元素从链表删除，代码如下：
/**
* 移除链表中指定位置的元素，并将后续元素向左移动（索引减1）
* 返回被移除的元素
*
* @param index 要移除元素的索引位置
* @return 被移除的元素
* @throws IndexOutOfBoundsException 如果索引超出范围（index < 0 或 index >= size()）
*/
public E remove(int index) {
// 检查索引是否有效（在 0 到 size-1 之间）
checkElementIndex(index);
// 1. 通过 node(index) 找到指定索引处的节点
// 2. 调用 unlink 方法移除该节点并返回其元素
return unlink(node(index));
}
/**
* 私有辅助方法：解除非空节点x的链接（即从链表中移除节点x）
* 注意：此方法假设传入的节点x是非空的
*
* @param x 要从链表中移除的节点（必须非空）
* @return 被移除节点中存储的元素
*/
E unlink(Node<E> x) {
// 断言：确保传入的节点x非空（代码中未实际执行，仅作为开发提示）
// assert x != null;
// 获取要移除节点中的元素（用于返回）
final E element = x.item;
// 获取要移除节点的下一个节点
final Node<E> next = x.next;
// 获取要移除节点的上一个节点
final Node<E> prev = x.prev;
// 处理前驱节点的引用关系
if (prev == null) {
// 如果前驱节点为null，说明x是头节点，将头节点指向x的下一个节点
first = next;
} else {
// 否则，将前驱节点的next指向x的下一个节点
prev.next = next;
// 断开x与前驱节点的连接，帮助GC
x.prev = null;
}
// 处理后继节点的引用关系
if (next == null) {
// 如果后继节点为null，说明x是尾节点，将尾节点指向x的上一个节点
last = prev;
} else {
// 否则，将后继节点的prev指向x的上一个节点
next.prev = prev;
// 断开x与后继节点的连接，帮助GC
x.next = null;
}
// 清空节点x的数据域，帮助GC
x.item = null;
// 链表长度减1
size--;
// 修改计数器加1，支持迭代器的快速失败机制
modCount++;
// 返回被移除节点的元素
return element;
}更多源码请读者自行阅读分析。
川公网安备51010802032098