Java 源码阅读 - LinkedList

发表于 更新于 分类于 Waline： 阅读次数：

做技术，不能只知其然而不知其所以然。在知道了工具的原理之后，才能更高效的使用这个工具。在程序的世界里，源码里面没有秘密，看懂了源码，也就看懂了原理。

这次就来阅读一下 LinkedList 的源码。

LinkedList 的特性

LinkedList 有如下几个特性：

  • 底层的数据结构是双向链表
  • 存储的数据允许为 null
  • 允许存放重复的数据
  • 元素在 List 中的顺序由添加顺序决定
  • 不是线程安全的

类的声明

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

上面代码声明了一个名为 LinkedList 的泛型类，继承了 AbstractSequentialList，并实现了 List，Deque，Cloneable，Serializable 接口。

AbstractSequentialList 抽象类提供了一个 “骨架” 级别的 List 实现，用来减少实现一个支持顺序读写的 List 的工作量。

Deque 接口约定了要实现一个双向队列 (Double Ended Queue) 所必须要实现的方法。

Cloneable 是一个标记接口，表明了这个类允许使用 Object.clone() 命令进行属性到属性的复制。

Serializable 也是一个标记接口，表明在这个类上启用 Java 的序列化功能。

如何存储数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
transient int size = 0;

/**
    * Pointer to first node.
    * Invariant: (first == null && last == null) ||
    *            (first.prev == null && first.item != null)
    */
transient Node<E> first;

/**
    * Pointer to last node.
    * Invariant: (first == null && last == null) ||
    *            (last.next == null && last.item != null)
    */
transient Node<E> last;

first 和 last 是两个 Node 对象，分别指向了链表中的第一个节点和最后一个节点。size 保存了这个链表中元素的个数。

Node 类是 LinkedList 类中的一个内部类，它定义了一个元素实际上是如何被存储的。

1
2
3
4
5
6
7
8
9
10
11
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;
    }
}

item 是实际存储的数据，next 和 prev 则分别指向了下一个元素和上一个元素。

构造方法

LinkedList 有两个构造方法，分别用来初始化一个空的链表，和从一个给定的集合中取出元素来初始化一个链表。

无参构造方法

1
2
3
4
5
/**
    * Constructs an empty list.
    */
public LinkedList() {
}

无参的构造方法实际上什么都没有做，返回的 LinkedList 对象中，size 为默认值 0，first 和 last 的值都是 null。

从集合初始化的构造方法

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 *
 * @param  c the collection whose elements are to be placed into this list
 * @throws NullPointerException if the specified collection is null
 */
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

这个构造方法首先创建了一个空的 LinkedList，然后调用了 addAll 方法将集合中的数据放到这个链表中。

插入数据

在 LinkedList 中插入数据有三种方式：在头部增加节点、在尾部增加节点，和在某个元素间插入节点。

在头部增加节点

要在链表头部增加节点，可以使用 addFirst(E) 方法。

1
2
3
4
5
6
7
8
/**
 * Inserts the specified element at the beginning of this list.
 *
 * @param e the element to add
 */
public void addFirst(E e) {
    linkFirst(e);
}

该方法又调用了一个 private 方法 linkFirst(E) 实现在头部插入数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Links e as first element.
 */
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++;
}

linkFirst(E) 方法首先取出当前的头部元素 first，然后构造了一个新的 Node 对象，新对象的 prev 值为 null，代表它是一个头部元素，next 值为原来的 first，它存储的数据则是这次插入的数据。然后它将链表的 first 设为这次新增加的元素。

根据链表的特性可以知道，如果一个链表不是空的，那么它的 first 必定非空；反之，如果它的 first 为 null，那么这个链表一定为空。所以根据这个规则，它会判断在插入元素前，这个链表是不是空的，如果是空的，那么新元素就同时作为链表的尾 last；如果不是空的，那么就让原来的 first 的 prev 指向新插入的元素。这样操作之后，新元素与原 first 元素之间就出现了一个双向的引用，即完成了一个小的双向链表。

最后使链表的 size 加一，就完成了一次新增头元素的操作。

在尾部增加节点

在尾部增加节点，可以使用 add(E) 方法或 addLast(E) 方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #add}.
 *
 * @param e the element to add
 */
public void addLast(E e) {
    linkLast(e);
}

/**
 * Appends the specified element to the end of this list.
 *
 * <p>This method is equivalent to {@link #addLast}.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}

可以看出，两个方法都是通过一个 private 方法 linkLast(E) 实现的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * Links e as last element.
 */
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;
    size++;
    modCount++;
}

在尾部插入数据的操作与在头部插入数据的操作类似，依旧是构造一个新的节点，使原来的 last 节点指向新节点，然后根据原链表是否为空执行后续操作。在这里就不多赘述了。

在中间增加节点

要在链表中间插入数据，可以使用 add(int, E) 方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

这个方法所做的操作，简单来说就是，将新的元素放到指定位置，并将原来处于这个位置的元素及其所有后续元素全部后移一个位置。

首先它调用了 checkPositionIndex(int) 方法，我们看看它干了什么。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
 * Tells if the argument is the index of a valid position for an
 * iterator or an add operation.
 */
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

/**
 * Constructs an IndexOutOfBoundsException detail message.
 * Of the many possible refactorings of the error handling code,
 * this "outlining" performs best with both server and client VMs.
 */
private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}

这个方法检查了用户输入的插入位置是不是一个合法的位置，规则就是插入位置必须大于等于 0 且小于等于最大位置。

通过检查之后，它继续判断插入的位置是不是链表的末尾，如果是末尾的话，就直接调用 linkLast(E) 在链表尾部新增一个元素，否则它会先取出现在位于插入位置的节点，然后调用 linkBefore(E, Node) 在链表中间插入元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        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;
    }
}

/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

node(int) 方法巧妙的利用了二分法，根据元素所在的位置来决定是从链表头部还是从尾部开始查找节点。

linkBefore(E, Node) 方法进行的操作，就像我们在书中学习到的一样，先让新节点建立起到左右两个节点的连接，然后让右边的节点连接到新插入的节点，最后更新链表的大小。

用集合批量增加节点

之前我们在 LinkedList 的构造方法中看到了一个 addAll(Collection) 方法，现在就来看看它干了什么。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
 * Appends all of the elements in the specified collection to the end of
 * this list, in the order that they are returned by the specified
 * collection's iterator.  The behavior of this operation is undefined if
 * the specified collection is modified while the operation is in
 * progress.  (Note that this will occur if the specified collection is
 * this list, and it's nonempty.)
 *
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws NullPointerException if the specified collection is null
 */
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

/**
 * Inserts all of the elements in the specified collection into this
 * list, starting at the specified position.  Shifts the element
 * currently at that position (if any) and any subsequent elements to
 * the right (increases their indices).  The new elements will appear
 * in the list in the order that they are returned by the
 * specified collection's iterator.
 *
 * @param index index at which to insert the first element
 *              from the specified collection
 * @param c collection containing elements to be added to this list
 * @return {@code true} if this list changed as a result of the call
 * @throws IndexOutOfBoundsException {@inheritDoc}
 * @throws NullPointerException if the specified collection is null
 */
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;
}

这里的重头戏是 addAll(int, Collection) 方法，它实现了在链表中间批量插入节点的功能。addAll(Collection) 实际上就是调用它在链表末尾批量插入节点。

首先 addAll 方法会检查插入的位置是否合法，如果不合法就会抛出 IndexOutOfBoundsException 异常。然后它将传入的集合转换成一个对象数组，并检查数组长度，如果长度是 0，则说明链表内容未被改变，直接返回 false。

然后它会检查插入的位置，并且记录下插入位置的上一个节点和下一个节点。

接下来这个方法开始遍历传入的集合，并将集合中的数据逐个插入到链表中。插入的逻辑与前面讲的类似，所以就不再赘述了。

最后它会完成一系列收尾工作，包括设定链表尾部的节点，和更新链表的长度，然后返回 true，代表链表成功被更新了。

查询数据

因为 LinkedList 也是一个双向队列，所以它既允许从两端开始获取数据，又可以根据下标从指定位置获取数据。

取出头部的节点

LinkedList 提供了多个方法来允许用户从链表头部取出数据，分别有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Returns the first element in this list.
 *
 * @return the first element in this list
 * @throws NoSuchElementException if this list is empty
 */
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

/**
 * Retrieves, but does not remove, the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

/**
 * Retrieves and removes the head (first element) of this list.
 *
 * @return the head of this list, or {@code null} if this list is empty
 * @since 1.5
 */
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

从头部取出节点的操作都大同小异，区别只是在于取出空值之后是抛异常还是返回 null，以及会不会同时删除头部元素。逻辑很简单，这里就不多赘述了。

除了上面列出的几个方法外，还有 pop()、pollFirst() 等方法也提供了相同的功能，但是代码内容大同小异，所以也不放上来了，以免浪费篇幅。

取出尾部的节点

LinkedList 同样提供了数个方法用于从尾部取出节点，它们的逻辑也基本相同，这里同上文一样，仅展示部分代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * Returns the last element in this list.
 *
 * @return the last element in this list
 * @throws NoSuchElementException if this list is empty
 */
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

/**
 * Retrieves, but does not remove, the last element of this list,
 * or returns {@code null} if this list is empty.
 *
 * @return the last element of this list, or {@code null}
 *         if this list is empty
 * @since 1.6
 */
public E peekLast() {
    final Node<E> l = last;
    return (l == null) ? null : l.item;
}

/**
 * Retrieves and removes the last element of this list,
 * or returns {@code null} if this list is empty.
 *
 * @return the last element of this list, or {@code null} if
 *     this list is empty
 * @since 1.6
 */
public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

取出中间的节点

要从链表中的某个位置取出节点，可以使用 get(int) 方法。

1
2
3
4
5
6
7
8
9
10
11
/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

它首先还是检查了传入的下标是否合法，如果合法就调用 node(int) 方法取得该节点，并返回其数据。node(int) 方法在上面已经介绍过，这里就不重复介绍了。

查询链表是否包含某个数据

LinkedList 提供了 contains(Object) 方法用来查询该链表是否包含某个数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Returns {@code true} if this list contains the specified element.
 * More formally, returns {@code true} if and only if this list contains
 * at least one element {@code e} such that
 * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 *
 * @param o element whose presence in this list is to be tested
 * @return {@code true} if this list contains the specified element
 */
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

/**
 * Returns the index of the first occurrence of the specified element
 * in this list, or -1 if this list does not contain the element.
 * More formally, returns the lowest index {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 * or -1 if there is no such index.
 *
 * @param o element to search for
 * @return the index of the first occurrence of the specified element in
 *         this list, or -1 if this list does not contain the element
 */
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;
}

contains(Object) 方法实际上是调用了 indexOf(Object) 方法，并检查其返回是否为 -1，来判断这个值是否存在于该链表中。

indexOf(Object) 方法的逻辑就是，从链表的头部开始，逐个检查其节点的值是否为传入的值。如果链表为空则直接返回 -1。

修改数据

LinkedList 提供了一个 set(int, E) 的方法用于修改某个节点的数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Replaces the element at the specified position in this list with the
 * specified element.
 *
 * @param index index of the element to replace
 * @param element element to be stored at the specified position
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

该方法首先检查传入的下标是否合法，检查通过后，它会为指定位置的节点设定新的数据，并返回该节点原有的数据。

删除数据

LinkedList 提供了多个方法来从链表中删除节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Removes and returns the first element from this list.
 *
 * @return the first element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

/**
 * Removes and returns the last element from this list.
 *
 * @return the last element from this list
 * @throws NoSuchElementException if this list is empty
 */
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

removeFirst() 和 removeLast() 方法分别可以从链表的头部和尾部取出一个节点，并将其删除。如果链表是空的，则会抛出 NoSuchElementException 异常。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * Removes the element at the specified position in this list.  Shifts any
 * subsequent elements to the left (subtracts one from their indices).
 * Returns the element that was removed from the list.
 *
 * @param index the index of the element to be removed
 * @return the element previously at the specified position
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

remove(int) 方法可以用来取出并删除指定位置下的一个节点，同时所有处于其后方的节点都将向前移动一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * Removes the first occurrence of the specified element from this list,
 * if it is present.  If this list does not contain the element, it is
 * unchanged.  More formally, removes the element with the lowest index
 * {@code i} such that
 * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 * (if such an element exists).  Returns {@code true} if this list
 * contained the specified element (or equivalently, if this list
 * changed as a result of the call).
 *
 * @param o element to be removed from this list, if present
 * @return {@code true} if this list contained the specified element
 */
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

/**
 * Removes the first occurrence of the specified element in this
 * list (when traversing the list from head to tail).  If the list
 * does not contain the element, it is unchanged.
 *
 * @param o element to be removed from this list, if present
 * @return {@code true} if the list contained the specified element
 * @since 1.6
 */
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}

/**
 * Removes the last occurrence of the specified element in this
 * list (when traversing the list from head to tail).  If the list
 * does not contain the element, it is unchanged.
 *
 * @param o element to be removed from this list, if present
 * @return {@code true} if the list contained the specified element
 * @since 1.6
 */
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;
}

remove(Object) 方法和 removeFirstOccurrence(Object) 方法会从头部遍历整个链表，并检查各个节点是否与传入的参数匹配。一旦找到一个匹配的节点就将其删除，并结束操作。removeLastOccurrence(Object) 方法则是从链表尾部开始查找匹配的节点，并删除第一个匹配到的节点。

将 LinkedList 当作栈来操作

上面说过，LinkedList 可以被当成一个双向队列来操作。那么，如果我们把这个队列的底部 “封死”，只操作头部，它是不是就变成了一个栈呢？没错，它是可以这样用的，而且也已经有方法来允许我们这样操作了。实际上，push 和 pop 的操作，就是直接调用了 addFirst(E) 和 removeFirst() 方法来实现入栈和出栈操作的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Pushes an element onto the stack represented by this list.  In other
 * words, inserts the element at the front of this list.
 *
 * <p>This method is equivalent to {@link #addFirst}.
 *
 * @param e the element to push
 * @since 1.6
 */
public void push(E e) {
    addFirst(e);
}

/**
 * Pops an element from the stack represented by this list.  In other
 * words, removes and returns the first element of this list.
 *
 * <p>This method is equivalent to {@link #removeFirst()}.
 *
 * @return the element at the front of this list (which is the top
 *         of the stack represented by this list)
 * @throws NoSuchElementException if this list is empty
 * @since 1.6
 */
public E pop() {
    return removeFirst();
}

迭代

LinkedList 提供了 iterator() 和 listIterator(int) 方法来获取迭代器。实际上这两个方法都将返回一个 ListItr 实例，区别在于 iterator() 是从链表头部开始迭代，而 listIterator(int) 方法则是从指定位置开始迭代。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
private class ListItr implements ListIterator<E> {
    // 上次迭代时返回的节点
    private Node<E> lastReturned;

    // 下一次迭代即将返回的节点
    // 其实也是当前指向但仍未取值的节点
    private Node<E> next;

    // 下一个被迭代节点的位置
    private int nextIndex;

    private int expectedModCount = modCount;

    ListItr(int index) {
        // 判断开始迭代的位置是否为链表末尾
        // 如果不是末尾就取出开始迭代位置的节点，否则取出null
        next = (index == size) ? null : node(index);

        // 将nextIndex指向初始迭代位置
        nextIndex = index;
    }

    // 检查有无下一个节点可供迭代
    public boolean hasNext() {
        // 如果下一个迭代位置的下标小于链表长度
        // 就认为还有元素可供迭代
        return nextIndex < size;
    }

    // 获取下一个节点
    public E next() {
        // 检查链表的结构有没有被修改
        checkForComodification();

        // 如果已经没有节点可供迭代
        // 则抛出NoSuchElementException
        if (!hasNext())
            throw new NoSuchElementException();

        // 取出下一个被迭代的节点
        lastReturned = next;

        // next指针像下一个节点移动
        next = next.next;
        nextIndex++;

        // 取出当前被迭代的节点的值
        return lastReturned.item;
    }

    // nextIndex的初始值为0
    // 当它大于0时，就认定该位置的前面仍有节点可供迭代
    public boolean hasPrevious() {
        return nextIndex > 0;
    }

    // 获取上一个节点
    public E previous() {
        // 检查链表的结构有没有被修改
        checkForComodification();

        // 检查前面有无节点可供迭代
        if (!hasPrevious())
            throw new NoSuchElementException();

        // 检查当前节点是否为null，如果是，就说明当前已经处于链表的末尾，那么就返回链表最后一个节点；
        // 如果不是，就返回当前位置的上一个节点
        // 然后设定当前位置和上一次返回位置为上一个节点
        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();

        // 如果没有上一次被迭代的节点
        // 则抛出IllegalStateException
        if (lastReturned == null)
            throw new IllegalStateException();

        // 取出将被删除节点的下一个节点
        Node<E> lastNext = lastReturned.next;

        // 然后删掉它
        unlink(lastReturned);

        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;

        // 重置上一次被迭代的位置
        lastReturned = null;

        // 因为unlink会使modCound加一
        // 所以这里要同步把expectedModCount加一
        expectedModCount++;
    }

    // 修改上次迭代到的节点的值
    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();

        // 因为lastReturned是某个节点的引用
        // 所以可以直接修改它的值
        lastReturned.item = e;
    }

    // 在下一个被迭代的节点前插入一个节点
    public void add(E e) {
        checkForComodification();
        lastReturned = null;

        if (next == null)
            // 如果已经迭代到链表的末尾，那么就在末尾新增一个节点
            linkLast(e);
        else
            // 否则就在下个被迭代的节点前插入一个节点
            linkBefore(e, next);

        // 游标向后移一位
        nextIndex++;

        // 同步expectedModCount
        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();
    }
}