[Java]-Collection源码分析-LinkedList

发表于 | 分类于 | 阅读次数

ArrayList查找性能优秀，但是增删较慢，LinkedList则相反。

LinkedList既实现了List又实现了queue，它的内部实现是一个双向链表。

继承关系


可以看到它继承于List 和 Deque

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

成员变量

链表大小，头指针，尾指针

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

transient Node<E> first;

transient Node<E> last;

    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;
        }
    }

构造函数

无参构造函数：一个空链表，只有为null的头尾指针，size=0

有参构造函数：从一个集合构造链表。其中this()可以用来调用当前类的构造函数。然后将集合加入liste。

其中取某个index的节点的代码判断了当前的节点在链表的前半段还是后半段，来决定从头节点开始遍历还是从尾节点开始遍历。二分之一运算用位运算做，速度快省内存效率高（如8*2在底层是用加法实现的，还要判断进位溢出等）。这个方法提高了链表查询的效率。

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


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;
    }

    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;
}

===
//取某个节点
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;
    }
}

====
private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
=======
//当前要取的下标是否合法。index == size --> null
private boolean isPositionIndex(int index) {
    return index >= 0 && index <= size;
}

方法

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
//将某节点拼接在链表头部
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++;
}

//将某节点拼接在链表尾部
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++;
}

//将某节点拼接在某节点前边
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++;
}

private E unlinkFirst(Node<E> f) {
   ···
}

private E unlinkLast(Node<E> l) {
	···
}
    
E unlink(Node<E> 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
   public E peek() {
       final Node<E> f = first;
       return (f == null) ? null : f.item;
   }

   public E element() {
       return getFirst();
   }

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

//队头删除元素
   public E remove() {
       return removeFirst();
   }
   
   
   public E removeFirst() {
       final Node<E> f = first;
       if (f == null)
           throw new NoSuchElementException();
       return unlinkFirst(f);
   }

//队尾加入元素
   public boolean offer(E e) {
       return add(e);
   }

栈的实现：

1
2
3
4
5
6
7
8
9
//从头部加入从头部删除
public void push(E e) {
    addFirst(e);
}

//unlinkFirst实现
public E pop() {
    return 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
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
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;
       }
	
	//小于size
       public boolean hasNext() {
           return nextIndex < size;
       }

       public E next() {
           checkForComodification();
           if (!hasNext())
               throw new NoSuchElementException();

           lastReturned = next;
           next = next.next;
           nextIndex++;
           return lastReturned.item;
       }
	
	//index不是第一个
       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非常适合大量数据的插入与删除，但其对处于中间位置的元素，无论是增删还是改查都需要折半遍历（找到要插入位置的节点），这在数据量大时会十分影响性能。在使用时，尽量不要涉及查询与在中间插入数据，另外如果要遍历，也最好使用foreach，也就是Iterator提供的方式。

ArrayList适合查询，不适合大量的增删操作，LinkedList适合数据的插入和删除（非中间位置），查找性能较差，LinkedList同时实现了队列和栈。Deque是一个双端循环队列。

LinkedList（链表实现）和ArrayDeque（数组实现）都可以用来实现队列和栈，ArrayDeque是推荐的实现队列和栈的方法，效率较高，因为在确定了插入或删除位置时，ArrayDeque的插入或删除是O（1）.ArrayDeque是非线程安全的，需要程序员来保证安全。