jdk LinkedList工作原理分析

发表于 | 阅读次数

jdk LinkedList工作原理分析

List接口的实现类之一ArrayList的内部实现是一个数组，而另外一个实现类LinkedList的内部实现是使用双向链表。

继承结构

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

LinkedList是一个继承于AbstractSequentialList的双向链表。可以被当作双端队列进行操作。

LinkedList是非同步的。

成员变量

1
2
3
4
5
6
//链表的节点数量
transient int size = 0;
//链表的首节点
transient Node<E> first;
//链表的尾节点
transient Node<E> last;

我们看下node的节点定义。

Node结构

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

构造函数

LinedList有一个无参的构造函数，和一个集合参数构造函数。

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
public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
    //调用无参构造函数
    this();
    addAll(c);
}

public boolean addAll(Collection<? extends E> c) {
    //传入当前节点个数，此时size为0，并将collection对象传入进去
    return addAll(size, c);
}

public boolean addAll(int index, Collection<? extends E> c) {
    // 索引越界检查
    checkPositionIndex(index);
    //将collection转换为数组对象
    Object[] a = c.toArray();
    //需要添加的元素数量
    int numNew = a.length;
    if (numNew == 0)
        return false;
    
    Node<E> pred, succ;
    if (index == size) {   //把集合c插入到最后面
        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节点是最后一个插入的节点
        last = pred;
    } else {    //如果插入中间，最后插入节点的下一个节点当前节点，当前节点的上一个节点是最后插入节点
        pred.next = succ;
        succ.prev = pred;
    }
    size += numNew;    //节点大小增加集合的元素数量
    modCount++;    //修改次数+1
    return true;
}

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

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

//node方法根据索引找到对应的节点
Node<E> node(int index) {
    // 如果索引比链表的数量一半还要小，从前往后找，花费O（n）时间
    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;
    }
}

方法

我们还是挑选几个主要的方法讲解一下。

boolean add(E e)

添加元素到链表的最后位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    //添加元素到链表的尾部，所以这个新节点是链表的最后一个节点，它的前节点是目前链表的尾节点，后节点为null
    final Node<E> newNode = new Node<>(l, e, null);
    //尾节点变成新节点
    last = newNode;
    //如果一开始节点还没有设置，那么新节点也就是第一个节点（首节点）
    if (l == null)
        first = newNode;
    else    //否则新节点是目前链表尾节点的下一个节点
        l.next = newNode;
    size++;    //节点数加1
    modCount++;     //修改次数加1
}

上图第一个图表示已经有1，2节点的LinkedList调用add方法，第二个图表示添加一个节点3后的情况。

原先尾节点的下一个节点变为节点3，新节点3的前节点变为原先的尾节点2，新节点的后节点为null，同时链表的尾节点变为节点3

void 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
public void add(int index, E element) {
    checkPositionIndex(index);   //检查索引不能超过链表的个数，不能小于0
    if (index == size)   //如果在链表的尾部插入节点，则调用linlast方法，上面已分析
        linkLast(element);
    else   //否则调用linbefore方法，参数为要插入的元素和节点对象
        linkBefore(element, node(index));
}

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++;
}
//succ节点的位置是要插入节点的位置
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    //1： 新节点的前节点是succ节点的前节点，后节点是succ节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    //2： succ节点的前节点是新节点
    succ.prev = newNode;
    if (pred == null) //如果succ是首节点，则只需要重新设置下新节点为首节点就好了，首节点的下一个节点在步骤1设置过了
        first = newNode;
    else    
        pred.next = newNode;     3：succ的前节点的后节点是新节点
    size++;
    modCount++;
}

上面图中的1，2，3对应下图

E 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
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;  //1
        x.prev = null;  //1
    }
    if (next == null) {  //如果删除的是尾节点
        last = prev;
    } else {
        next.prev = prev;  //2
        x.next = null;  //2
    }
    x.item = null;  //3
    size--;
    modCount++;
    return element;
}

上面代码中的1，2，3在如图中表示

E get(int index)

获取索引位置上的元素

1
2
3
4
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;  //通过上面介绍的算法找到节点，返回节点元素值
}

ListIterator listIterator(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
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
public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    private int expectedModCount = modCount;
    ListItr(int index) {
        // assert isPositionIndex(index);
        next = (index == size) ? null : node(index);
        nextIndex = index;
    }
    public boolean hasNext() {
        return nextIndex < size;
    }
    public E next() {
        checkForComodification();
        if (!hasNext())
            throw new NoSuchElementException();
        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }
    public boolean hasPrevious() {
        return nextIndex > 0;
    }
    public E previous() {
        checkForComodification();
        if (!hasPrevious())
            throw new NoSuchElementException();
        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();
        if (lastReturned == null)
            throw new IllegalStateException();
        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);
        if (next == lastReturned)
            next = lastNext;
        else
            nextIndex--;
        lastReturned = null;
        expectedModCount++;
    }
    public void set(E e) {
        if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();
        lastReturned.item = e;
    }
    public void add(E e) {
        checkForComodification();
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        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();
    }
}

LinkedList和ArrayList的比较

1.两者的设计理念不同，ArrayList是基于数组，而LinkedList基于节点，也就是链表。所以LinkedList没有容量的概念。

2.两者的使用场景不同。ArrayList适用于读多写少的场景，LinkedList适用于写多读少的场景。

因为LinkedList要找到节点的必须要遍历一个一个的节点，直到找到为止。而ArrayList完全不需要，因为ArrayList内部维护一个数组，直接根据索引找到需要的元素就好了。