Java集合框架：LinkedList-EW帮帮网

private static class Node<E> {
    E item;          // 存储元素
    Node<E> next;    // 指向后继节点
    Node<E> prev;    // 指向前驱节点

    // 构造方法，创建节点时需要指定前驱、元素和后继
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Node是私有的静态内部类，只能在 LinkedList 内部访问

每个节点包含三个部分：元素本身、前驱节点引用、后继节点引用

这种结构允许从任意节点向两个方向遍历链表

LinkedList 通过以下几个字段维护整个链表结构：

transient Node<E> first;  // 指向头节点
transient Node<E> last;   // 指向尾节点
transient int size = 0;   // 元素数量
protected transient int modCount = 0;  // 从AbstractList继承，用于快速失败机制

first和last指针分别指向链表的头和尾，使得首尾操作可以在 O (1) 时间内完成

size记录元素数量，避免每次需要大小时遍历整个链表

modCount用于记录结构修改次数，迭代器通过检查此值实现快速失败

1.2 接口实现

LinkedList 实现了以下关键接口：

List<E>：提供列表的基本操作（增删改查）

Deque<E>：提供双端队列的操作（首尾元素操作）

Cloneable：支持克隆

Serializable：支持序列化

这意味着 LinkedList 既可以作为普通列表使用，也可以作为队列、栈等数据结构使用。

1.3 重要特性

允许 null 元素：可以添加 null 值到集合中

非线程安全：多线程环境下需要外部同步

快速失败机制：迭代器在检测到并发修改时会抛出 ConcurrentModificationException

无容量限制：链表可以动态增长，理论上只受内存限制

二、构造方法详解

LinkedList 提供了两个构造方法：

2.1 无参构造方法

创建一个空的 LinkedList：

// 构造空链表
LinkedList<String> list = new LinkedList<>();
System.out.println(list); // 输出：[]

2.2 集合参数构造方法

创建包含指定集合元素的 LinkedList，元素顺序与集合迭代器顺序一致：

// 从其他集合初始化
List<String> initial = Arrays.asList("a", "b", "c");
LinkedList<String> list = new LinkedList<>(initial);
System.out.println(list); // 输出：[a, b, c]

三、核心方法详解与示例

3.1 元素添加方法

3.1.1 基本添加操作

add(E e)：在链表尾部添加元素

add(int index, E element)：在指定位置插入元素

addAll(Collection<? extends E> c)：在尾部添加集合所有元素

addAll(int index, Collection<? extends E> c)：在指定位置插入集合所有元素

LinkedList<String> list = new LinkedList<>();

// 在尾部添加元素
list.add("A");
list.add("B");
System.out.println(list); // [A, B]

// 在指定位置插入
list.add(1, "C");
System.out.println(list); // [A, C, B]

// 添加整个集合
List<String> newElements = Arrays.asList("D", "E");
list.addAll(newElements);
System.out.println(list); // [A, C, B, D, E]

// 在指定位置添加集合
list.addAll(2, Arrays.asList("F", "G"));
System.out.println(list); // [A, C, F, G, B, D, E]

3.1.2 首尾添加操作（Deque 特性）

addFirst(E e)：在链表头部添加元素

addLast(E e)：在链表尾部添加元素（与 add 方法功能相同）

offer(E e)：在尾部添加元素（与 add 类似，队列风格）

offerFirst(E e)：在头部添加元素（与 addFirst 类似）

offerLast(E e)：在尾部添加元素（与 addLast 类似）

LinkedList<String> list = new LinkedList<>();

list.addFirst("A");  // 头部添加
list.addLast("B");   // 尾部添加
System.out.println(list); // [A, B]

list.offer("C");     // 尾部添加
list.offerFirst("D");// 头部添加
System.out.println(list); // [D, A, B, C]

3.1.3 栈操作

push(E e)：将元素推入栈（实际上是在头部添加，与 addFirst 相同）

LinkedList<String> stack = new LinkedList<>();

stack.push("A");
stack.push("B");
stack.push("C");
System.out.println(stack); // [C, B, A]  栈顶是C

3.2 元素删除方法

3.2.1 基本删除操作

remove()：删除并返回头部元素

remove(int index)：删除指定位置元素并返回

remove(Object o)：删除第一个匹配的元素，返回是否删除成功

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C", "B"));

// 删除头部元素
String first = list.remove();
System.out.println(first); // A
System.out.println(list);  // [B, C, B]

// 删除指定位置元素
String removed = list.remove(1);
System.out.println(removed); // C
System.out.println(list);    // [B, B]

// 删除指定元素
boolean isRemoved = list.remove("B");
System.out.println(isRemoved); // true
System.out.println(list);      // [B]

3.2.2 首尾删除操作（Deque 特性）

removeFirst()：删除并返回头部元素

removeLast()：删除并返回尾部元素

removeFirstOccurrence(Object o)：删除第一次出现的元素

removeLastOccurrence(Object o)：删除最后一次出现的元素

poll()：删除并返回头部元素（与 remove 类似，队列为空时返回 null）

pollFirst()：删除并返回头部元素（与 removeFirst 类似）

pollLast()：删除并返回尾部元素（与 removeLast 类似）

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C", "B", "D"));

// 删除第一次出现的B
list.removeFirstOccurrence("B");
System.out.println(list); // [A, C, B, D]

// 删除最后一次出现的B
list.removeLastOccurrence("B");
System.out.println(list); // [A, C, D]

// poll系列方法
String head = list.poll();      // 移除头部
String last = list.pollLast();  // 移除尾部
System.out.println(head);  // A
System.out.println(last);  // D
System.out.println(list);  // [C]

3.2.3 栈操作

pop()：弹出栈顶元素（实际上是删除头部元素，与 removeFirst 相同）

LinkedList<String> stack = new LinkedList<>(Arrays.asList("A", "B", "C"));

String top = stack.pop();
System.out.println(top);   // A
System.out.println(stack); // [B, C]

3.3 元素查询方法

3.3.1 基本查询操作

get(int index)：返回指定位置的元素

getFirst()：返回头部元素

getLast()：返回尾部元素

contains(Object o)：判断是否包含指定元素

indexOf(Object o)：返回第一个匹配元素的索引

lastIndexOf(Object o)：返回最后一个匹配元素的索引

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C", "B"));

// 获取指定位置元素
String element = list.get(2);
System.out.println(element); // C

// 获取首尾元素
System.out.println(list.getFirst()); // A
System.out.println(list.getLast());  // B

// 查找元素位置
System.out.println(list.indexOf("B"));    // 1
System.out.println(list.lastIndexOf("B"));// 3

// 判断是否包含
System.out.println(list.contains("C"));   // true
System.out.println(list.contains("D"));   // false

3.3.2 队列风格查询（Deque 特性）

element()：返回头部元素（队列为空时抛异常）

peek()：返回头部元素（队列为空时返回 null）

peekFirst()：返回头部元素（队列为空时返回 null）

peekLast()：返回尾部元素（队列为空时返回 null）

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C"));

// 队列风格查询
System.out.println(list.element());    // A
System.out.println(list.peek());       // A
System.out.println(list.peekFirst());  // A
System.out.println(list.peekLast());   // C

// 空列表测试
LinkedList<String> emptyList = new LinkedList<>();
System.out.println(emptyList.peek());  // null
// System.out.println(emptyList.element()); // 抛出NoSuchElementException

3.4 元素修改方法

set(int index, E element)：替换指定位置的元素并返回旧元素

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C"));

// 替换元素
String old = list.set(1, "X");
System.out.println(old);   // B
System.out.println(list);  // [A, X, C]

3.5 其他常用方法

size()：返回元素数量

clear()：清空所有元素

clone()：返回浅拷贝

toArray()：转换为数组

toArray(T[] a)：转换为指定类型数组

descendingIterator()：返回逆序迭代器

listIterator(int index)：返回从指定位置开始的列表迭代器

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C"));

// 基本信息
System.out.println(list.size()); // 3

// 克隆
LinkedList<String> cloned = (LinkedList<String>) list.clone();
System.out.println(cloned); // [A, B, C]

// 转换为数组
Object[] array = list.toArray();
String[] strArray = list.toArray(new String[0]);

// 逆序迭代
Iterator<String> descIt = list.descendingIterator();
while (descIt.hasNext()) {
    System.out.print(descIt.next() + " "); // C B A
}

// 列表迭代器
ListIterator<String> lit = list.listIterator(1);
while (lit.hasNext()) {
    System.out.print(lit.next() + " "); // B C
}

// 清空列表
list.clear();
System.out.println(list.size()); // 0

四、LinkedList 与 ArrayList 对比分析

特性	LinkedList	ArrayList
底层结构	双向链表	动态数组
随机访问	慢（O (n)）	快（O (1)）
头部插入 / 删除	快（O (1)）	慢（O (n)）
尾部插入 / 删除	快（O (1)）	快（O (1)）
中间插入 / 删除	慢（O (n)）	慢（O (n)）
内存占用	较高（每个节点需要额外存储前后引用）	较低（连续存储）
扩容机制	无需扩容	需要扩容（通常扩容为 1.5 倍）

选择建议：

需要频繁随机访问时，选择 ArrayList

需要频繁在首尾操作元素时，选择 LinkedList

需要频繁在中间插入删除时，视具体情况而定（ LinkedList 需要先遍历到指定位置，也是 O (n) 操作）

五、线程安全问题

LinkedList 是非线程安全的集合类。在多线程环境下，若有一个线程修改了集合结构（添加或删除元素），其他线程在迭代时可能会抛出 ConcurrentModificationException。

线程安全解决方案：

1、使用 Collections.synchronizedList() 包装：

List<String> syncList = Collections.synchronizedList(new LinkedList<>());

2、使用 java.util.concurrent 包下的 ConcurrentLinkedDeque（推荐）：

Deque<String> concurrentDeque = new ConcurrentLinkedDeque<>();

六、迭代器与快速失败机制

LinkedList 的迭代器（包括 iterator 和 listIterator）采用快速失败（fail-fast）机制：当迭代器创建后，如果集合结构被修改（除了通过迭代器自身的方法），迭代器会立即抛出 ConcurrentModificationException。

LinkedList<String> list = new LinkedList<>(Arrays.asList("A", "B", "C"));

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    if (s.equals("B")) {
        // 使用迭代器的remove方法是安全的
        it.remove(); 
        // 直接使用list的remove方法会抛出异常
        // list.remove("B"); // 抛出ConcurrentModificationException
    }
}
System.out.println(list); // [A, C]

注意：

快速失败机制只是尽力而为，不能保证一定能检测到并发修改，因此不能依赖它来处理并发问题，只能用于调试。

迭代方对比：

LinkedList<String> list = new LinkedList<>();
// 添加元素...

// 方式1：for循环通过索引访问 - 性能最差
for (int i = 0; i < list.size(); i++) {
    String s = list.get(i);  // 每次get都要从头或尾遍历
}

// 方式2：增强for循环 - 内部使用迭代器
for (String s : list) {
    // 操作元素
}

// 方式3：显式使用迭代器 - 可以控制遍历过程
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String s = it.next();
    // 可以调用it.remove()
}

// 方式4：使用forEach方法（Java 8+）
list.forEach(s -> {
    // 操作元素
});

避免使用 for 循环通过索引访问 LinkedList

优先使用迭代器或增强 for 循环

需要删除元素时，使用迭代器的 remove () 方法

七、常见问题与注意事项

7.1 关于 null 元素

LinkedList 允许添加 null 元素，并且可以正确处理：

LinkedList<String> list = new LinkedList<>();
list.add(null);
list.add("A");
list.add(null);

System.out.println(list.contains(null));  // true
System.out.println(list.indexOf(null));   // 0
System.out.println(list.lastIndexOf(null)); // 2

但需注意：在使用indexOf()和lastIndexOf()时，null 值会被正确识别和比较。

7.2 序列化问题

LinkedList 实现了 Serializable 接口，但它的first、last和size字段都被声明为transient，这意味着默认序列化机制不会序列化这些字段。

LinkedList 通过重写writeObject()和readObject()方法实现了自定义序列化，只序列化元素本身，而不是整个节点结构，这样可以减小序列化后的大小。

7.3 克隆问题

LinkedList 的clone()方法返回的是浅拷贝：

LinkedList<List<String>> list = new LinkedList<>();
list.add(new ArrayList<>());

LinkedList<List<String>> cloned = (LinkedList<List<String>>) list.clone();
// 克隆后的列表包含相同的元素引用
System.out.println(list.get(0) == cloned.get(0));  // true

这意味着：

基本类型元素会被复制

对象元素只会复制引用，不会创建新对象

修改克隆列表中的对象元素会影响原列表

Java集合框架：LinkedList

文档链接

一、LinkedList 核心原理

1.1 底层数据结构