Java源码之LinkedList

发表于   |   分类于 ，   |     |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/08/29/Java源码之LinkedList/

访问原文「Java源码之LinkedList」

关于LinkedList

似乎我们在工作中很少用到LinkedList，大部分都是使用ArrayList。先来看一下LinkedList的定义吧，它是List和Deque接口的双向链表实现；实现所有可选列表操作，并允许所有元素（包括null）；所有的操作都实在操作双向列表；索引到列表中的操作将从开始或结束遍历列表，以更接近指定的索引为准。从这个定义来看，这个LinkedList更适合较多插入和删除元素，较少读取元素，因为插入和删除元素不涉及重排数据。

至于Deque是什么。Deque是支持两端元素插入和移除的线性集合，而名称deque是双端队列(double ended queue)的缩写，通常发音为deck。既然它是个列表，那它确实继承了Queue，也支持所有与Queue相关的进、出方法。本文不再对deque做详细说明。

LinkedList主要成员变量

下面是LinkedList的主要成员变量。可以看到包含头指针和尾指针，而Node也是双向链表节点的表示，也就是说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
// 列表大小
transient int size = 0;
/**
 * 指向头结点的指针
 */
transient Node<E> first;
/**
 * 指向尾节点的指针
 */
transient Node<E> last;
// Node类
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;
    }
}

LinkedList核心方法

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
/**
 * 将e作为头节点加入链表中
 */
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++;
}
/**
 * 将e作为尾节点加入链表中
 */
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++;
}
/**
 * 将e插入至节点succ前.
 */
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++;
}
/**
 * 删除头节点f，f == first && f != null;
 */
private E unlinkFirst(Node<E> 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;
}
/**
 * 删除尾节点l，l == last && l != null;
 */
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}
/**
 * 删除中间节点x，x != null
 */
E unlink(Node<E> x) {
    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;
}

List常用方法

为什么叫List常用方法，因为LinkedList是双向队列，包含队列操作，这节不予说明。
下面列出了add、remove、get这三个常用方法。从前两个方法可以看到它用到了上节介绍的核心方法；而get方法可以看到是一个遍历搜索的方法，可以明显的发现如果这个列表的get方法在使用中频繁出现，那么我们应该选择ArrayList而不是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
/**
 * 将元素加入至链表尾部
 *
 * 等同于addLast
 *
 * @param e 将要加入列表的元素
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    linkLast(e);
    return true;
}
/**
 * 从列表中删除指定元素的第一个出现（如果存在）。如果此列表不包含该元素，则它不会更改。
 * 正式的说，删除具有最低索引i的元素，使得(o==null?get(i)==null:o.equals(get(i)))。
 * 如果列表包含这个元素则返回true
 *
 * @param o 需要删除的元素
 * @return 如果列表包含这个元素则返回true
 */
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;
}
/**
 * 返回指定位置的元素
 *
 * @param index 元素位置（索引）
 * @return 指定位置的元素
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
/**
 * 返回指定位置的元素
 * 位置离头节点近的话从头节点往后搜
 * 位置离尾节点近的话从尾节点往前搜
 */
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;
   }
}

Deque常用方法

与上节相似，因为LinkedList实现了Deque接口，包含队列和栈操作，这节将介绍几个常用的队列和栈操作。
下面列出了peek、poll、offer、push、pop这五个常用方法。peek方法直接返回头节点，poll方法等同于第三节介绍的unlinkFirst方法，offer方法最终等同于linkLast，push方法等同于addFirst方法，而addFirst方法实际上等同于第三节介绍的linkFirst方法，pop方法最终等同于unlinkFirst。peek、poll、offer这三个方法实现了队列这一先入先出的数据结构，而push、pop这两个方法实现了栈这一先入后出的数据结构。

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
/**
 * 获取头节点，但不删除
 *
 * @return 返回头节点，如果队列为空则返回null
 * @since 1.5
 */
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}
/**
 * 获取头节点，并删除
 *
 * @return 返回头节点，如果队列为空则返回null
 * @since 1.5
 */
public E poll() {
   final Node<E> f = first;
   return (f == null) ? null : unlinkFirst(f);
}
/**
 * 将元素加入列表尾部.
 *
 * @param e 加入的元素
 * @return true
 * @since 1.5
 */
public boolean offer(E e) {
    return add(e);
}
/**
 * 在该列表的前面插入元素
 *
 * @param e 插入的元素
 * @since 1.6
 */
public void push(E e) {
    addFirst(e);
}
/**
 * 删除并返回头节点
 *
 * @return 头节点
 * @throws NoSuchElementException if this list is empty
 * @since 1.6
 */
public E pop() {
    return removeFirst();
}

总结一下

LinkedList作为一个平时不常使用的类其结构是比较简单的。由于其内部表示为链表结构，所以核心方法均为链表操作。进而所有的主要方法都是由这些核心方法扩展而来。
本文只介绍几个常用的方法，实际上LinkedList中包含了很多其他方法，例如：addFirst、addLast、removeLast、offerFirst、offerLast等等，实际上都是由本文第三节介绍的核心方法扩展或者仅仅是改了名字，有兴趣的同学可以详细学习一下，我这里就不详细介绍了。

Jerky Lu wechat
欢迎加入微信公众号