LinkedList<E> 源码解读

继承AbstractSequentialList<E>

实现List<E>, Deque<E>, Cloneable, Serializable接口

方法说明

private void linkFirst(E e)

功能：将新元素添加至链表的头。

过程：如果头为空，头尾结点共同指向新结点，反之，把新结点插入到原头结点前。

void linkLast(E e)

功能：将新元素添加至链表的尾。

过程：如果尾为空，头尾结点共同指向新结点，反之，把新结点 插入到原尾结点后。

void linkBefore(E e, Node<E> succ)

功能：把新结点插入到目标结点前。

过程：设置一个临时引用指向succ的前结点，然后把新结点插入到succ结点前结点的后面，succ的前指针重新指向新结点，新结点前指针如果为空，那么头指针指向新结点，否则，新结点的前结点的后指针指向新结点。

private E unlinkFirst(Node<E> f)

功能：把头结点删除并返回结点元素值（不能对空链表执行该操作）。

过程：建立临时结点存储头结点的next指针指向的结点，让头结点的元素值置为空，头结点的next指针指向空，判断如果头结点的next指针指向空，那么尾结点也指向空（即链表为空），否则，让头结点的next指针指向的结点（最开始存入临时结点）的前指针指向空。

private E unlinkLast(Node<E> l)

功能：把尾结点删除并返回结点元素值（不能对空链表执行该操作）。

过程：建立临时结点存储尾结点的prev指针指向的结点，让尾结点的元素值置为空，尾结点的prev指针指向空，判断如果尾结点的prev指针指向空，那么头结点也指向空（即链表为空），否则，让尾结点的prev指针指向的结点（最开始存入临时结点）的后指针指向空。

E unlink(Node<E> x)

功能：删除一个结点，并返回该结点的元素值（不能对空链表执行该操作）。

过程：建立两个临时的结点的引用，分别指向目标结点的头指针指向的结点和后指针指向的结点。判断如果目标结点前指针不为空，那么临时的结点引用prev的后指针指向临时的结点引用next指向的结点，否则，原头指针指向临时结点引用next所指向的结点，然后把目标结点的前指针指向空。对目标结点的后指针同样进行判断操作，然后把目标结点的后指针指向空。最后把目标结点元素置空。

public E getFirst()

功能：返回链表第一个结点的元素值。

过程：判断头结点是否为空，如果为空则抛出NoSuchElementException异常，否则返回头指针指向的结点的元素值。

public E getLast ()

功能：返回链表最后一个结点的元素值。

过程：判断尾结点是否为空，如果为空则抛出NoSuchElementException异常，否则返回尾指针指向的结点的元素值。

public E removeFirst()

功能：删除头结点并返回结点元素值。

过程：判断头结点是否为空，如果为空则抛出NoSuchElementException异常，否则调用unlinkFirst()方法。

public E removeLast ()

功能：删除尾结点并返回结点元素值。

过程：判断尾结点是否为空，如果为空则抛出NoSuchElementException异常，否则调用unlinkLast()方法。

public void addFirst(E e)

功能：向链表头添加一个元素。

过程：调用linkFirst(E e)方法。

public void addLast(E e)

功能：向链表尾添加一个元素。

过程：调用linkLast (E e)方法。

public boolean contains(Object o)

功能：判断某个元素是否在链表中。

过程：调用indexOf()方法，判断返回的索引值是否为-1，如果是则代表链表中不存在该元素索引，则返回false，否则返回true.

public int size()

功能：返回链表长度。

过程：返回LinkedList类中的类私有变量size.

备注：size在链表进行添加和删除操作时都会相应的增加或减少。

public boolean add(E e)

功能：向链表尾部添加一个元素

过程：调用包权限方法linkLast(E e)，并返回true.

public boolean remove(Object o)

功能：删除链表中的某个元素。

过程：判断o是否为空，如果为空则遍历链表，把空元素所在结点用unlink()方法删除，并返回true；反之，也遍历链表，调用equals()方法判断每个结点的元素是否和传入的元素相等，如果是则调用unlink()方法删除，并返回true;如果都没有符合条件的元素，则返回false.

public boolean addAll(Collection<? extends E> c)

功能：把一个Collection对象直接添加至链表尾部。

过程：调用addAll(size, c)并将该方法的返回值直接返回。

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

功能：把一个Collection对象插入到链表第index元素之后。

过程：先调用checkPositionIndex方法检测传入的index是否超过链表size，如果是则抛出异常。然后将Collection对象转为Object数组，判断数组长度是否为0，是的话则返回false.然后创建两个结点的引用，分别指向index结点（prev）和index后一结点（succ）（如果后一结点为空则指向空）。然后遍历传入的Collection对象被转成的Object数组，每次建立一个临时的newNode，然后插入之前创建的指针中（prev后，succ前），并返回true.

public void clear()

功能：清空链表中所有结点。

过程：遍历链表，当结点不为空时，建立一个临时结点引用指向下一结点，然后清空当前结点的元素值及prev next指针。最后让first和last指针都指向空，并置size为0.

public E get(int index)

功能：根据索引返回指定的结点元素值。

过程：先调用checkElementIndex()方法检查索引是否超过链表长度，超过则抛出异常。然后返回指定结点元素，调用node()方法的返回制定结点并访问item成员。

public E set(int index, E element)

功能：根据指定的索引修改结点中的元素值，并返回之前结点中的元素值。

过程：先调用checkElementIndex()方法检查索引是否超过链表长度，超过则抛出异常。然后把原先结点的元素的值存储起来，替换后返回原结点的元素值。

public void add(int index, E element)

功能：把元素插入到指定索引结点前。

过程：首先判断索引是否越界，如果是则抛出异常。否则，判断索引是否为最后一个元素之后的元素（即index == size），如果是则调用linkLast()方法，把结点插入最后，否则调用linkBefore()方法，把新结点插入到指定索引结点前。

public E remove(int index)

功能：删除指定索引出的结点。

过程：先调用checkElementIndex()方法判断索引是否越界，是则抛出异常。然后调用unlink()方法将指定结点删除，并返回unlink()的返回值。

private boolean isElementIndex(int index)

功能：判断索引值是否大于等于0且小于size，即索引对应的结点是否存在。

过程：如果小于0或大于等于size则返回false,反之，则返回true.

private boolean isPositionIndex(int index)

功能：判断索引值是否大于等于0且小于等于size，即索引位置对于迭代器和add()方法来说是否合法。

过程：如果小于0或大于size则返回false,反之，则返回true.

private String outOfBoundsMsg(int index)

功能：返回索引越界异常的字符串提示信息。

过程：返回索引越界异常的字符串提示信息。

private void checkElementIndex(int index)

功能：如果索引对应结点不存在（index < 0 || index >= size），抛出越界异常。

过程：调用isElementIndex()方法判断索引是否有对应的结点，如果没有，抛出异常。

private void checkPositionIndex()

功能：如果索引不能用于迭代器和add()方法（index < 0 || index > size），抛出越界异常。

过程：调用isPositionIndex()方法判断索引是否有对应的结点，如果没有，抛出异常。

Node<E> node(int index)

功能：返回索引对应的结点。

过程：先判断index与size右移一位后（>>1即除以2）后，如果index在左半部分，则从head结点开始遍历，如果index在右半部分，则从last结点向前开始遍历。

private int indexOf(Object o)

功能：返回对应的o所在结点的索引值，如果有重复则返回第一个结点对应的索引值，如果不存在则返回-1.

过程：判断o是否为空，分为空或非空的分支情况然后从first结点遍历链表，若没有找到则返回-1.

private int lastIndexOf(Object o)

功能：返回对应的o所在结点的索引值，如果有重复则返回最后的一个结点的索引值，如果不存在则返回-1.

过程：判断o是否为空，分为空或非空的分支情况然后从last结点遍历链表，若没有找到则返回-1.

LinkedList模拟Queue方法

public E peek()

功能：返回头结点的元素值。

过程：判断头结点是否为空，为空则返回空，否则返回头结点对应元素。

public E element()

功能：返回头结点的元素值，如果为空则抛出异常。

过程：调用getFirst()方法，并将getFirst()方法的返回值返回。

public E poll()

功能：删除头结点。

过程：删除头结点，如果头为空则返回空，否则调用unlinkFirst()方法并返回该方法的返回值。

public E remove()

功能：删除头结点，如果头结点为空则抛出异常。

过程：调用removeFirst()方法并返回该方法的返回值。

public boolean offer(E e)

功能：添加一个结点至链表尾部。

过程：调用add()方法。

LinkedList模拟Deque方法

public boolean offerFirst(E e)

功能：添加一个结点至链表头部。

过程：调用addFirst()方法并返回true.

public boolean offerLast(E e)

功能：添加一个结点至链表尾部。

过程：调用addLast()方法并返回true.

public E peekFirst()

功能：返回头结点的元素值，如果为空则返回空。

过程：判断头结点是否为空，如果为空则返回null，否则返回头结点元素值。

public E peekLast()

功能：返回尾结点的元素值，如果为空则返回空。

过程：判断尾结点是否为空，如果为空则返回null，否则返回尾结点元素值。

public E pollFirst()

功能：返回头结点的元素值，如果为空则返回空，否则删除头结点。

过程：判断头结点是否为空，如果为空则返回null，否则调用unlinkFirst()并返回该方法的返回值。

public E pollLast()

功能：返回尾结点的元素值，如果为空则返回空，否则删除尾结点。

过程：判断尾结点是否为空，如果为空则返回null，否则调用unlinkLast()方法并返回该方法的返回值。

public void push(E e)

功能：把一个元素添加到链表的头。

过程：调用addFirst()方法。

public E pop()

功能：删除头结点并返回头结点元素值，如果为空链表则抛出异常。

过程：调用removeFirst()并返回该方法的返回值。

public boolean removeFirstOccurrence(Object o)

功能：删除对应元素第一次出现所在的结点。

过程：调用remove()方法并返回该方法返回值。

public boolean removeLastOccurrence(Object o)

功能：删除对应元素最后一次出现所在的结点。

过程：判断o是否为空，分两种情况分别操作。从链表尾部向前遍历链表，遇到第一个符合条件的结点时调用unlink()方法删除，并返回true.如果没有符合条件的结点，则返回false.

Iterator操作

public ListIterator<E> ListIterator(int index)

功能：返回对应索引的迭代器。如果索引越界则抛出异常。

过程：调用checkPositionIndex(index),然后返回一个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)

功能：带参数的构造器。初始化next结点为索引对应链表中的结点，如果为空则返回空。初始化nextIndex为index.

过程：判断index是否等于size，如果等于则复制next为空，否则调用node()方法把索引对应的结点让next引用指向。最后把index赋值nextIndex.

public boolean hasNext()

功能：判断链表是否有下一结点。

过程：返回nextIndex < size结果。

public E next()

功能：判断迭代过程中是否对链表对象进行更改，如果有则抛出异常。然后判断是否有下个元素，如果没有抛出异常。然后返回迭代器指向的下一结点的元素值，然后把迭代器指向下一位。

过程：调用checkForComodification()方法检查在迭代过程中是否对链表对象进行操作（只能使用迭代器提供的方法对链表进行操作），然后调用hasNext()方法判断是否有下一结点，如果没有抛出NoSuchElementException()异常。最后使用内部类成员变量lastReturned指向next指向的结点位置，然后让next引用指向后一结点对象，为nextIndex进行加一操作，返回lastReturned的元素值。

public boolean hasPrevious()

功能：判断当前结点是否还有前结点。

过程：返回nextIndex > 0结果（nextIndex为初始化是传递进来的索引值）。

public E previous()

功能：判断迭代过程中是否对链表对象进行更改，如果有则抛出异常。然后判断是否有上个元素，如果没有抛出异常。然后返回迭代器指向的上一结点的元素值，然后把迭代器指向上一位。

过程：调用checkForComodification()方法检查在迭代过程中是否对链表对象进行操作（只能使用迭代器提供的方法对链表进行操作），然后调用hasPrevious()方法判断是否有下一结点，如果没有抛出NoSuchElementException()异常。最后使用内部类成员变量lastReturned指向next指向的结点位置，然后让next引用指向前一结点对象（为空则置空），为nextIndex进行减减操作，返回lastReturned的元素值。

public int nextIndex()

功能：返回当前结点的索引值。

过程：返回nextIndex.

public int previousIndex()

功能：返回前一结点的索引值。

过程：返回nextIndex – 1.

public void remove()

功能：判断是否在迭代过程中使用非迭代器方法对链表进行操作了（会对链表长度产生变化），如果有则抛出异常。然后判断迭代器是否移动了，如果未移动则抛出异常。然后删除迭代器移动之前所指向结点。

过程：调用checkForComodification()方法判断迭代过程中是否有非迭代器方法对链表长度改变的操作，然后判断lastReturned是否为空，即是否使迭代器位置发生改变。如果未发生改变则抛出异常。然后把lastReturned的下一结点赋值给临时结点引用，调用unlink()方法删除目标结点（迭代器移动前所指向的结点），如果要删除的结点是尾结点，那么next结点引用指向被删结点的next指向结点，否则，nextIndex计数器减减操作。

public void set(E e)

功能：把上一次迭代器改变位置的结点置新值。

过程：判断lastReturned变量是否为空来判断迭代器是否移动过，如果没有移动过则抛出异常，然后调用checkForComodification()方法判断是否有非迭代器方法改变了链表长度，如果有则抛出异常。然后把lastReturned结点的item值更换为传递过来的引用。

public void add(E e)

功能：如果迭代器移动过，则把新元素添加到迭代器上次指向的结点之后。

过程：调用checkForComodification()判断迭代器是否移动过，如果上次移动的位置是结尾，则调用linkLast()方法把元素添加至链表尾部，否则调用linkBefore()方法把元素添加至目标结点后。

public void foreachRemaining(Consumer<? super E> action)

暂时不明确该方法使用方法及实现过程。

final void checkForComodification()

功能：判断是否有非迭代器方法使得链表长度发生改变。

过程：比较modCount和expectedModCount变量，如果在迭代期间调用了操作链表长度的非迭代器内方法，则modCount值会与expectedModCount不同步，抛出异常。

内部类private static class Node<E>

成员变量：E item;          代表一个结点的元素值。泛型E表示。

Node<E> next;              代表指向下一结点的引用。

Node<E> prev;              代表指向前一结点的引用。

Node(Node<E> prev, E element, Node<E> next)

含参构造器，用于初始化。

迭代器方法

public Iterator<E> descendingIterator()

功能：返回一个逆向迭代器的对象。

过程：返回一个DescendingIterator实例。

内部类 private class DescendingIterator implements Iterator<E>

成员变量：private final ListItr itr = new ListItr(size());

建立一个迭代器的实例，让其初始指向链表尾部。

public boolean hasNext()

功能：判断是否有前驱结点并返回真假。

过程：调用ListItr内部类中hasPrevious()方法并返回其返回值。

public E next()

功能：返回前驱结点的元素值。

过程：调用ListItr内部类中previous()方法并返回其返回值。

public void remove()

功能：删除迭代器上次操作指向结点。

过程：调用ListItr内部类中remove()方法。

其他方法

private LinkedList<E> superClone()

功能：调用Object(基类)的clone()方法进行复制操作。

过程：如果不能克隆则抛出异常，否则用super调用Object的clone方法并返回。

public Object clone()

功能：重写Object的clone()方法，用于链表的复制。

过程：调用superClone()方法进行一次浅复制，然后把这个复制的链表对象置空，遍历原链表，然后进行复制，最后返回。

public Object[] toArray()

功能：把链表的元素以Object数组的形式返回。

过程：建立一个大小为size的Object数组，遍历链表把每个结点的元素值赋值给Object数组，最后返回该数组。

public <T> T[] toArray(T[] a)

功能：返回以适当顺序（从第一个元素到最后一个元素）包含此列表中所有元素的数组；返回数组的运行时类型为指定数组的类型。如果指定数组能容纳列表，则在其中返回该列表。否则，分配具有指定数组的运行时类型和此列表大小的新数组。

如果指定数组能容纳列表，并有剩余空间（即数组比列表元素多），则紧跟在列表末尾的数组元素会被设置为 null。（只有 在调用者知道列表不包含任何 null 元素时，才可使用此方法来确定列表的长度。）

private void writeObject(java.io.ObjectOutputStream s)

private void readObject(java.io.ObjectInputStream s)

暂时不明确该方法功能及过程。

public Spliterator<E> spliterator()

功能：返回一个Spliterator迭代器。

过程：返回一个LLSpliterator<E>的实例。

内部类 static final class LLSpliterator<E> implements Spliterator<E>

暂时不明确用法及功能。