為什么 Java 的 LinkedList 的雙鏈表實現不會鏈接后面元素

問題描述

JDK7中 LinkedList private 方法 private void linkFirst(E e)在新添加元素時鏈表不會斷裂?

代碼來源于 JDK7

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;else f.prev = newNode; // 此處沒有執行 newNode.next = f; newNode.next 不會鏈接后面的元素size++;modCount++; }

問題解答

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

final Node<E> newNode = new Node<>(null, e, f); // 構造函數的第3個參數不就是 next 元素了?；卮?：

為什么會斷鏈呢？f指向原來的first，將新的newNode設置為first。這個時候就判斷，如果原來的鏈表就是空的，那么last也就是first咯。如果不為空，那么就是將f<原來的首節點>的prev就指向first。

我猜你之所以覺得會斷鏈是因為，你沒看到first的next指向f。額next這個在Node中已經傳進去了final Node<E> newNode = new Node<>(null, e, f);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; }}