LinkedList 源码解析

发表于

类结构

LinkedList底层采用双向链表结构存储数据，允许重复数据和null值，长度没有限制：

lkl01.png

每个节点用内部类Node表示：

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

Node节点包含item（存储数据），next（后继节点）和prev（前继节点）。数组内存地址必须连续，而链表就没有这个限制了，Node可以分布于各个内存地址，它们之间的关系通过prev和next维护。

LinkedList类关系图：

lkl02.png

可以看到LinkedList类并没有实现RandomAccess接口，额外实现了Deque接口，所以包含一些队列方法。

LinkedList包含如下成员变量：

1
2
3
4
5
6
7
8
java复制代码// 元素个数，默认为0
transient int size = 0;

// 表示第一个节点，第一个节点必须满足(first == null && last == null) || (first.prev == null && first.item != null)
transient Node<E> first;

// 表示最后一个节点，最后一个节点必须满足(first == null && last == null) || (last.next == null && last.item != null)
transient Node<E> last;

方法解析

构造函数

LinkedList()：

1
java复制代码public LinkedList() {}

空参构造函数，默认size为0，每次添加新元素都要创建Node节点。

LinkedList(Collection<? extends E> c)：

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
java复制代码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;

    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
    // 循环创建节点，设置prev，next指向
    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;
}

该构造函数用于创建LinkedList，并往里添加指定集合元素。

add(int index, E element)

add(int index, E element)指定下标插入元素：

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
java复制代码public void add(int index, E element) {
    // 下标合法性检查
    checkPositionIndex(index);

    if (index == size)
        // 如果插入下标等于size，说明是在尾部插入，执行尾部插入操作
        linkLast(element);
    else
        // 如果不是尾插入，则在指定下标节点前插入
        linkBefore(element, node(index));
}

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

private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

void linkLast(E e) {
    // 获取最后一个节点
    final Node<E> l = last;
    // 创建一个新节点，prev为原链表最后一个节点，next为null
    final Node<E> newNode = new Node<>(l, e, null);
    // 更新last为新节点
    last = newNode;
    if (l == null)
        // 如果原链表最后一个节点为null，说明原链表没有节点，将新节点赋给first
        first = newNode;
    else
        // 否则更新原链表最后一个节点的next为新节点
        l.next = newNode;
    // size递增
    size++;
    // 模数递增，用于快速失败
    modCount++;
}

void linkBefore(E e, Node<E> succ) {
    // succ为原链表指定index位置的节点，获取其prev节点
    final Node<E> pred = succ.prev;
    // 创建新节点，prev为原链表指定index位置的节点的prev节点，next为原链表指定index位置的节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 将原链表指定index位置的节点的prev更新为新节点
    succ.prev = newNode;
    if (pred == null)
        // 如果链表指定index位置的节点的prev为null，说明原链表没有节点，将新节点赋给first
        first = newNode;
    else
        // 否则更新原链表指定index位置的节点的prev的next节点为新节点
        pred.next = newNode;
    // size递增
    size++;
    // 模数递增，用于快速失败
    modCount++;
}

// 采用二分法遍历每个Node节点，直到找到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;
    }
}

无非就是设置节点的prev和next关系。可以看到，除了头插和尾插外，在链表别的位置插入新节点，涉及到节点遍历操作，所以我们常说的链表插入速度快，指的是插入节点改变前后节点的引用过程很快。

get(int index)

get(int index)获取指定下标元素：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
java复制代码public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 采用二分法遍历每个Node节点，直到找到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;
    }
}

通过node函数查找指定index下标Node，然后获取其item属性值，节点查找需要遍历。

set(int index, E element)

set(int index, E element)设置指定下标节点的item为指定值：

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
java复制代码public E set(int index, E element) {
    // 下标合法性检查
    checkElementIndex(index);
    // 获取index下标节点
    Node<E> x = node(index);
    // 获取旧值
    E oldVal = x.item;
    // 设置新值
    x.item = element;
    // 返回旧值
    return oldVal;
}

// 采用二分法遍历每个Node节点，直到找到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;
    }
}

可以看到，set方法也需要通过遍历查找目标节点。

remove(int index)

remove(int index)删除指定下标节点：

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
java复制代码public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

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;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

remove(int index)通过node方法找到需要删除的节点，然后调用unlink方法改变删除节点的prev和next节点的前继和后继节点。

剩下的方法可以自己阅读源码。

RandomAccess接口

RandomAccess接口是一个空接口，不包含任何方法，只是作为一个标识：

1
2
3
java复制代码package java.util;

public interface RandomAccess {}

实现该接口的类说明其支持快速随机访问，比如ArrayList实现了该接口，说明ArrayList支持快速随机访问。所谓快速随机访问指的是通过元素的下标即可快速获取元素对象，无需遍历，而LinkedList则没有这个特性，元素获取必须遍历链表。

在Collections类的binarySearch(List<? extends Comparable<? super T>> list, T key)方法中，可以看到RandomAccess的应用：

1
2
3
4
5
6
7
java复制代码public static <T>
int binarySearch(List<? extends Comparable<? super T>> list, T key) {
    if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
        return Collections.indexedBinarySearch(list, key);
    else
        return Collections.iteratorBinarySearch(list, key);
}

当list实现了RandomAccess接口时，调用indexedBinarySearch方法，否则调用iteratorBinarySearch。所以当我们遍历集合时，如果集合实现了RandomAccess接口，优先选择普通for循环，其次foreach；遍历未实现RandomAccess的接口，优先选择iterator遍历。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%