Java 集合框架中的 LinkedList 类

一、介绍

双向链表实现了 List 和 Deque 接口。它实现了所有可选的列表操作，并允许所有类型的元素（包括 null）。所有操作的性能都符合对双向链表的预期。对于那些需要索引列表的操作，链表会根据指定索引靠近列表起点或终点的情况，从起点或终点开始遍历。

需要注意的是，这个实现并不是线程安全的。如果多个线程同时访问一个链表，并且至少有一个线程对链表进行了结构性修改，则必须通过外部同步来确保线程安全。结构性修改指的是添加或删除一个或多个元素的操作；仅仅设置元素的值不属于结构性修改。通常的做法是对封装链表的某个对象进行同步。如果没有这样的对象存在，链表应当使用 Collections.synchronizedList 方法进行“包装”。最好在链表创建时进行包装，以防止意外的非同步访问：

List list = Collections.synchronizedList(new LinkedList(...));

这个类的 iterator 和 listIterator 方法返回的迭代器是快速失败的（fail-fast）：如果在迭代器创建后，链表被结构性修改了（除了通过迭代器自身的 remove 或 add 方法进行的修改外），迭代器会抛出 ConcurrentModificationException。因此，在并发修改的情况下，迭代器会迅速而干净地失败，而不是在未来的不确定时间内面临任意的、不可预测的行为。

需要注意的是，迭代器的快速失败行为无法得到保证，因为在未同步的并发修改情况下，一般来说无法做出任何硬性保证。快速失败的迭代器是在“尽力而为”的基础上抛出 ConcurrentModificationException。因此，编写依赖于该异常来确保正确性的程序是错误的做法：迭代器的快速失败行为应仅用于检测程序中的错误。

二、源码

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

}

1、基础节点

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

LinkedList 中定了内部类 Node，用来表示链表中的节点。提供属性如下：

• item，节点所存储数据
• next，下一个节点
• prer，上一个节点

2、属性

transient int size = 0;

transient Node<E> first;  

transient Node<E> last;

• size，当前链表中存储的元素数量
• first，链表中的第一个节点
• last，链表中的最后一个节点

3、构造方法

public LinkedList() {  
}

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

相较于 ArrayList，LinkedList 没有提供入参为初始化容量的构造方法，相应的方法在 ArrayList 中为 public ArrayList(int initialCapacity)。

4、实现 Deque 接口方法

void addFirst(E e);

void addLast(E e);

boolean offerFirst(E e);

boolean offerLast(E e);

E removeFirst();

E removeLast();

E pollFirst();

E pollLast();

E getFirst();

E getLast();

E peekFirst();

E peekLast();

boolean removeFirstOccurrence(Object o);

boolean removeLastOccurrence(Object o);

关于双端队列 Deque 的内容，请参考 [[Deque]]

4.1 addFirst

该方法在此链表的开头插入指定的元素。

public void addFirst(E e) {  
    linkFirst(e);  
}

4.2 addLast

该方法在链表的结尾插入指定元素。

public void addLast(E e) {  
    linkLast(e);  
}

4.3 offerFirst

public boolean offerFirst(E e) {  
    addFirst(e);  
    return true;  
}

4.4 offerLast

public boolean offerLast(E e) {  
    addLast(e);  
    return true;  
}

4.5 removeFirst

删除并返回此列表中的第一个元素。

public E removeFirst() {  
    final Node<E> f = first;  
    if (f == null) {  
        throw new NoSuchElementException();  
    }  
    return unlinkFirst(f);  
}

4.6 removeLast

删除并返回此列表中的最后一个元素。

public E removeLast() {  
    final Node<E> l = last;  
    if (l == null) {  
        throw new NoSuchElementException();  
    }  
    return unlinkLast(l);  
}

4.7 pollFirst

检索并删除此列表的第一个元素，如果此列表为空，则返回 null。

public E pollFirst() {  
    final Node<E> f = first;  
    return (f == null) ? null : unlinkFirst(f);  
}

4.8 pollLast

检索并删除此列表的最后一个元素，如果此列表为空，则返回 null。

public E pollLast() {  
    final Node<E> l = last;  
    return (l == null) ? null : unlinkLast(l);  
}

4.9 getFirst

返回此列表中的第一个元素。

public E getFirst() {  
    final Node<E> f = first;  
    if (f == null) {  
        throw new NoSuchElementException();  
    }  
    return f.item;  
}

4.10 getLast

返回此列表中的最后一个元素。

public E getLast() {  
    final Node<E> l = last;  
    if (l == null) {  
        throw new NoSuchElementException();  
    }  
    return l.item;  
}

4.11 peekFirst

检索但不删除此列表的第一个元素，如果此列表为空，则返回 null。

public E peekFirst() {  
    final Node<E> f = first;  
    return (f == null) ? null : f.item;  
 }

4.12 peekLast

检索但不删除此列表的最后一个元素，如果此列表为空，则返回null。

public E peekLast() {  
    final Node<E> l = last;  
    return (l == null) ? null : l.item;  
}

5、实现 Queue 接口方法

boolean add(E e);

boolean offer(E e);

E remove();

E poll();

E element();

E peek();

5.1 add

将指定元素附加到此列表的末尾。此方法等效于 addLast。

public boolean add(E e) {  
    linkLast(e);  
    return true;  
}

5.2 offer

将指定元素添加为此列表的尾部（最后一个元素）。

public boolean offer(E e) {  
    return add(e);  
}

5.3 remove

检索并删除此列表的头部（第一个元素）。

public E remove() {  
    return removeFirst();  
}

5.4 poll

检索并删除此列表的头部（第一个元素）。

public E poll() {  
    final Node<E> f = first;  
    return (f == null) ? null : unlinkFirst(f);  
}

5.5 element

检索但不删除此列表的头部（第一个元素）。

public E element() {  
    return getFirst();  
}

5.6 peek

检索但不删除此列表的头部（第一个元素）。

public E peek() {  
    final Node<E> f = first;  
    return (f == null) ? null : f.item;  
}

6、实现 Collection 接口方法

6.1 contains

如果此列表包含指定元素，则返回 true。

更正式地说，当且仅当此列表包含至少一个元素 e 满足 Objects.equals(o, e) 时，返回 true。

public boolean contains(Object o) {  
    return indexOf(o) >= 0;  
}

6.2 toArray 方法

Object[] toArray();
    
<T> T[] toArray(T[] a);

6.2.1 Object[] toArray(); 方法

返回一个包含此列表中所有元素的数组，元素按正确的顺序排列（从第一个到最后一个元素）。

返回的数组是“安全的”，因为此列表不会保留对该数组的引用。（换句话说，此方法必须分配一个新的数组）。因此，调用者可以自由地修改返回的数组。

此方法在基于数组的 API 和基于集合的 API 之间起到桥梁作用。

public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    // 从链表首节点遍历链表直到链表结尾
    for (Node<E> x = first; x != null; x = x.next) {
        // 数组元素赋值
        result[i++] = x.item;
    }
    return result;
}

6.2.2 <T> T[] toArray(T[] a); 方法

public <T> T[] toArray(T[] a) {
    // 如果入参数组的长度小于链表的容量，则需要创建一个长度为链表容量的数组
    if (a.length < size) {
        a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
    }
    int i = 0;
    Object[] result = a;
    // 循环遍历链表，数组元素赋值
    for (Node<E> x = first; x != null; x = x.next) {
        result[i++] = x.item;
    }
    // 如果数组长度大于链表元素数量，则将多余位置赋值为 null
    if (a.length > size) {
        a[size] = null;
    }

    return a;
}

6.3 add

Java 集合框架中的 LinkedList 类 | z2huo

6.4 remove

public boolean remove(Object o) {  
    if (o == null) {  
        // 当入参对象为 null 时  
        // 从链表首节点开始往后遍历，直到遍历到列表结尾或查找到存储数据为 null 的节点为止  
        for (Node<E> x = first; x != null; x = x.next) {  
            if (x.item == null) {  
                unlink(x);  
                return true;  
            }  
        }  
    } else {  
        // 当入参对象不为 null 时  
        // 从链表首节点开始往后遍历，直到遍历到列表结尾或查找到存储数据与入参对象相等的节点为止 
        for (Node<E> x = first; x != null; x = x.next) {  
            if (o.equals(x.item)) {  
                unlink(x);  
                return true;  
            }  
        }  
    }  
    return false;  
}

6.5 addAll 方法

将指定集合中的所有元素按其迭代器返回的顺序追加到此列表的末尾。

如果在操作进行过程中修改了指定的集合，则此操作的行为是未定义的。注意，如果指定的集合是此列表自身并且它非空，则会发生这种情况。

public boolean addAll(Collection<? extends E> c) {  
    return addAll(size, c);  
}

6.6 containAll 方法

继承自 AbstractCollection 抽象类中的 containAll 方法

6.7 removeAll 方法

继承自 AbstractCollection 抽象类中的 removeAll 方法

6.8 retainAll 方法

继承自 AbstractCollection 抽象类中的 retainAll 方法

6.9 clear 方法

删除此列表中的所有元素。此调用返回后，列表将为空。

public void clear() {
    // 清除节点之间的所有链接是“不必要的”，
    // 但是：如果丢弃的节点存在多代，则有助于一代GC
    // 即使有可访问的迭代器，也一定会释放内存
    
    // 从链表首节点开始遍历，将节点存储的数据、前置节点、后置节点赋值为 null，直到链表末尾
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    // 链表首节点、尾结点赋值为 null
    first = last = null;
    // 容量赋值为 0
    size = 0;
    modCount++;
}

7、实现 List 接口方法

7.1 搜索元素操作

7.1.1 indexOf

返回指定元素在此列表中首次出现的索引，如果此列表不包含该元素，则返回 -1。

更正式地说，返回满足 Objects.equals(o, get(i)) 的最低索引 i，如果没有这样的索引，则返回 -1。

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        // 当入参对象为 null 时
        // 从链表第一个节点开始往后循环遍历，循环直到找到存储数据为 null 的节点或遍历到链表末尾为止
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                return index;
            }
            // 索引加 1
            index++;
        }
    } else {
        // 当入参对象不为 null 时
        // 从链表第一个节点开始往后循环遍历，循环直到找到存储数据与入参对象相等的节点或遍历到链表末尾为止
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                return index;
            }
            // 索引加 1
            index++;
        }
    }
    return -1;
}

7.1.2 lastIndexOf

返回指定元素在此列表中最后一次出现的索引，如果此列表不包含该元素，则返回 -1。

更正式地说，返回满足 Objects.equals(o, get(i)) 的最高索引 i，如果没有这样的索引，则返回 -1。

public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null) {
                return index;
            }
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item)) {
                return index;
            }
        }
    }
    return -1;
}

lastIndexOf 方法内部逻辑与 indexOf 大体相同，前者从后往前遍历链表，后者从前往后遍历链表。

7.2 addAll 方法

boolean addAll(int index, Collection<? extends E> c) 方法将指定集合中的所有元素插入到此列表中的指定位置。从该位置开始的元素（如果有）以及所有后续元素将向右移动（它们的索引增加）。新元素将按照指定集合的迭代器返回的顺序出现在列表中。

public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    // 待添加集合底层数组
    Object[] a = c.toArray();
    // 待添加集合底层数组长度
    int numNew = a.length;
    // 如果待添加集合中没有元素，直接返回 false
    if (numNew == 0) {
        return false;
    }

    // 待添加位置的前一位的节点
    Node<E> pred;
    // 待添加位置的节点
    Node<E> succ;
    // 如果待添加位置为当前链表的末尾
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    // 遍历待添加数组
    for (Object o : a) {
        @SuppressWarnings("unchecked")
        E e = (E) o;
        // 创建新节点，前置节点为 pred，后置节点为 null
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null) {
            // 如果 pred 为 null，表示待添加位置为链表开头位置
            first = newNode;
        } else {
            // 如果 pred 不为 null，将新节点接到链表中
            pred.next = newNode;
        }
        // pred 重新赋值为新创建的节点
        pred = newNode;
    }
    
    if (succ == null) {
        // 如果待添加位置元素为 null，表示添加元素位置为链表末尾
        // last 赋值为 pred，pred 为添加完数组后的最后一个节点
        last = pred;
    } else {
        // 如果待添加位置元素不为 null
        // 将原链表拼接到添加完数组后的最后一个元素上
        pred.next = succ;
        succ.prev = pred;
    }

    // 链表容量增加
    size += numNew;
    modCount++;
    return true;
}

7.3 get 方法

返回此列表中指定位置的元素。

public E get(int index) {  
    checkElementIndex(index);  
    return node(index).item;  
}

7.4 set 方法

将此列表中指定位置的元素替换为指定元素。

public E set(int index, E element) {  
    checkElementIndex(index);  
    Node<E> x = node(index);  
    E oldVal = x.item;  
    // 替换节点存储数据  
    x.item = element;  
    return oldVal;  
}

7.5 add 方法

在此列表中的指定位置插入指定元素。将当前位于该位置的元素（如果有的话）和任何后续元素向右移动（将其索引加一）。

public void add(int index, E element) {  
    checkPositionIndex(index);  
  
    if (index == size) {  
        // 当插入位置为列表末尾  
        linkLast(element);  
    } else {  
        // 当插入位置不在列表末尾  
        linkBefore(element, node(index));  
    }  
}

7.6 remove 方法

删除此列表中指定位置的元素。将任何后续元素向左移动（从其索引中减去一）。返回从列表中删除的元素。

public E remove(int index) {  
    checkElementIndex(index);  
    return unlink(node(index));  
}

8、迭代器

iterator() 方法继承自 AbstractSequentialList 抽象类，其中调用了 listIterator() 方法。

public Iterator<E> iterator() {  
    return listIterator();  
}

8.1 列表迭代器

LinkedList 中提供了返回列表迭代器的方法。

public ListIterator<E> listIterator(int index) {  
    checkPositionIndex(index);  
    return new ListItr(index);  
}

另外还有继承自 AbstractList 的返回列表迭代器的方法。

public ListIterator<E> listIterator() {  
    return listIterator(0);  
}

LinkedList 中的列表迭代器 ListItr 源码如下：

private class ListItr implements ListIterator<E> {  
    // 最后返回的节点  
    private Node<E> lastReturned;  
    // 下一个节点  
    private Node<E> next;  
    // 下一个节点的索引  
    private int nextIndex;  
    private int expectedModCount = modCount;  
  
    ListItr(int index) {  
        // index 在链表边界范围内  
        // assert isPositionIndex(index);  
        next = (index == size) ? null : node(index);  
        nextIndex = index;  
    }  
  
    public boolean hasNext() {  
        return nextIndex < size;  
    }  
  
    public E next() {  
        checkForComodification();  
        if (!hasNext()) {  
            throw new NoSuchElementException();  
        }  
  
        lastReturned = next;  
        // next 为当前节点的下一个节点  
        next = next.next;  
        // 下一个节点的索引递增  
        nextIndex++;  
        // 返回节点存储的数据  
        return lastReturned.item;  
    }  
  
    public boolean hasPrevious() {  
        return nextIndex > 0;  
    }  
  
    public E previous() {  
        checkForComodification();  
        if (!hasPrevious()) {  
            throw new NoSuchElementException();  
        }  
  
        // 如果 next 为 null，表示当前游标位置为链表最后一个节点后，返回节点为链表最后一个节点  
        // 如果 next 不为 null，表示当前游标位置不为链表最后一个节点，返回节点为游标位置的前置节点  
        lastReturned = next = (next == null) ? last : next.prev;  
        nextIndex--;  
        return lastReturned.item;  
    }  
  
    public int nextIndex() {  
        return nextIndex;  
    }  
  
    public int previousIndex() {  
        return nextIndex - 1;  
    }  
  
    /**  
     * remove 方法会从列表中删除 next 或 previous 方法返回的最后一个  
     */  
    public void remove() {  
        checkForComodification();  
        if (lastReturned == null) {  
            throw new IllegalStateException();  
        }  
  
        // 游标所处位置后的节点的后置节点  
        Node<E> lastNext = lastReturned.next;  
        // 将最后返回的节点从链表中解除链接  
        unlink(lastReturned);  
        if (next == lastReturned) {  
            // 调用 previous 后，next == lastReturned  
            next = lastNext;  
        } else {  
            // 调用 next 后  
            nextIndex--;  
        }  
        lastReturned = null;  
        expectedModCount++;  
    }  
  
    /**  
     * set 方法将 next 或 previous 方法返回的最后一个元素替换为指定的元素  
     */  
    public void set(E e) {  
        if (lastReturned == null) {  
            throw new IllegalStateException();  
        }  
        checkForComodification();  
        lastReturned.item = e;  
    }  
  
    /**  
     * <p>add 方法，将指定元素插入到列表中  
     * <p>该元素被插入到 `next()` 方法返回的元素之前（如果元素存在的话），以及 `previous()` 方法返回的元素之后（如果元素存在的话）。  
     */  
    public void add(E e) {  
        checkForComodification();  
        lastReturned = null;  
        if (next == null) {  
            // 当前游标所处位置为最后一个节点之后  
            linkLast(e);  
        } else {  
            // 当前游标所处位置为链表中间  
            linkBefore(e, next);  
        }  
        nextIndex++;  
        expectedModCount++;  
    }  
  
    public void forEachRemaining(Consumer<? super E> action) {  
        Objects.requireNonNull(action);  
        while (modCount == expectedModCount && nextIndex < size) {  
            action.accept(next.item);  
            lastReturned = next;  
            next = next.next;  
            nextIndex++;  
        }  
        checkForComodification();  
    }  
  
    final void checkForComodification() {  
        if (modCount != expectedModCount)  
            throw new ConcurrentModificationException();  
    }  
}

8.2 逆序迭代器

public Iterator<E> descendingIterator() {  
    return new DescendingIterator();  
}

LinkedList 类提供了一个方法 descendingIterator()，它返回一个以逆序遍历列表元素的迭代器。该迭代器会从列表的最后一个元素开始，依次向前遍历到第一个元素。

逆序迭代器的源码如下：

private class DescendingIterator implements Iterator<E> {  
    private final ListItr itr = new ListItr(size());  
  
    public boolean hasNext() {  
        return itr.hasPrevious();  
    }  
      
    public E next() {  
        return itr.previous();  
    }  
  
    public void remove() {  
        itr.remove();  
    }  
}

9、逆序视图

LinkedList 类中的 reversed() 方法返回此集合的逆序视图。返回视图中的元素顺序与此集合中的元素顺序相反。逆序排列会影响所有依赖顺序的操作，包括对返回视图的视图集合的操作。如果集合的实现允许对该视图进行修改，则这些修改会“传递”到底层集合中。根据具体实现，对底层集合的更改可能会或可能不会在该逆序视图中可见。

对逆序视图的修改是允许的，并且这些修改将传播到此列表。此外，对该列表的修改也将在逆序视图中可见。

/**  
 * @since 21 
 */
public LinkedList<E> reversed() {  
    return new ReverseOrderLinkedListView<>(this, super.reversed(), Deque.super.reversed());  
}

LinkedList 类的内部类 ReverseOrderLinkedListView 定义如下：

static class ReverseOrderLinkedListView<E> extends LinkedList<E> implements java.io.Externalizable {  
    final LinkedList<E> list;  
    final List<E> rlist;  
    final Deque<E> rdeque;  
  
    ReverseOrderLinkedListView(LinkedList<E> list, List<E> rlist, Deque<E> rdeque) {  
        this.list = list;  
        this.rlist = rlist;  
        this.rdeque = rdeque;  
    }

}

10、基础支持方法

10.1 节点链接操作

10.1.1 linkFirst

链接入参中的 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) {  
        // 如果链表首个节点为 null，表示当前为空链表，则第一个节点也就是最后一个节点  
        last = newNode;  
    } else {  
        // 如果当前链表不为空链表，则原首节点的前置节点为刚才新创建的节点  
        f.prev = newNode;  
    }  
    // 容量加 1    
    size++;  
    modCount++;  
}

10.1.2 linkLast

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;  
    } else {  
        // 如果来拿表不为空，则原尾结点的下一个节点为新创建的节点  
        l.next = newNode;  
    }  
    // 容量加 1
    size++;  
    modCount++;  
}

10.1.3 unlinkFirst

取消链接非空的第一个节点。

private E unlinkFirst(Node<E> f) {  
    // 使用该方法的前提，入参中的节点 f 为链表首节点，并且首节点不为空（非空链表）  
    // assert f == first && f != null;  
    final E element = f.item;  
    final Node<E> next = f.next;  
    // 置为空，GC 垃圾回收  
    f.item = null;  
    f.next = null; // help GC  
    // 将链表首节点赋值为首节点的后置节点  
    first = next;  
    if (next == null) {  
        // 如果首节点的后置节点为 null，表示此列表只有一个元素，则将此链表的尾节点赋值为 null  
        last = null;  
    } else {  
        // 如果首节点的后置节点不为 null，next 已经为首节点，将首节点的前置节点置为 null      
        next.prev = null;  
    }  
    // 容量减 1    
    size--;  
    modCount++;  
    return element;  
}

10.1.4 unlinkLast

取消链接非空的最后一个节点。

private E unlinkLast(Node<E> l) {
    // 使用该方法的前提，入参中的节点 l 为链表尾节点，并且尾节点不为空（非空链表）
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    // 置为空，GC 垃圾回收
    l.item = null;
    l.prev = null; // help GC
    // 将链表尾节点赋值为尾结点的前置节点
    last = prev;
    if (prev == null) {
        // 如果首节点的前置节点为 null，表示此链表只有一个元素，则将此链表的首节点赋值为 null
        first = null;
    } else {
        // 如果首节点的前置节点不为 null，prev 已经为尾节点，将尾结点的后置节点置为 null
        prev.next = null;
    }
    // 容量减 1
    size--;
    modCount++;
    return element;
}

10.1.5 unlink

取消链接入参中指定的非空节点。

E unlink(Node<E> x) {
    // 使用该方法的前提是，该方法的入参节点不为 null
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        // 如果当前节点的前置节点为 null，表示当前节点为首节点，重新赋值链表首节点
        first = next;
    } else {
        // 如果当前节点的前置节点不为 null
        // 将该结点的前置节点赋值为该节点的后置节点
        prev.next = next;
        // 将该节点的前置节点赋值为 null
        x.prev = null;
    }

    if (next == null) {
        // 如果当前节点的后置节点为 null，表示当前节点为尾节点，重新赋值链表尾节点
        last = prev;
    } else {
        // 如果当前节点的后置节点不为 null
        // 将该节点的后置节点赋值为该节点的前置节点
        next.prev = prev;
        // 将该节点的后置节点赋值为 null
        x.next = null;
    }

    // 当前节点存储的元素赋值为 null
    x.item = null;
    // 容量减 1
    size--;
    modCount++;
    return element;
}

10.1.6 linkBefore

在入参非空节点 succ 之前插入元素e

void linkBefore(E e, Node<E> succ) {
    // 该方法的前提是 succ 为非空节点
    // assert succ != null;

    // 待插入位置的前置节点
    final Node<E> pred = succ.prev;
    // 新创建节点，前置节点为 pred，后置节点为 succ
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 后置节点的前置节点赋值为刚创建的节点
    succ.prev = newNode;
    if (pred == null) {
        // 如果 succ 节点前置节点为 null，表示插入位置为链表开头位置
        first = newNode;
    } else {
        pred.next = newNode;
    }
    // 容量加 1
    size++;
    modCount++;
}

10.2 索引定位方法

Node<E> node(int index) 方法返回指定元素索引处的（非空）节点。

Node<E> node(int index) {
    // 使用该方法的前提是，入参 index 未超过链表边界
    // assert isElementIndex(index);

    // 如果 index 的值小于链表容量的除以 2，即 index 为链表前半部分
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 从前往后遍历链表
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    } else {
        // 如果 index 的值大于等于链表容量的除以 2，即 index 为链表后半部分
        Node<E> x = last;
        // 从后往前遍历链表
        for (int i = size - 1; i > index; i--) {
            x = x.prev;
        }
        return x;
    }
}

11、关于栈的方法

双端队列还可以用作 LIFO（后进先出）栈。该接口应优先于传统的 Stack 类使用。当双端队列用作栈时，元素从双端队列的开头被推入或弹出。栈方法与双端队列方法等价，Stack 和 Deque 方法比较如下表所示：

Stack 方法	Deque 等价方法
push(e)	addFirst(e)
pop()	removeFirst()
peek()	getFirst()

public void push(E e) {  
    addFirst(e);  
}

public E pop() {  
    return removeFirst();  
}

public E peek() {  
    final Node<E> f = first;  
    return (f == null) ? null : f.item;  
}

12、removeFirstOccurrence

移除列表中首次出现的指定元素（当从头到尾遍历列表时）。如果列表中不包含该元素，则列表保持不变。

public boolean removeFirstOccurrence(Object o) {  
    return remove(o);  
}

Java 集合框架中的 LinkedList 类 | z2huo

13、removeLastOccurrence

移除列表中最后一次出现的指定元素（当从头到尾遍历列表时）。如果列表中不包含该元素，则列表保持不变。

public boolean removeLastOccurrence(Object o) {  
    if (o == null) {  
        for (Node<E> x = last; x != null; x = x.prev) {  
            if (x.item == null) {  
                unlink(x);  
                return true;  
            }  
        }  
    } else {  
        for (Node<E> x = last; x != null; x = x.prev) {  
            if (o.equals(x.item)) {  
                unlink(x);  
                return true;  
            }  
        }  
    }  
    return false;  
}

上面的方法可以看做是 Java 集合框架中的 LinkedList 类 | z2huo 方法的翻版，不同的是 remove 方法为从前往后遍历，而 removeLastOccurrence 方法为从后往前遍历。

三、其他问题

1、ArrayList 与 LinkedList 的对比

• 底层数据结构
  • ArrayList: 基于动态数组实现。它使用一个可调整大小的数组来存储元素。
  • LinkedList: 基于双向链表实现。每个元素都是一个节点，节点包含指向前一个和后一个节点的引用。
• 存储方式
  • ArrayList: 连续的内存块，用于存储所有元素。每次添加或删除操作可能会导致数组重新分配更大的空间。
  • LinkedList: 每个元素是独立的节点，存储在非连续的内存中。每个节点包含元素本身以及指向前后节点的引用。
• 访问速度
  • ArrayList: 由于其底层是数组，能够通过索引直接访问元素，时间复杂度为 O(1)。适合频繁的随机访问操作。
  • LinkedList: 访问某个元素需要从头或尾遍历链表，时间复杂度为 O(n)。不适合频繁的随机访问。
• 插入和删除操作
  • ArrayList: 插入或删除元素时，特别是对中间元素的操作，可能涉及到移动大量的元素，时间复杂度为 O(n)。但是，末尾的插入操作 add(E e) 时间复杂度为 O(1)。
  • LinkedList: 插入和删除操作无需移动其他元素，时间复杂度为 O(1)，但需要遍历链表找到插入或删除的位置，整体时间复杂度为 O(n)。对于头尾的操作效率较高 addFirst 或 removeFirst，时间复杂度为 O(1)。
• 内存开销
  • ArrayList: 数组在扩展时需要重新分配和复制，因此可能存在额外的内存开销。当数组容量超出当前大小时，会按照一定的倍数扩展。每个元素只存储它本身，没有额外的开销。
  • LinkedList: 每个节点都需要额外的存储空间来保存前后节点的引用，因此内存开销较大。
• 适用场景
  • ArrayList: 适合频繁读取和随机访问的场景，例如通过索引获取元素，或需要快速查找元素的场合。
  • LinkedList: 适合频繁插入、删除元素的场景，尤其是在头尾插入或删除时效率更高。
• 线程安全。ArrayList 和 LinkedList 默认都是非线程安全的。如果在多线程环境中使用，需要手动进行同步，例如使用 Collections.synchronizedList()。

相关链接

迭代器 Iterator | z2huo

迭代器 ListIterator | z2huo

Deque | z2huo

Java 集合框架中的 LinkedList 类 | z2huo

OB links

[[迭代器 Iterator]]

[[迭代器 ListIterator]]

[[Deque]]

[[AbstractCollection]]

OB tags

#Java