Java集合之LinkedList源码篇

小奥2024-01-132024-01-13

Java集合之LinkedList源码篇

概述

LinkedList使用链表结构存储元素，链表是一种线性的存储结构，将要存储的数据存在一个存储单元中，这个存储单元除了存储的数据意外，还存储下一个存储单元的地址。

LinkedList是双向链表结构，除了存储自身的值之外，还额外存储了前一个和后一个元素的地址。

不过，我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！就连 LinkedList 的作者约书亚 · 布洛克（Josh Bloch）自己都说从来不会使用 LinkedList 。

底层数据结构

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

继承AbstractSequentialList，AbstractSequentialList又继承自AbstractList。
实现List接口，表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
实现Deque接口，继承自 Queue 接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。
实现Cloneable接口，表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
实现Serializable接口，表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。

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

成员变量

/**
 * 链表的长度，即节点的个数
 */
transient int size = 0;

   /**
    * 指向第一个节点的指针。
    * 不变式:(first == null && last == null) || 
    * 			   (first.)Prev == null && first。= null)
    */
   transient Node<E> first;

   /**
    * 指向最后一个节点的指针
    * 不变式: (first == null && last == null) ||
    *            (last.next == null && last.item != null)
    */
   transient Node<E> last;

构造函数

/**
 * 构造一个空列表
 */
public LinkedList() {
}

/**
 * 按照指定集合的迭代器返回的顺序，构造一个包含指定集合元素的列表。
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

插入元素

add() 方法有两个版本：

add(E e)：用于在 LinkedList 的尾部插入元素，即将新元素作为链表的最后一个元素，时间复杂度为 O(1)。
add(int index, E element):用于在指定位置插入元素。这种插入方式需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

/**
 * 将指定的元素追加到此列表的末尾。
 * 这个方法等价于addLast。
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

/**
 * 将指定元素插入此列表中的指定位置。
 * 将当前在该位置的元素(如果有的话)和任何后续元素向右移动(在它们的索引上加1)。
 */
public void add(int index, E element) {
    // 下标越界检查
    checkPositionIndex(index);

    if (index == size)
        // 如果index是链表的尾部位置，则直接调用linkLast将元素节点插入链表尾部即可
        linkLast(element);
    else
        // 如果index不是链表的尾部位置，则调用linkBefore方法将其插入指定元素之前
        linkBefore(element, node(index));
}

linkLast()、linkBefore()

/**
    * 插入e作为最后一个元素。
    */
   void linkLast(E e) {
       // 将最后一个元素赋值（引用传递）给节点l
       final Node<E> l = last;
       // 创建节点，并指定节点前驱为链表尾接待你last，后继引用为null
       final Node<E> newNode = new Node<>(l, e, null);
       // 将last引用指向新节点
       last = newNode;
       if (l == null)
           // 如果l为null，说明是第一次添加元素，将first赋值为新节点，此时链表只有一个元素
           first = newNode;
       else
           // 如果l不为null，说明不是第一次添加，将新节点赋值给l（添加前的最后一个元素）的next
           l.next = newNode;
       size++;
       modCount++;
   }

   /**
    * 在非空节点前插入元素e。
    */
   void linkBefore(E e, Node<E> succ) {
       // assert succ != null; 断言succ不为空
       // 定义一个节点元素保存succ的prev引用，也就是前一个节点
       final Node<E> pred = succ.prev;
       // 初始化节点，并指明prev和next
       final Node<E> newNode = new Node<>(pred, e, succ);
       // 将succ节点前驱引用prev指向新节点
       succ.prev = newNode;
       // 判断尾节点是否为null
       if (pred == null)
           // 如果为null表示当前链表还没有节点，将first节点指向newNode
           first = newNode;
       else
           // 如果不为null表示当前链表已经存在，将pred的next指向newNode
           pred.next = newNode;
       size++;
       modCount++;
   }

获取元素

LinkedList获取元素相关的方法一共有 3 个：

getFirst()：获取链表的第一个元素。
getLast()：获取链表的最后一个元素。
get(int index)：获取链表指定位置的元素。

/**
 * 返回列表中第一个元素
 */
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

/**
 * 返回列表中最后一个元素
 */
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

/**
 * 返回列表中指定位置的元素。
 */
public E get(int index) {
    // 下标越界检查
    checkElementIndex(index);
    // 返回链表中对应下标的元素
    return node(index).item;
}

从get()方法中可以看到，核心逻辑在于node(int index)这个方法。

/**
 * 返回指定元素索引处的(非空)节点。
 */
Node<E> node(int index) {
    // assert isElementIndex(index); 断言下标未越界

    if (index < (size >> 1)) {
        // 如果index < size / 2，从前开始向后查找
        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;
    }
}

从这个方法的实现逻辑可以看出，该方法通过比较索引值与链表size/2来确定从链表头还是链表尾开始遍历。

如果索引值小于size/2，则从链表头开始遍历
如果索引值大于等于size/2，则从链表尾部开始遍历

这样，即使最坏的情况，也只需要O(n/2)的时间内找到目标节点，充分利用了双向链表的特性来提高效率。

删除元素

LinkedList删除元素相关的方法一共有 5 个：

removeFirst()：删除并返回链表的第一个元素。
removeLast()：删除并返回链表的最后一个元素。
remove(Object o)：删除链表中首次出现的指定元素，如果不存在该元素则返回 false。
remove(int index)：删除指定索引处的元素，并返回该元素的值。
void clear()：移除此链表中的所有元素。

/**
    * 移除并且返回列表的第一个元素
    */
   public E removeFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return unlinkFirst(f);
   }

   /**
    * 移除并且返回列表的最后一个元素
    */
   public E removeLast() {
       final Node<E> l = last;
       if (l == null)
           throw new NoSuchElementException();
       return unlinkLast(l);
   }
   /**
    * 从此列表中删除第一个出现的指定元素(如果该元素存在)。
    * 如果此列表不包含该元素，则该元素不变。
    * 更正式地说，删除具有最低索引i的元素，使(o==null ?Get (i)==null: o.equals(Get (i)))(如果存在这样的元素)。
    * 如果此列表包含指定的元素(或者等价地，如果此列表因调用而更改)，则返回true。
    */
   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;
   }

   /**
    * 移除此列表中指定位置的元素。
    * 将所有后续元素向左移动(从它们的索引中减去1)。返回从列表中删除的元素。
    */
   public E remove(int index) {
       checkElementIndex(index);
       return unlink(node(index));
   }

   /**
    * 从列表中删除所有元素。该调用返回后，列表将为空。
    */
   public void clear() {
       //清除所有节点间的链接是"不必要的"，但是:
       // -如果被丢弃的节点驻留，帮助分代GC
       //多代
       // -即使存在可访问的迭代器，也一定会释放内存
       for (Node<E> x = first; x != null; ) {
           Node<E> next = x.next;
           x.item = null;
           x.next = null;
           x.prev = null;
           x = next;
       }
       first = last = null;
       size = 0;
       modCount++;
   }

从上面几个方法中可以看到，具体的核心逻辑在unlink()这个方法中。

/**
 * 解除非空节点x
 */
E unlink(Node<E> x) {
    // assert x != null; 断言x不为null
    // 获取当前节点，也就是待删除节点的元素
    final E element = x.item;
    final Node<E> next = x.next; // next节点
    final Node<E> prev = x.prev; // prev节点

    if (prev == null) {
        // 如果prev为null，说明当前节点是头节点
        // 直接让链表头指向当前节点的下一个节点
        first = next;
    } else {
        // 当前节点不是头节点
        // 将前一个节点的next指针指向当前节点的下一个节点
        prev.next = next;
        // 将当前节点的prev指针置为null，方便GC回收
        x.prev = null;
    }

    if (next == null) {
        // 如果next为null，说明当前节点是尾节点
        // 直接让链表尾指向当前节点的前一个节点
        last = prev;
    } else {
        // 如果next不为null
        // 将下一个节点的prev指针指向当前节点的前一个节点
        next.prev = prev;
        // 将当前节点的next指针置为null，方便GC回收
        x.next = null;
    }
    // 将当前节点元素置为null，方便GC回收
    x.item = null;
    size--;
    modCount++;
    return element;
}

unlink()方法的逻辑如下：

首先获取待删除节点x的前驱和后继节点
判断待删除节点是否为头节点或者尾节点：
- 如果x是头节点，则将first指向x的后继节点next
- 如果x是尾节点，则将last指向x的前驱节点prev
- 如果x不是头节点也不是尾节点，执行下一步操作
将待删除节点x的前驱的后继指向待删除节点的后继next，断开x和x.prev之间的链接
将待删除节点 x 的后继的前驱指向待删除节点的前驱 prev，断开 x 和 x.next 之间的链接
将待删除节点 x 的元素置空，修改链表长度

遍历链表

LinkedList 的遍历的核心就是它的迭代器的实现。我们一般推荐使用foreach来进行遍历，因为底层其实就是使用迭代器来进行遍历的。

我们来看一下双向迭代器的实现：

// 双向迭代器
private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned; // 表示上一次调用next()或者previous()方法时经过的节点
    private Node<E> next; // 表示下一个要遍历的节点
    private int nextIndex; // 表示下一个要遍历的节点的下标，也就是当前节点的next的下标
    // 表示哦当前遍历期望的修改计数器，用于和LinkedList的modCount比较，判断链表是否倍其他线程修改
    private int expectedModCount = modCount;

    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }

    // 判断是否还有下一个节点
    public boolean hasNext() {
        // 判断下一个节点的下标是否小于链表的大小，如果是则表示还有下一个元素可以遍历
        return nextIndex < size;
    }

    // 获取下一个节点
    public E next() {
        checkForComodification(); // 检查在迭代过程中链表是否被修改过
        if (!hasNext())
            // 如果没有下一个节点，则抛出NoSuchElementException异常
            throw new NoSuchElementException();

        lastReturned = next; // 将lastReturned指向当前节点
        next = next.next; // 将next指向下一个节点
        nextIndex++;
        return lastReturned.item;
    }

    // 判断是否还有前一个节点
    public boolean hasPrevious() {
        return nextIndex > 0;
    }
    // 获取前一个节点
    public E previous() {
        checkForComodification(); // 检查是否在迭代过程中链表被修改
        if (!hasPrevious())
            // 如果没有前一个节点，则抛出NoSuchElementException异常
            throw new NoSuchElementException();
        // 将lastReturned和next指针指向上一个节点
        lastReturned = next = (next == null) ? last : next.prev;
        nextIndex--;
        return lastReturned.item;
    }

    public int nextIndex() {
        return nextIndex;
    }

    public int previousIndex() {
        return nextIndex - 1;
    }
    // 从列表中删除上次被返回的元素
    public void remove() {
        checkForComodification(); // 检查是否在迭代过程中链表被修改
        if (lastReturned == null)
            // 如果上次返回的节点为null，则抛出异常
            throw new IllegalStateException();

        // 获取当前节点的下一个节点
        Node<E> lastNext = lastReturned.next;
        // 从链表中删除上次返回的节点
        unlink(lastReturned);
        // 修改指针
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        // 将上次返回的节点的引用置为null，方便GC回收
        lastReturned = null;
        expectedModCount++;
    }

    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }

    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }
	...
}

其中主要的几个个核心方法如下：

从头到尾遍历，包括方法hasNext()和next()
从尾到头遍历，包括方法hasPrevious()和previous()
移除遍历过的节点，包括方法remove()
添加或更新节点，包括方法add()和set()

Queue方法

// 队列的操作。

  /**
   * 检索但不删除此列表的头部(第一个元素)。
   */
  public E peek() {
      final Node<E> f = first;
      return (f == null) ? null : f.item;
  }

  /**
   * 检索但不删除此列表的头部(第一个元素)。
   */
  public E element() {
      return getFirst();
  }

  /**
   * 检索并删除此列表的头部(第一个元素)。
   */
  public E poll() {
      final Node<E> f = first;
      return (f == null) ? null : unlinkFirst(f);
  }

  /**
   * 检索并删除此列表的头部(第一个元素)。
   */
  public E remove() {
      return removeFirst();
  }

  /**
   * 添加指定元素作为此列表的尾部(最后一个元素)。
   */
  public boolean offer(E e) {
      return add(e);
  }

Deque方法

// 双端队列的操作。

/**
 * 在此列表的前面插入指定的元素。
 */
public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

/**
 * 在此列表的末尾插入指定的元素。
 */
public boolean offerLast(E e) {
    addLast(e);
    return true;
}

/**
 * 检索但不删除此列表的第一个元素，如果此列表为空则返回null。
 */
public E peekFirst() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

/**
 * 检索但不删除此列表的最后一个元素，如果此列表为空则返回null。
 */
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

/**
 * 检索并删除此列表的第一个元素，如果此列表为空，则返回null。
 */
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

/**
 * 检索并删除此列表的最后一个元素，如果此列表为空，则返回null。
 */
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

/**
 * 将一个元素压入由该列表表示的堆栈。换句话说，将元素插入到列表的前面。
 * 该方法等价于addFirst。
 */
public void push(E e) {
    addFirst(e);
}

/**
 * 从此列表表示的堆栈中弹出一个元素。换句话说，删除并返回该列表的第一个元素。
 * 这个方法等价于removeFirst()。
 */
public E pop() {
    return removeFirst();
}

LinkedList面试题总结

LinkedList 插入和删除元素的时间复杂度如何？

头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

LinkedList 为什么不能实现 RandomAccess 接口？

RandomAccess 是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于 LinkedList 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 RandomAccess 接口。

ArrayList和LinkedList的区别

（1）是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；

（2）底层数据结构： Arraylist 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环）

（3）存取效率：ArrayList底层使用数组实现，所以它的查找时间复杂度是O(1)，插入和删除时间复杂度是O(n)；而LinkedList底层使用链表实现的，所以它的查找时间复杂度是O(n)，插入和删除只需要改变元素指针的指向即可，所以是O(1)。

（4）内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

源码

package java.util;

import java.util.function.Consumer;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * 指向第一个节点的指针。
     * 不变式:(first == null && last == null) || 
     * 			   (first.)Prev == null && first。= null)
     */
    transient Node<E> first;

    /**
     * 指向最后一个节点的指针
     * 不变式: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

    /**
     * 构造一个空列表
     */
    public LinkedList() {
    }

    /**
     * 按照指定集合的迭代器返回的顺序，构造一个包含指定集合元素的列表。
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    /**
     * 插入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;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * 插入e作为最后一个元素。
     */
    void linkLast(E e) {
        // 将最后一个元素赋值（引用传递）给节点l
        final Node<E> l = last;
        // 创建节点，并指定节点前驱为链表尾接待你last，后继引用为null
        final Node<E> newNode = new Node<>(l, e, null);
        // 将last引用指向新节点
        last = newNode;
        if (l == null)
            // 如果l为null，说明是第一次添加元素，将first赋值为新节点，此时链表只有一个元素
            first = newNode;
        else
            // 如果l不为null，说明不是第一次添加，将新节点赋值给l（添加前的最后一个元素）的next
            l.next = newNode;
        size++;
        modCount++;
    }

    /**
     * 在非空节点前插入元素e。
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null; 断言succ不为空
        // 定义一个节点元素保存succ的prev引用，也就是前一个节点
        final Node<E> pred = succ.prev;
        // 初始化节点，并指明prev和next
        final Node<E> newNode = new Node<>(pred, e, succ);
        // 将succ节点前驱引用prev指向新节点
        succ.prev = newNode;
        // 判断尾节点是否为null
        if (pred == null)
            // 如果为null表示当前链表还没有节点，将first节点指向newNode
            first = newNode;
        else
            // 如果不为null表示当前链表已经存在，将pred的next指向newNode
            pred.next = newNode;
        size++;
        modCount++;
    }

    /**
     * 解除第一个非空节点f
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> 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;
    }

    /**
     * 解除最后一个非空节点l
     */
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> 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;
    }

    /**
     * 解除非空节点x
     */
    E unlink(Node<E> x) {
        // assert x != null; 断言x不为null
        // 获取当前节点，也就是待删除节点的元素
        final E element = x.item;
        final Node<E> next = x.next; // next节点 
        final Node<E> prev = x.prev; // prev节点

        if (prev == null) {
            // 如果prev为null，说明当前节点是头节点
            // 直接让链表头指向当前节点的下一个节点
            first = next;
        } else {
            // 当前节点不是头节点 
            // 将前一个节点的next指针指向当前节点的下一个节点 
            prev.next = next;
            // 将当前节点的prev指针置为null，方便GC回收
            x.prev = null;
        }

        if (next == null) {
            // 如果next为null，说明当前节点是尾节点
            // 直接让链表尾指向当前节点的前一个节点
            last = prev;
        } else {
            // 如果next不为null
            // 将下一个节点的prev指针指向当前节点的前一个节点 
            next.prev = prev;
            // 将当前节点的next指针置为null，方便GC回收
            x.next = null;
        }
		// 将当前节点元素置为null，方便GC回收
        x.item = null;
        size--;
        modCount++;
        return element;
    }

    /**
     * 返回列表中第一个元素
     */
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    /**
     * 返回列表中最后一个元素
     */
    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

    /**
     * 移除并且返回列表的第一个元素
     */
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    /**
     * 移除并且返回列表的最后一个元素 
     */
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

    /**
     * 在此列表的开头插入指定的元素。
     */
    public void addFirst(E e) {
        linkFirst(e);
    }

    /**
     * 将指定的元素追加到此列表的末尾。
     */
    public void addLast(E e) {
        linkLast(e);
    }

    /**
     * 如果此列表包含指定的元素，则返回true。
     * 更正式地说，当且仅当此列表包含至少一个元素e满足(o==null ?)e==null: 0 .equals(e))。
     */
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    /**
     * 返回此列表中元素的个数。
     */
    public int size() {
        return size;
    }

    /**
     * 将指定的元素追加到此列表的末尾。
     * 这个方法等价于addLast。
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * 从此列表中删除第一个出现的指定元素(如果该元素存在)。
     * 如果此列表不包含该元素，则该元素不变。
     * 更正式地说，删除具有最低索引i的元素，使(o==null ?Get (i)==null: o.equals(Get (i)))(如果存在这样的元素)。
     * 如果此列表包含指定的元素(或者等价地，如果此列表因调用而更改)，则返回true。
     */
    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;
    }

    /**
     * 按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到该列表的末尾。
     * 如果在操作进行期间修改了指定的集合，则此操作的行为是未定义的。
     * (注意，如果指定的集合是这个列表，并且它是非空的，则会发生这种情况。)
     */
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    /**
     * 从指定位置开始，将指定集合中的所有元素插入此列表。
     * 将当前在该位置的元素(如果有的话)和任何后续元素向右移动(增加它们的索引)。
     * 新元素将按照指定集合的迭代器返回的顺序出现在列表中。
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, 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;
            Node<E> newNode = new Node<>(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;
    }

    /**
     * 从列表中删除所有元素。该调用返回后，列表将为空。
     */
    public void clear() {
        //清除所有节点间的链接是"不必要的"，但是:
        // -如果被丢弃的节点驻留，帮助分代GC
        //多代
        // -即使存在可访问的迭代器，也一定会释放内存
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }


    // 位置访问操作

    /**
     * 返回列表中指定位置的元素。
     */
    public E get(int index) {
        // 下标越界检查
        checkElementIndex(index);
        // 返回链表中对应下标的元素
        return node(index).item;
    }

    /**
     * 将此列表中指定位置的元素替换为指定元素。
     */
    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    /**
     * 将指定元素插入此列表中的指定位置。
     * 将当前在该位置的元素(如果有的话)和任何后续元素向右移动(在它们的索引上加1)。
     */
    public void add(int index, E element) {
        // 下标越界检查
        checkPositionIndex(index);

        if (index == size)
            // 如果index是链表的尾部位置，则直接调用linkLast将元素节点插入链表尾部即可
            linkLast(element);
        else
            // 如果index不是链表的尾部位置，则调用linkBefore方法将其插入指定元素之前
            linkBefore(element, node(index));
    }

    /**
     * 移除此列表中指定位置的元素。
     * 将所有后续元素向左移动(从它们的索引中减去1)。返回从列表中删除的元素。
     */
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

    /**
     * 告诉参数是否是现有元素的索引。
     */
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    /**
     * 告诉参数是否是迭代器或加法操作的有效位置的索引。
     */
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    /**
     * 构造IndexOutOfBoundsException详细消息。
     * 在许多可能的错误处理代码重构中，这种“概述”在服务器和客户端vm中都表现最好。
     */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    private void checkPositionIndex(int index) {
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    /**
     * 返回指定元素索引处的(非空)节点。
     */
    Node<E> node(int index) {
        // assert isElementIndex(index); 断言下标未越界 

        if (index < (size >> 1)) {
            // 如果index < size / 2，从前开始向后查找
            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。
     * 更正式地说，返回最低索引i，使得(o==null ?Get (i)==null: o.equals(Get (i)))，如果没有这样的索引，则为-1。
     */
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

    /**
     * 返回指定元素在此列表中最后出现的索引，如果此列表不包含该元素，则返回-1。
     * 更正式地说，返回最高索引i，使得(o==null ?Get (i)==null: o.equals(Get (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;
    }

    // 队列的操作。

    /**
     * 检索但不删除此列表的头部(第一个元素)。
     */
    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

    /**
     * 检索但不删除此列表的头部(第一个元素)。
     */
    public E element() {
        return getFirst();
    }

    /**
     * 检索并删除此列表的头部(第一个元素)。
     */
    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    /**
     * 检索并删除此列表的头部(第一个元素)。
     */
    public E remove() {
        return removeFirst();
    }

    /**
     * 添加指定元素作为此列表的尾部(最后一个元素)。
     */
    public boolean offer(E e) {
        return add(e);
    }

    // 双端队列的操作。
    
    /**
     * 在此列表的前面插入指定的元素。
     */
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

    /**
     * 在此列表的末尾插入指定的元素。
     */
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

    /**
     * 检索但不删除此列表的第一个元素，如果此列表为空则返回null。
     */
    public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

    /**
     * 检索但不删除此列表的最后一个元素，如果此列表为空则返回null。
     */
    public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

    /**
     * 检索并删除此列表的第一个元素，如果此列表为空，则返回null。
     */
    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    /**
     * 检索并删除此列表的最后一个元素，如果此列表为空，则返回null。
     */
    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

    /**
     * 将一个元素压入由该列表表示的堆栈。换句话说，将元素插入到列表的前面。
     * 该方法等价于addFirst。
     */
    public void push(E e) {
        addFirst(e);
    }

    /**
     * 从此列表表示的堆栈中弹出一个元素。换句话说，删除并返回该列表的第一个元素。
     * 这个方法等价于removeFirst()。
     */
    public E pop() {
        return removeFirst();
    }

    /**
     * 删除该列表中第一次出现的指定元素(当从头到尾遍历列表时)。
     * 如果列表中不包含该元素，则该元素不变。
     */
    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

    /**
     * 删除该列表中最后一次出现的指定元素(当从头到尾遍历列表时)。
     * 如果列表中不包含该元素，则该元素不变。
     */
    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;
    }

    /**
     * 返回此列表中元素的列表迭代器(以适当的顺序)，从列表中的指定位置开始。
     * 遵循list.listtiterator (int)的一般约定。
     * list- Iterator是快速失败的：如果在Iterator创建后的任何时间，
     * 以除通过list- Iterator自己的remove或add方法之外的任何方式修改列表，
     * list- Iterator将抛出ConcurrentModificationException。
     * 因此，在面对并发修改时，迭代器会快速而干净地失败，而不是在未来不确定的时间冒任意的、不确定的行为的风险。
     */
    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new ListItr(index);
    }

   	// 双向迭代器 
    private class ListItr implements ListIterator<E> {
        private Node<E> lastReturned; // 表示上一次调用next()或者previous()方法时经过的节点 
        private Node<E> next; // 表示下一个要遍历的节点 
        private int nextIndex; // 表示下一个要遍历的节点的下标，也就是当前节点的next的下标
        // 表示哦当前遍历期望的修改计数器，用于和LinkedList的modCount比较，判断链表是否倍其他线程修改
        private int expectedModCount = modCount; 

        ListItr(int index) {
            // assert isPositionIndex(index);
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }
		
        // 判断是否还有下一个节点 
        public boolean hasNext() {
            // 判断下一个节点的下标是否小于链表的大小，如果是则表示还有下一个元素可以遍历
            return nextIndex < size;
        }

        // 获取下一个节点 
        public E next() {
            checkForComodification(); // 检查在迭代过程中链表是否被修改过
            if (!hasNext())
                // 如果没有下一个节点，则抛出NoSuchElementException异常
                throw new NoSuchElementException();

            lastReturned = next; // 将lastReturned指向当前节点 
            next = next.next; // 将next指向下一个节点
            nextIndex++;
            return lastReturned.item;
        }

       	// 判断是否还有前一个节点
        public boolean hasPrevious() {
            return nextIndex > 0;
        }
		// 获取前一个节点 
        public E previous() {
            checkForComodification(); // 检查是否在迭代过程中链表被修改
            if (!hasPrevious())
                // 如果没有前一个节点，则抛出NoSuchElementException异常
                throw new NoSuchElementException();
			// 将lastReturned和next指针指向上一个节点
            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }
		// 从列表中删除上次被返回的元素 
        public void remove() {
            checkForComodification(); // 检查是否在迭代过程中链表被修改
            if (lastReturned == null)
                // 如果上次返回的节点为null，则抛出异常
                throw new IllegalStateException();

            // 获取当前节点的下一个节点 
            Node<E> lastNext = lastReturned.next;
            // 从链表中删除上次返回的节点
            unlink(lastReturned);
            // 修改指针
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            // 将上次返回的节点的引用置为null，方便GC回收
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

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

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

    /**
     * @since 1.6
     */
    public Iterator<E> descendingIterator() {
        return new DescendingIterator();
    }

    /**
     * 通过listitter.previous提供降序迭代器的适配器
     */
    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();
        }
    }

    @SuppressWarnings("unchecked")
    private LinkedList<E> superClone() {
        try {
            return (LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }

    /**
     * 返回该LinkedList的浅拷贝。(元素本身不被克隆。)
     */
    public Object clone() {
        LinkedList<E> clone = superClone();

        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;

        // Initialize clone with our elements
        for (Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);

        return clone;
    }

    /**
     * 返回一个数组，其中包含此列表中按适当顺序(从第一个元素到最后一个元素)的所有元素。
     * 返回的数组将是“安全的”，因为此列表不维护对它的引用。(换句话说，这个方法必须分配一个新的数组)。
     * 因此，调用者可以自由地修改返回的数组。此方法充当基于数组和基于集合的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;
    }

    /**
     * 返回一个数组，其中包含列表中所有元素的正确顺序(从第一个元素到最后一个元素);
     * 返回数组的运行时类型为指定数组的运行时类型。
     * 如果列表适合指定的数组，它将在指定的数组中返回。否则，将使用指定数组的运行时类型和此列表的大小分配一个新数组。
     * 如果列表适合指定的数组，并且有足够的空间(即，数组的元素多于列表)，则数组中紧接在列表末尾的元素被设置为空。
     * (只有当调用者知道列表不包含任何null元素时，这在确定列表长度时才有用。)
     * 与toArray()方法一样，该方法充当基于数组和基于集合的api之间的桥梁。
     * 此外，此方法允许对输出数组的运行时类型进行精确控制，并且在某些情况下可以用于节省分配成本。
     * 假设x是一个已知只包含字符串的列表。下面的代码可用于将列表转储到新分配的String数组中:
     * String[] y = x.toArray(new String[0]);
     * 注意，toArray(new Object[0])在函数上与toArray()相同。
     */
    @SuppressWarnings("unchecked")
    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;

        if (a.length > size)
            a[size] = null;

        return a;
    }

    private static final long serialVersionUID = 876323262645176354L;

    /**
     * 将这个LinkedList实例的状态保存到一个流(也就是说，序列化它)
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out size
        s.writeInt(size);

        // Write out all elements in the proper order.
        for (Node<E> x = first; x != null; x = x.next)
            s.writeObject(x.item);
    }

    /**
     * 从一个流重新构造这个LinkedList实例(也就是说，反序列化它)。
     */
    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read in size
        int size = s.readInt();

        // Read in all elements in the proper order.
        for (int i = 0; i < size; i++)
            linkLast((E)s.readObject());
    }

    /**
     * 在此列表中的元素上创建一个延迟绑定和故障快速分割器。
     * Spliterator报告Spliterator.SIZED和Spliterator.ORDERED.Overriding实现应该记录额外特征值的报告。
     */
    @Override
    public Spliterator<E> spliterator() {
        return new LLSpliterator<E>(this, -1, 0);
    }

    /** A customized variant of Spliterators.IteratorSpliterator */
    static final class LLSpliterator<E> implements Spliterator<E> {
        static final int BATCH_UNIT = 1 << 10;  // batch array size increment
        static final int MAX_BATCH = 1 << 25;  // max batch array size;
        final LinkedList<E> list; // null OK unless traversed
        Node<E> current;      // current node; null until initialized
        int est;              // size estimate; -1 until first needed
        int expectedModCount; // initialized when est set
        int batch;            // batch size for splits

        LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
            this.list = list;
            this.est = est;
            this.expectedModCount = expectedModCount;
        }

        final int getEst() {
            int s; // force initialization
            final LinkedList<E> lst;
            if ((s = est) < 0) {
                if ((lst = list) == null)
                    s = est = 0;
                else {
                    expectedModCount = lst.modCount;
                    current = lst.first;
                    s = est = lst.size;
                }
            }
            return s;
        }

        public long estimateSize() { return (long) getEst(); }

        public Spliterator<E> trySplit() {
            Node<E> p;
            int s = getEst();
            if (s > 1 && (p = current) != null) {
                int n = batch + BATCH_UNIT;
                if (n > s)
                    n = s;
                if (n > MAX_BATCH)
                    n = MAX_BATCH;
                Object[] a = new Object[n];
                int j = 0;
                do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
                current = p;
                batch = j;
                est = s - j;
                return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
            }
            return null;
        }

        public void forEachRemaining(Consumer<? super E> action) {
            Node<E> p; int n;
            if (action == null) throw new NullPointerException();
            if ((n = getEst()) > 0 && (p = current) != null) {
                current = null;
                est = 0;
                do {
                    E e = p.item;
                    p = p.next;
                    action.accept(e);
                } while (p != null && --n > 0);
            }
            if (list.modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

        public boolean tryAdvance(Consumer<? super E> action) {
            Node<E> p;
            if (action == null) throw new NullPointerException();
            if (getEst() > 0 && (p = current) != null) {
                --est;
                E e = p.item;
                current = p.next;
                action.accept(e);
                if (list.modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                return true;
            }
            return false;
        }

        public int characteristics() {
            return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
        }
    }

}