文章首发于：clawhub.club

介绍

LinkedList继承图谱.png

LinkedList双端链表.png

  • LinkedList实现了 List 接口:可以作为链表（常用的方法有 add()、remove()、get()）使用。
  • LinkedList实现了 Deque（双端队列）接口:可以作为队列（常用的方法有 offer()、poll()、peek()）使用（FIFO）。
  • LinkedList内部是双向链表结构，从链表的任一端都可以遍历，所以 LinkedList 还可以作为堆栈（常用的方法有 push()、pop()）使用。

属性

都不参与序列化。

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;

构造方法

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
   //无参构造
   public LinkedList() {
   }
   //构造一个包含指定 collection 中的元素的列表，这些元素按其 collection 的迭代器返回的顺序排列。
   public LinkedList(Collection<? extends E> c) {
       this();
       addAll(c);
   }
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;

       // pred 指向当前索引位置的前一个 node（node.prev），succ 指向当前索引位置上的 node
       Node<E> pred, succ;
       // 如果索引是链表的元素个数，这个索引位置是没有 node 的，索引 succ = null，这个索引的前一个位置是链表的末尾，所以 pred = last
       if (index == size) {
           succ = null;
           pred = last;
       // 否则，succ 指向当前索引的 node，pred 指向 succ 的前一个 node
       } 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);
           // 如果是从链表头部开始的添加，first 要指向第一个插入元素封装的新 node
           if (pred == null)
               first = newNode;
           // 否则当前 node 的前一个 node 的 next 指向自己
           else
               pred.next = newNode;
           pred = newNode;
       }

       // 插入完后，改变 last 的指向位置
       // 如果是从 index == size 开始插入的，last 指向添加进来的最后一个 node
       if (succ == null) {
           last = pred;
       // 否则，succ 和 pred 互相指向，因为是双向链表嘛，这样才使新添加的链表和 index （包括 index）前面的链表连接上
       } else {
           pred.next = succ;
           succ.prev = pred;
       }

       // 链表长度加上数组长度，修改次数加 1
       size += numNew;
       modCount++;
       return true;
   }

核心方法

linkLast(E e)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 链接 e 元素作为（链表的）最后一个元素
 */
void linkLast(E e) {
     // 复制 last 引用
    final Node<E> l = last;
    // 用元素 e 构造新 node
    final Node<E> newNode = new Node<>(l, e, null);
    // last 指向新 node
    last = newNode;
    // 如果原链表为空，也即是 first，last 都指向 null，此时插入尾部的 node，first 和 last 都指向这个 node
    if (l == null)
        first = newNode;
    // 原链表不为空，将原尾部 node 的 next 指向这个新 node
    else
        l.next = newNode;
    // 链表长度加 1，修改次数加 1
    size++;
    modCount++;
}

linkBefore(E e, Node succ)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 在非 null 的 node succ 前插入元素 e
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null; 这行代码在源码中就是注释掉的，对于 succ 非 null 判断是该方法调用的外部进行的
    // 复制 node succ 的 prev 引用
    final Node<E> pred = succ.prev;
    // 用元素 e 构造新 node
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    // 如果 node succ 前面没有 node，说明 succ 就是链表中的第一个元素，将 succ 的 prev 指向新 node
    if (pred == null)
        first = newNode;
    // 否则就将 node succ 的前一个 node 的 next 指向新 node
    else
        pred.next = newNode;
    // 链表长度加 1，修改次数加 1
    size++;
    modCount++;
}

linkFirst(E e)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 链接 e 元素作为（链表的）第一个元素
 */
private void linkFirst(E e) {
    // 复制 first 引用
    final Node<E> f = first;
    // 用元素 e 构造新 node
    final Node<E> newNode = new Node<>(null, e, f);
    // fisrt 指向新 node
    first = newNode;
    // 如果原链表为空，也即是 first，last 都指向 null，此时插入头部的 node，first 和 last 都指向这个 node
    if (f == null)
        last = newNode;
    // 原链表不为空，将原头部 node 的 prev 指向这个新 node
    else
        f.prev = newNode;
    // 链表长度加 1，修改次数加 1
    size++;
    modCount++;
}

node(int index)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 返回指定元素索引的 node
 */
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 这里编写者将查找的次数从 n 降到了 n/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;
    }
}

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
/**
 * 不链接非 null node x，即将 node x 从链表中删除
 */
E unlink(Node<E> x) {
    // assert x != null;
    // 复制 node x 中元素的值
    final E element = x.item;
    // 复制 node x 前一个和后一个 node 的引用
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    // 如果 node x 的前一个 node 为 null，也即是 node x 为链表头部第一个 node，first 只能指向 node 的后一个 node 了
    if (prev == null) {
        first = next;
    // 否则，node x 的前一个 node 的 next 指向 node x 的后一个 node，node x 的 prev 指向 null（这样更加安全，避免后面再次使用 node x 会对原链表产生影响）
    } else {
        prev.next = next;
        x.prev = null;
    }

    // 如果 node x 的后一个 node 为 null，也即是 node x 为链表尾部最后一个 node，last 只能指向 node 的前一个 node 了
    if (next == null) {
        last = prev;
    // 否则，node x 的后一个 node 的 prev 指向 node x 的前一个 node，node x 的 next 指向 null（这样更加安全，避免后面再次使用 node x 会对原链表产生影响）
    } else {
        next.prev = prev;
        x.next = null;
    }

    // help GC
    x.item = null;
    // 链表长度减 1，修改次数加 1
    size--;
    modCount++;
    // 返回删除的 node 的元素的值
    return element;
}

unlinkFirst(Node f)

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
/**
 * 不链接非空的第一个 node f，即将 node f 从链表头部删除
 */
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    // 复制 node f 中元素的值
    final E element = f.item;
    // 复制 node f 后一个 node 的引用
    final Node<E> next = f.next;
    // 将 item，next 指向为 null，利于垃圾回收器回收 f.item 和 f.next 指向的对象
    f.item = null;
    f.next = null; // help GC
    // fisrt 指向 node f 后一个 node
    first = next;
    // 如果这个链表只有 node f 这一个元素，删除 f 后，first 和 last 都指向 null
    if (next == null)
        last = null;
    // 否则，node f 后一个 node 的 prev 指向 null
    else
        next.prev = null;
    // 链表长度减 1，修改次数加 1
    size--;
    modCount++;
    // 返回删除的 node 的元素值
    return element;
}

内部方法区别

以下封装的方法底层都是对双端链表的操作。

链表

add

add(E e):将指定的元素追加到此列表的末尾。

1
2
3
4
public boolean add(E e) {
    linkLast(e);
    return true;
}

add(int index, E element):将指定元素插入到列表中的指定位置。将当前位于该位置的元素(如果有的话)和随后的任何元素向右移动(将一个元素添加到它们的索引中)。

1
2
3
4
5
6
7
8
public void add(int index, E element) {
    checkPositionIndex(index);

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

addFirst(E e):在列表的开头插入指定的元素。

1
2
3
public void addFirst(E e) {
    linkFirst(e);
}

addLast(E e):将指定的元素追加到此列表的末尾。

1
2
3
public void addLast(E e) {
    linkLast(e);
}

set

用指定的元素替换列表中指定位置的元素。

1
2
3
4
5
6
7
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

remove()

remove(Object o):从列表中删除指定元素的第一个出现项(如果存在)。如果这个列表不包含这个元素，它将保持不变。更正式地说，删除索引最低的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}

removeFirst():从列表中移除并返回第一个元素。

1
2
3
4
5
6
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

get()

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

1
2
3
4
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

队列

offer()

将指定的元素添加为列表的尾部(最后一个元素)。

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

poll()

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

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

peek()

检索但不删除此列表的头(第一个元素)。

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

栈

push()

检索但不删除此列表的头(第一个元素)。从这个列表表示的堆栈中弹出一个元素。换句话说，删除并返回列表的第一个元素。这个方法相当于{@link #removeFirst()}。

1
2
3
public E pop() {
    return removeFirst();
}

pop()

将元素推入此列表所表示的堆栈。换句话说，将元素插入到列表的前面。

1
2
3
public void push(E e) {
    addFirst(e);
}

参考资料

https://snailclimb.gitee.io/javaguide/#/./java/LinkedList
http://wiki.jikexueyuan.com/project/java-enhancement/java-twentytwo.html
https://juejin.im/post/5c0e4cd65188251595127f44