关于 LinkedList

发表于 更新于 分类于

LinkedList 的 DOC 注释

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
/**
 * Doubly-linked list implementation of the {@code List} and {@code Deque}
 * interfaces.  Implements all optional list operations, and permits all
 * elements (including {@code null}).
 * 该双向链表实现了 List 接口和 Deque 接口。实现了 list 的所有可选操作，并且允许(添加)所有元素(包括 null)。
 * <p>All of the operations perform as could be expected for a doubly-linked
 * list.  Operations that index into the list will traverse the list from
 * the beginning or the end, whichever is closer to the specified index.
 * 对于该双向链表，所有操作都是可预期的。如果对 list 的操作涉及到指定索引位置的元素，那么将判断指定的索引离 begin 更近，还是离 end 更近。这样能进行更少次数的迭代，性能更好。
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access a linked list concurrently, and at least
 * one of the threads modifies the list structurally, it <i>must</i> be
 * synchronized externally.  (A structural modification is any operation
 * that adds or deletes one or more elements; merely setting the value of
 * an element is not a structural modification.)  This is typically
 * accomplished by synchronizing on some object that naturally
 * encapsulates the list.
 * 需要注意的是 LinkedList 类并不是线程安全的。如果多线程同时访问 linked list，而且至少一个线程会修改 list 的结构，那么它的外部必须使用 synchronized 关键字。(结构性修改指的是 插入(add)或者删除(remove)操作，修改一个元素的值并不是结构性修改)。这通常通过同步(synchronized 修饰)一个 封装了 list 的对象来实现。
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new LinkedList(...));</pre>
 * 如果手头儿没有这样的对象，list 应该被 Collections.synchronizedList() 包裹起来。最好在初始化 LinkedList 对象时候就这样去做，以免不可预知的对 list 的非同步访问。
 * <p>The iterators returned by this class's {@code iterator} and
 * {@code listIterator} methods are <i>fail-fast</i>: if the list is
 * structurally modified at any time after the iterator is created, in
 * any way except through the Iterator's own {@code remove} or
 * {@code add} methods, the iterator will throw a {@link
 * ConcurrentModificationException}.  Thus, in the face of concurrent
 * modification, the iterator fails quickly and cleanly, rather than
 * risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 * 通过LinkedList 的 iterator() 方法，或者 listIterator(int) 方法返回的 iterator 都是 fail-fast(快速失效)的：如果在创建 iterator 之后，任何对 list 的结构性修改，都会抛出 ConcurrentModificationException，除了 iterator 本身的 remove() 和 add() 方法。因此，在面临并发对 list 的修改时，iterator 会快速而干净的失效，而不是在未来不确定的时间冒着任意的、不确定的风险。
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:   <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 * 另外，需要注意的是，，iterator 的 fail-fast 行为是不能被保证的，，通常来说，在并发非同步对 list 的修改时，任何硬性的保证都是不可能的。fail-fast 会让 iterator 尽可能抛出 ConcurrentModificationException。因此，在程序中通过依赖抛出 ConcurrentModificationException 异常来保证自身的正常运行是错误的：fail-fast 行为只应该用来 debug。
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author  Josh Bloch
 * @see     List
 * @see     ArrayList
 * @since 1.2
 * @param <E> the type of elements held in this collection
 */
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

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
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
159
160
161
162
163
164
165
166
167
168
169
170
171
transient int size = 0;

/**
 * Pointer to first node. // 指向 LinkedList 的第一个节点
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node. // 指向 LinkedList 的最后一个节点
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

/**
 * Constructs an empty list.
 * 构造一个空 list
 */
public LinkedList() {
}

/**
 * Constructs a list containing the elements of the specified
 * collection, in the order they are returned by the collection's
 * iterator.
 * 通过指定的 collection 构造一个包含元素的 list，其顺序由 collection 的迭代器决定。
 * @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);
}

/**
 * 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.)
 * 将指定的 collection 的所有元素拼接到 list 的末尾元素之后，顺序由指定的 collection 的迭代器决定。在执行该操作(addAll())的时候，如果 collection 被修改了，该操作的行为将不可预知(请注意，如果指定的 collection 正好是该 list 对象自己，那么这种情况将会发生)。
 * @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.
 * 从指定的位置开始将指定 collection 中的所有元素插入到该 list 中。指定位置的元素(如果有的话)及其右边的元素将会右移(原索引值增大)。新的元素将会以指定 collection 的迭代器 返回的顺序出现在 list 中。
 * @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);

    // 将 collection 转为数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 如果为空数组，返回 false
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    // 如果索引值与容器的大小相同，即当前 LinkedList 实例中无任何元素
    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 节点对象 newNode
        Node<E> newNode = new Node<>(pred, e, null);
        // 如果指定位置的元素位于列表头部，则 newNode 为 first 节点
        if (pred == null)
            first = newNode;
        else
            // 否则，前一个节点的 next 属性指向 newNode
            pred.next = newNode;
        // pred 指向 newNode，开始下一轮遍历(相当于常规 for 循环的 i++)
        pred = newNode;
    }

    // 如果原 list 为空列表，则经过遍历之后，last 指向 pred
    if (succ == null) {
        last = pred;
    } else {
        // 如果指定索引位置有值，遍历添加 collection 中的元素之后，指定索引位置的元素及其右侧的所有元素统一右移，，将新增的所有元素中的最后一个元素的 next 指向 右移的元素中的第一个元素；右移的元素中的第一个元素的 prev 属性指向新增元素中的最后一个。
        pred.next = succ;
        succ.prev = pred;
    }

    // 原 size 加上 新增元素的数量
    size += numNew;
    // list 的结构性更改次数 +1
    modCount++;
    return true;
}

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.
 * 判断参数代表的索引位置在 iterator 或者 add() 中是否可用
 */
private boolean isPositionIndex(int index) {
    // 不小于零，且不大于 size
    return index >= 0 && index <= size;
}

/**
 * Returns the (non-null) Node at the specified element index.
 * 返回指定位置的非空节点
 * 此处遍历 list 查找指定位置的元素时，先判断 index 距离 begin 节点近还是 end 节点。如此可以减少遍历次数，有助于性能表现。大概这就是维护成双向列表而非单向列表的原因吧。
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    // 指定的索引值是否小于中位数(翻译成人话就是，判断索引是否在列表的前半段)
    if (index < (size >> 1)) {
        Node<E> x = first;
        // 就是硬遍历，直到指定索引位置
        //  因为 i < index，所以会遍历到指定索引位置的前一个节点，这时取其 next 指向的节点即可。
        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;
    }
}

// 私有静态内部类
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        // item 为当前节点的值
        this.item = element;
        // next 指向当前节点的下一个节点
        this.next = next;
        // prev 指向当前节点的前一个节点
        this.prev = prev;
    }
}

关于关键字 transient，，
一个对象只要实现了 Serializable 接口，该对象就可以被序列化。然而在实际开发过程中，常常会遇到这样的问题，该类有些属性需要序列化，其他属性不需要被序列化。例如一个用户有一些敏感信息（如密码，银行卡号等），为了安全起见，不希望在网络操作（主要涉及序列化）中被传输，这些信息对应的变量就可以加上 transient 关键字，这样变量的生命周期仅存在于调用者的内存中而不会被写到磁盘里持久化。)

首尾节点的操作

因为 first 和 last 属性的存在，所以在 LinkedList 中首尾节点的操作效率很高，以 getFirst() 和 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 查
/**
 * 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;
}

// 删
 /**
 * 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);
}
/**
 * Unlinks non-null first node f.
 * 首先 first 节点的 prev 肯定是 null，先复制它的 next 节点，然后将它的 item 和 next 置空，至此，，first 节点就是一个空的 Node 对象了，最终被 GC。然后判断 next 节点，如果它为null，则说明该 LinkedList 对象只有一个 Node，否则将 first 指向 刚才复制的 next 节点。最后 size 减 1，modCount 加 1。
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 断言 f 为 first 节点，且 f 不为空
    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;
}
// '改'就不说了
// '增'其实是 removeFirst() 反向操作，略。

关于 modCount 👇

1
2
3
4
5
6
7
8
9
10
/**
 * The number of times this list has been structurally modified.
 * 该列表在结构上被修改的次数
 */
protected transient int modCount = 0;

modCount 为 AbstractList(
class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable =>
abstract class AbstractSequentialList<E> extends AbstractList<E> =>
abstract class AbstractList<E> extends AbstractCollection<E> implements List<E>)的属性

非首尾节点的操作

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
// 删
/**
 * Removes the element at the specified position in this list.
 * 删除该列表指定位置的元素
 */
public E remove(int index) {
 checkElementIndex(index);
    return unlink(node(index));
}
/**
 * Returns the (non-null) Node at the specified element index.
 * 返回指定位置的非空node，，判断 index 在 LinkedList 的前半部分还是后半部分，然后取循环次数少的分支进行遍历。
 */
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 保证不会抛出 IndexOutOfBoundsException 异常

    // >>：带符号右移。正数右移高位补0，负数右移高位补1。
    // 比如：4 >> 1，4 的二进制为 100，移位之后变为 10，即十进制 2。
    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;
    }
}
/**
 * Unlinks non-null node x.
 */
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // 如果要移除的元素位于头节点，则直接将头节点指向下一个节点。
    // 否则将前一个节点的 next 属性指向下一个节点，并将当前节点的 prev 属性置空
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    // 如果要移除的元素位于尾节点，则直接将尾节点指向前一个节点。
    // 否则将下一个节点的 prev 属性指向前一个节点，并将当前节点的 next 属性置空
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    // 将当前节点的 item 属性置空
    x.item = null;
    // 长度 -1
    size--;
    // 结构性修改次数 +1
    modCount++;
    return element;
}

// 增
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
// linkLast 与 linkBefore 方法类似，以 linkBefore 为例
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    // succ 为插入前 index 位置的节点，需要做的是将新节点的 prev 属性指向 succ.prev，将新节点的 next 属性指向 succ。
    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++;
}

另外值得注意的是，LinkedList 支持插入 null 值，原因在于 Node 的构造方法。插入 null 值时，其实是将 null 值给了 node 节点的 item 属性，node 节点的 prev 和 next 还是 非 null 的。

—- update@2019-03-18 22：23：47 下面—-
发现个知识点，，今天点开 LinkedList 中实现的 Deque接口，DOC注释中这样写道：👇

A linear collection that supports element insertion and removal at both ends. The name deque is short for “double ended queue” and is usually pronounced “deck”.
Deque 是支持双端插入和删除元素的线性集合，deque 是 double ended queue 的缩写，通常读作 deck。

总结

LinkedList 的本质是双向链表。与 ArrayList 相比，LinkedList 的插入和删除速度更快，但是随机访问速度则很慢。测试表明，对于 10 万条的数据，与 ArrayList 相比，随机提取元素时存在数百倍的差距。除继承 AbstractList 抽象外，LinkedList 还实现了另一个接口 Deque，即 double-ended-queue。这个接口同时具有队列和栈的性质。LinkedList 包含 3 个重要的成员：size、first、last。size 是双向链表中节点的个数。first 和 last 分别指向第一个和最后一个节点的引用。LinkedList 的优点在于可以将零散的内存单元附加引用的方式关联起来，形成按链路顺序查找的线性结构，内存利用率较高。

码出高效 Java 开发手册 P156

  1. 清浅池塘—LinkedList 初探
  2. 何柄融—ArrayList 和 LinkedList 的区别和使用场景(有删改)