1. 简介

LinkedList基于链表实现，非线程安全，其既实现了List接口又实现了Deque接口，所以既可以做为列表使用又可以做双端队列使用，队头队尾插入删除时间复杂度都为O(1)，查找效率为O(n)。

2. 实现

结点类型

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

属性

1
2
3
4
5
6
7
8
// 结点数量
transient int size = 0;

// 指向链表头结点
transient Node<E> first;

// 指向链表尾结点
transient Node<E> last;

构造函数

1
2
3
// 构造函数为空
public LinkedList() {
}

获取索引对应的结点

用链表实现的List不同于数组，查找对应索引的结点不支持随机访问，只能遍历链表找到对应位置的结点。
因为持有头尾结点的引用所以可以根据索引位于List中的位置而搜索对应的部分进一步提高搜索效率。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Node<E> node(int index) {
    // assert isElementIndex(index);
    // 如果索引位于List的前半部分则从头结点开始搜索
    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
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
// 将新结点插入到List后面
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++;
}

// 调用linkLast方法将元素e作为新结点插入List后面
public boolean add(E e) {
    linkLast(e);
    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;
}

// 遍历链表把每一个结点的属性都设置为null
public void clear() {
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

// 获取指定位置上的值
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 找到其对应结点修改其值并返回旧值
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

// 将元素作为新结点插入到指定位置
public void add(int index, E element) {
    // 判断插入位置是否在有效范围
    checkPositionIndex(index);
    // 如果插入位置在尾部则调用linkLast方法插入
    if (index == size)
        linkLast(element);
    else // 找到对应位置上的结点插入其前面
        linkBefore(element, node(index));
}

public E remove(int index) {
    // 判断索引位置是否合法
    checkElementIndex(index);
    // 找到指定位置对应的结点将其释放其链接
    return unlink(node(index));
}

toArray方法

创建一个数组，将链表所有结点的值都一一赋值到该数组上

1
2
3
4
5
6
7
public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}