Java集合-03-LinkedList源码：Node结构、双向链表与Deque定位

结论先行双向链表 DequeLinkedList 是 Java 集合框架中基于双向链表实现的 List同时实现了 Deque 接口因此既可以当列表用也可以当双端队列或栈用。它的底层由一个个 Node 节点通过 prev 和 next 指针串联而成每个节点只知道自己前一个和后一个邻居并不知道整个链表的全貌。正因为这种结构LinkedList 的头尾增删是 O(1)但随机访问是 O(n)中间插入也并非“一定快”——它要先从头或尾遍历到目标位置再执行指针操作。所以“LinkedList 增删快”这句话是有前提的不能无脑套用。核心结构NodeELinkedList 内部定义了一个静态内部类 Node它是整个链表的基石private static class NodeE { E item; // 当前节点存储的数据 NodeE next; // 指向后继节点 NodeE prev; // 指向前驱节点 Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } }每个节点有三个字段item 存数据prev 指向前一个节点next 指向后一个节点。链表本身只维护两个引用first 指向头节点last 指向尾节点以及 size 记录节点数量。双向链表结构示意flowchart LR A[first] -- B[Node1 itemA prevnull nextNode2] B -- C[Node2 itemB prevNode1 nextNode3] C -- D[Node3 itemC prevNode2 nextnull] D -- E[last] B -.-|prev| A C -.-|prev| B D -.-|prev| C从图中可以看到first 和 last 只是两个引用真正的数据都挂在 Node 上。头节点的 prev 为 null尾节点的 next 为 null这是链表遍历的终止条件。构造方法LinkedList 提供了两个构造方法public LinkedList() { } public LinkedList(Collection? extends E c) { this(); addAll(c); }无参构造直接创建一个空链表first 和 last 都为 null。传入集合的构造方法会调用 addAll 把集合元素逐个链接成链表顺序与集合的迭代顺序一致。添加linkFirst、linkLast、linkBeforeLinkedList 的添加操作最终都落到三个私有方法上它们负责真正的指针操作。linkFirst头插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; }头插的逻辑新建一个节点prev 为 nullnext 指向原头节点。如果原链表为空则新节点同时是头也是尾否则把原头节点的 prev 指向新节点。整个过程只操作常数个引用时间复杂度 O(1)。linkLast尾插private 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; }尾插与头插对称新节点的 prev 指向原尾节点next 为 null然后更新 last 引用。空链表时新节点同时成为头和尾。这也是 O(1) 操作。linkBefore在指定节点前插入private 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; }linkBefore 是中间插入的核心。它接收两个参数要插入的元素 e以及一个已经定位好的节点 succ新节点会插在 succ 前面。整个过程只改三个节点的引用本身是 O(1)但前提是 succ 已经找到。linkBefore 插入示意图flowchart LR A[Node1] -- B[Node2] B -- C[Node3] N[newNode] -.-|插入前| B A --|prev.next 改为 newNode| N N --|newNode.next 指向 Node2| B B --|Node2.prev 改为 newNode| N N --|newNode.prev 指向 Node1| A插入后 Node1 的 next 指向 newNodenewNode 的 next 指向 Node2Node2 的 prev 指向 newNodenewNode 的 prev 指向 Node1。原来的 Node1 和 Node2 之间的连接被 newNode 取代。add(int, E)先找节点再插入public void add(int index, E element) { checkPositionIndex(index); if (index size) linkLast(element); else linkBefore(element, node(index)); }add(int, E) 的逻辑很清晰如果 index 等于 size直接尾插否则先调用 node(index) 找到该位置的节点再调用 linkBefore 插到它前面。这里的 node(index) 就是 O(n) 的遍历所以中间插入的总成本是 O(n)而不是 O(1)。删除unlinkFirst、unlinkLast、unlink删除操作同样由三个私有方法完成核心是断开目标节点的引用让 GC 可以回收它。unlinkFirst删除头节点private E unlinkFirst(NodeE f) { final E element f.item; final NodeE next f.next; f.item null; f.next null; first next; if (next null) last null; else next.prev null; size--; modCount; return element; }删除头节点先保存原头节点的数据和 next 引用然后把原头节点的 item 和 next 置空帮助 GC。接着更新 first 为原 next。如果链表只有一个节点删除后 last 也要置空否则把新头节点的 prev 置为 null。O(1) 操作。unlinkLast删除尾节点private E unlinkLast(NodeE l) { final E element l.item; final NodeE prev l.prev; l.item null; l.prev null; last prev; if (prev null) first null; else prev.next null; size--; modCount; return element; }与 unlinkFirst 对称删除尾节点时把 last 更新为原 prev并把新尾节点的 next 置空。同样是 O(1)。unlink删除中间节点private 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; }unlink 删除中间节点把前驱节点的 next 直接指向后继节点把后继节点的 prev 直接指向前驱节点然后清空被删节点的三个字段。如果删除的是头或尾需要额外更新 first 或 last。指针操作本身是 O(1)但调用方需要先通过遍历找到这个节点。unlink 删除示意图flowchart LR A[Node1] -- B[Node2 待删除] B -- C[Node3] A --|next 改为 Node3| C C --|prev 改为 Node1| A B -.-|item/prev/next 置空| X[GC 回收]删除后 Node1 的 next 直接指向 Node3Node3 的 prev 直接指向 Node1Node2 从链表中脱离等待 GC 回收。remove(Object) 和 remove(int)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)); }remove(Object) 需要从头遍历链表找到第一个匹配的节点再调用 unlink时间复杂度 O(n)。remove(int) 先通过 node(index) 定位再 unlink同样是 O(n)。查询get(int) 与 node(int) 的二分优化public E get(int index) { checkElementIndex(index); return node(index).item; } NodeE node(int 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; } }node(int) 是 LinkedList 随机访问的核心方法它做了一个小优化如果 index 小于 size 的一半就从头部往后找否则从尾部往前找。这样最坏情况只需要遍历 size/2 个节点但时间复杂度仍然是 O(n)。为什么随机访问是 O(n)因为链表没有下标节点之间只通过指针相连。要访问第 index 个节点必须从 first 或 last 出发沿着 next 或 prev 逐个跳转无法像数组那样通过首地址加偏移量直接计算内存位置。即使有二分优化也只是把常数因子减半量级不变。Deque 能力addFirst、addLast、pollFirst、pollLastLinkedList 实现了 Deque 接口因此具备双端队列的能力。这些方法大多直接复用前面提到的 linkFirst、linkLast、unlinkFirst、unlinkLastpublic void addFirst(E e) { linkFirst(e); } public void addLast(E e) { linkLast(e); } public E pollFirst() { final NodeE f first; return (f null) ? null : unlinkFirst(f); } public E pollLast() { final NodeE l last; return (l null) ? null : unlinkLast(l); }addFirst 和 addLast 都是 O(1)pollFirst 和 pollLast 也都是 O(1)。这使得 LinkedList 可以当作栈或队列使用栈用 push等价 addFirst和 pop等价 removeFirst队列用 offer等价 addLast和 poll等价 pollFirst。不过这里有一个重要的对比ArrayDeque 通常比 LinkedList 更适合做栈和队列。ArrayDeque 基于循环数组实现头尾操作同样是 O(1)但内存连续、CPU 缓存友好且不需要维护 Node 对象内存占用更小。LinkedList 只有在需要频繁在中间插入删除或者需要同时利用 List 和 Deque 双重能力时才有优势。ArrayList vs LinkedList两者都是 List 接口的实现但底层结构完全不同适用场景也截然不同。下面从几个维度对比维度ArrayListLinkedList底层结构动态数组双向链表内存占用连续内存可能有预留容量每个节点额外存 prev 和 next 引用随机访问 get/setO(1)O(n)头尾插入删除尾插 O(1)均摊头插 O(n)O(1)中间插入删除O(n)移动元素O(n)先遍历定位CPU 缓存局部性好元素连续存储差节点分散在堆中迭代器遍历快相对慢内存占用方面ArrayList 只存数据本身虽然可能预留一些容量但整体是紧凑的连续内存。LinkedList 每个 Node 除了 item 还要存两个引用在 64 位 JVM 上开启压缩指针后一个 Node 大约占 24 字节左右比单纯存一个引用多得多。数据量越大LinkedList 的内存开销越明显。随机访问方面ArrayList 通过下标直接计算内存地址O(1)LinkedList 需要从头或尾遍历O(n)。这是两者最本质的差异。头尾插入方面LinkedList 的 linkFirst 和 linkLast 都是 O(1)ArrayList 尾插均摊 O(1)但头插需要把所有元素后移O(n)。所以如果业务是频繁在头部插入LinkedList 有明显优势。中间插入方面两者都是 O(n)但代价不同。ArrayList 是移动元素LinkedList 是遍历定位。移动元素是内存拷贝遍历定位是指针跳转。在数据量较大时ArrayList 的移动可能因为 memcpy 优化反而更快而 LinkedList 的指针跳转对 CPU 缓存不友好。所以“LinkedList 中间插入快”是常见的误区。CPU 缓存局部性方面ArrayList 的元素在内存中连续排列遍历时 CPU 可以预取相邻数据缓存命中率高。LinkedList 的节点分散在堆的不同位置每次跳转都可能触发缓存未命中遍历性能明显更差。使用场景与面试题什么时候该用 LinkedList需要频繁在头部或尾部插入删除且不需要随机访问。需要同时使用 List 和 Deque 的能力例如既要按下标遍历又要当队列用。数据量较小且插入删除集中在两端。什么时候不该用 LinkedList需要频繁随机访问例如 for 循环按下标 get。数据量大且需要遍历ArrayList 的缓存局部性优势明显。需要做栈或队列ArrayDeque 通常是更好的选择。面试题LinkedList 增删一定快吗不一定。头尾增删是 O(1)确实快但中间增删需要先遍历定位整体是 O(n)并不比 ArrayList 快。而且 ArrayList 的中间插入是内存移动LinkedList 是指针跳转在数据量大时 ArrayList 可能反而更快。所以正确的说法是LinkedList 在头尾增删场景下有优势中间增删没有优势。面试题LinkedList