一、引言LinkedList是 Java 集合框架中基于双向链表实现的重要数据结构。理解其内部实现细节特别是各种操作的实现原理有助于避免常见的空指针异常并对链表的优缺点形成更全面的认识。本文将通过源码分析深入探讨 LinkedList 的核心实现机制。二、继承关系与整体结构2.1 继承关系图与 ArrayList 相比LinkedList 实现了 List 和 Deque 接口支持双向队列操作。2.2 核心数据结构LinkedList 中的每个元素都存储在 Node 节点中Node 是一个典型的双向链表节点结构private static class NodeE { E item; // 存储元素 NodeE next; // 指向下一个元素 NodeE prev; // 指向上一个元素 Node(Nodelt;Egt; prev, E element, Nodelt;Egt; next) { this.item element; this.next next; this.prev prev; } }2.3 成员变量LinkedList 主要维护三个核心变量transient int size 0; // 当前列表的元素个数 /** Pointer to first node. Invariant: (first null last null) || (first.prev null amp;amp; first.item ! null) */ transient NodeE first; // 第一个元素 /** Pointer to last node. Invariant: (first null last null) || (last.next null amp;amp; last.item ! null) */ transient NodeE last; // 最后一个元素三、构造函数与初始化LinkedList 提供两个构造函数public LinkedList() {} // 无参构造函数 public LinkedList(Collection? extends E c) { this(); addAll(c); // 将集合c中的所有元素添加到列表中 }四、核心操作方法4.1 批量添加元素addAll() 方法支持在指定位置批量添加元素public boolean addAll(Collection? extends E c) { return addAll(size, c); // 默认添加到末尾 } public boolean addAll(int index, Collection? extends E c) { checkPositionIndex(index); // 检查位置合法性 [0, size] Object[] a c.toArray(); int numNew a.length; if (numNew 0) return false; Nodelt;Egt; pred, succ; // 前驱与后继节点 if (index size) { // 添加到末尾 succ null; pred last; } else { // 添加到中间位置 succ node(index); // 获取index位置的节点作为后继 pred succ.prev; // 后继的前驱作为前驱 } // 逐个插入新节点 for (Object o : a) { SuppressWarnings(unchecked) E e (E) o; Nodelt;Egt; newNode new Nodelt;gt;(pred, e, null); if (pred null) first newNode; else pred.next newNode; pred newNode; } // 连接剩余部分 if (succ null) { last pred; } else { pred.next succ; succ.prev pred; } size numNew; modCount; return true; }4.2 节点查找优化node() 方法通过二分查找优化节点访问NodeE node(int index) { // 根据index与中间位置的比较决定从前还是从后遍历 if (index (size 1)) { // 在前半部分 NodeE x first; for (int i 0; i index; i) x x.next; return x; } else { // 在后半部分 NodeE x last; for (int i size - 1; i index; i--) x x.prev; return x; } }4.3 测试示例public class Main { public static void main(String[] args) { ListString list new LinkedList(Arrays.asList(1, 2, 3)); System.out.println(list.toString()); // [1, 2, 3] list.addAll(2, Arrays.asList(4, 5)); System.out.println(list.toString()); // [1, 2, 4, 5, 3] list.addAll(0, Arrays.asList(6, 7)); System.out.println(list.toString()); // [6, 7, 1, 2, 4, 5, 3] } }五、元素添加操作5.1 基本添加方法LinkedList 提供了三个核心的链接方法5.1.1 链接到头部private void linkFirst(E e) { final NodeE f first; final NodeE newNode new Node(null, e, f); first newNode; if (f null) last newNode; else f.prev newNode; size; modCount; }5.1.2 链接到尾部void linkLast(E e) { final NodeE l last; final NodeE newNode new Node(l, e, null); last newNode; if (l null) first newNode; else l.next newNode; size; modCount; }5.1.3 链接到指定节点前void linkBefore(E e, NodeE succ) { final NodeE pred succ.prev; final NodeE newNode new Node(pred, e, succ); succ.prev newNode; if (pred null) first newNode; else pred.next newNode; size; modCount; }5.2 公共添加接口public boolean add(E e) { linkLast(e); return true; } public void add(int index, E element) { checkPositionIndex(index); if (index size) linkLast(element); else linkBefore(element, node(index)); } public void addFirst(E e) { linkFirst(e); } public void addLast(E e) { linkLast(e); }六、元素删除操作6.1 核心删除方法6.1.1 删除首节点private E unlinkFirst(NodeE f) { final E element f.item; final NodeE next f.next; f.item null; f.next null; // help GC first next; if (next null) last null; else next.prev null; size--; modCount; return element; }6.1.2 删除尾节点private E unlinkLast(NodeE l) { final E element l.item; final NodeE prev l.prev; l.item null; l.prev null; // help GC last prev; if (prev null) first null; else prev.next null; size--; modCount; return element; }6.1.3 删除任意节点E unlink(NodeE x) { final E element x.item; final NodeE next x.next; final NodeE 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; }6.2 公共删除接口public E removeFirst() { final NodeE f first; if (f null) throw new NoSuchElementException(); return unlinkFirst(f); } public E removeLast() { final NodeE l last; if (l null) throw new NoSuchElementException(); return unlinkLast(l); } public boolean remove(Object o) { if (o null) { for (NodeE x first; x ! null; x x.next) { if (x.item null) { unlink(x); return true; } } } else { for (NodeE x first; x ! null; x x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } public E remove(int index) { checkElementIndex(index); return unlink(node(index)); }七、元素修改与查询7.1 修改元素public E set(int index, E element) { checkElementIndex(index); NodeE x node(index); E oldVal x.item; x.item element; return oldVal; }7.2 查询元素public E get(int index) { checkElementIndex(index); return node(index).item; } public E getFirst() { final NodeE f first; if (f null) throw new NoSuchElementException(); return f.item; } public E getLast() { final NodeE l last; if (l null) throw new NoSuchElementException(); return l.item; }7.3 查找元素位置public int indexOf(Object o) { int index 0; if (o null) { for (NodeE x first; x ! null; x x.next) { if (x.item null) return index; index; } } else { for (NodeE x first; x ! null; x x.next) { if (o.equals(x.item)) return index; index; } } return -1; } public int lastIndexOf(Object o) { int index size; if (o null) { for (NodeE x last; x ! null; x x.prev) { index--; if (x.item null) return index; } } else { for (NodeE x last; x ! null; x x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }八、边界检查与工具方法// 下标检查保证数组访问不越界 [0, size) private boolean isElementIndex(int index) { return index 0 index size; } // 位置检查用于插入操作 [0, size] private boolean isPositionIndex(int index) { return index 0 index size; }九、总结与扩展LinkedList 作为双向链表的实现在插入和删除操作上具有 O(1) 的时间复杂度已知节点位置时但随机访问需要 O(n) 的时间。它还实现了 Queue 接口支持队列操作。在实际使用中需要根据具体场景选择合适的数据结构。关于序列化和迭代器的实现与 ArrayList 有所不同可以参考 ArrayList 的相关解析进行对比学习。