外贸电子商务网站建设今天的新闻头条

以下是基于 JDK 8 的 LinkedList 深度源码解析，涵盖其数据结构、核心方法实现、性能特点及使用场景。我们从 类结构、Node节点、插入/删除/访问操作、线程安全、性能对比 等角度进行详细分析

一、类结构与继承关系

1. 类定义

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

• AbstractSequentialList：提供按顺序访问元素的默认实现（如 get(int index)、set(int index, E element)）。
• List：支持按索引操作（如 add(int index, E element)、get(int index)）。
• Deque：双端队列接口，支持头尾插入/删除（如 addFirst()、removeLast()）。
• Cloneable 和 Serializable：支持克隆和序列化。

.

二、核心数据结构：Node节点

1. Node类定义

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;}
}

• 双向链表特性：每个节点通过 prev 和 next 指针连接，支持双向遍历。
• 内存分配：节点分散存储，不依赖连续内存（与 ArrayList 的数组不同）。

.

三、构造方法详解

1. 无参构造函数

public LinkedList() {}

• 初始化时 first 和 last 均为 null，size 为 0，表示链表为空。

2. 带初始集合的构造函数

public LinkedList(Collection<? extends E> c) {this();addAll(c);
}

• 调用无参构造函数后，通过 addAll() 方法将集合元素逐个添加到链表尾部。

.

四、插入操作详解

1. 尾部插入：add(E e)

public boolean add(E e) {linkLast(e);return true;
}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;elsel.next = newNode;size++;modCount++;
}

• 关键步骤：
  1. 获取当前尾节点 l
  2. 创建新节点 newNode，其 prev 指向 l，next 为 null。
  3. 更新 last 为 newNode。
  4. 如果链表为空（l == null），则 first 和 last 均指向 newNode。
  5. 否则，将原尾节点的 next 指向 newNode。
  6. 更新 size 和 modCount（结构修改计数器，用于迭代器的 fail-fast 机制）。

2. 头部插入：addFirst(E e)

private void linkFirst(E e) {final Node<E> f = first;final Node<E> newNode = new Node<>(null, e, f);first = newNode;if (f == null)last = newNode;elsef.prev = newNode;size++;modCount++;
}

• 关键步骤：
  1. 获取当前头节点 f。
  2. 创建新节点 newNode，其 next 指向 f，prev 为 null。
  3. 更新 first 为 newNode。
  4. 如果链表为空（f == null），则 first 和 last 均指向 newNode。
  5. 否则，将原头节点的 prev 指向 newNode。

3. 中间插入：add(int index, E element)

public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));
}

• 关键步骤：
  1. 检查索引合法性（0 ≤ index ≤ size）。
  2. 如果 index == size，调用 linkLast() 插入尾部。
  3. 否则，调用 node(index) 找到目标节点，再调用 linkBefore() 插入到该节点前。

linkBefore(E e, Node succ)

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;elsepred.next = newNode;size++;modCount++;
}

• 关键步骤：
  1. 获取目标节点 succ 的前驱节点 pred。
  2. 创建新节点 newNode，其 prev 指向 pred，next 指向 succ。
  3. 更新 succ.prev 为 newNode。
  4. 如果 pred == null（即插入到头部），更新 first。
  5. 否则，将 pred.next 指向 newNode。

.

五、删除操作详解

1. 删除指定元素：remove(Object o)

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;
}

• 关键步骤：
  1. 遍历链表查找匹配的节点。
  2. 找到后调用 unlink(x) 删除节点。

unlink(Node x)

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;x.prev = null;}if (next == null) {last = prev;} else {next.prev = prev;x.next = null;}x.item = null;size--;modCount++;return element;
}

• 关键步骤：
  1. 获取被删除节点 x 的前后节点 prev 和 next。
  2. 如果 prev == null，说明 x 是头节点，更新 first 为 next。
  3. 否则，将 prev.next 指向 next，并断开 x.prev。
  4. 如果 next == null，说明 x 是尾节点，更新 last 为 prev。
  5. 否则，将 next.prev 指向 prev，并断开 x.next。
  6. 将 x.item 置为 null，帮助 GC 回收。
  7. 更新 size 和 modCount。

2. 删除头节点：removeFirst()

private E unlinkFirst(Node<E> f) {final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null;first = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;
}

• 关键步骤：
  1. 获取头节点 f 的 item 和 next。
  2. 断开 f 的引用（f.item = null、f.next = null）。
  3. 更新 first 为 next。
  4. 如果 next == null，说明链表为空，更新 last 为 null。
  5. 否则，将 next.prev 置为 null。

.

六、访问操作详解

1. 按索引访问：get(int index)

public E get(int index) {checkElementIndex(index);return node(index).item;
}Node<E> node(int index) {if (index < (size >> 1)) {Node<E> x = first;for (int i = 0; i < index; i++)x = x.next;return x;} else {Node<E> x = last;for (int i = size - 1; i > index; i--)x = x.prev;return x;}
}

• 关键步骤：

  1. 根据索引位置选择从头节点或尾节点开始遍历。
  2. 如果 index < size/2，从头节点向后遍历；否则，从尾节点向前遍历。
  3. 返回对应节点的 item。

• 时间复杂度：O(n)，因为需要遍历链表。

.

七、线程安全与 Fail-Fast 机制

1. 线程不安全

LinkedList 不是线程安全的，多线程环境下可能导致数据不一致或 ConcurrentModificationException。

2. Fail-Fast 机制

• 通过 modCount 记录结构修改次数（如 add、remove）。
• 迭代器遍历时会检查 modCount 是否与创建迭代器时的值一致。如果不一致，抛出 ConcurrentModificationException。

示例代码

public Iterator<E> iterator() {return new Itr();
}private class Itr implements Iterator<E> {int expectedModCount = modCount;public boolean hasNext() {checkForComodification();return cursor != size;}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}
}

.

八、性能对比与使用建议

使用建议

• 频繁插入/删除：优先使用 LinkedList（尤其是头部或尾部操作）。
• 频繁随机访问：优先使用 ArrayList。
• 线程安全：使用 Collections.synchronizedList(new LinkedList<>()) 或 CopyOnWriteArrayList。
• 双端队列：LinkedList 实现了 Deque 接口，可作为双端队列使用（如栈、队列）。

.

九、扩展学习建议

1. 源码调试：使用 IDE（如 IntelliJ IDEA）调试 LinkedList 的 add、remove、get 方法，观察 first、last、size 的变化。
2. 版本差异：对比 JDK 8 和 JDK 21 的 LinkedList 源码，观察是否引入新的优化（如 Spliterator 支持）。
3. 进阶主题：
   • LinkedList 与 Vector 的区别（线程安全 vs 性能）。
   • Deque 接口的实现细节（如 ArrayDeque 与 LinkedList 的对比）。
   • LinkedList 在 JVM 内存模型中的表现（链表的离散性 vs 数组的连续性）。