链表

发表于 | 分类于 ， | | 本文总阅读数 次
| 字数统计: 3.8k | 阅读时长 ≈ 15
链表

链表

链表介绍

  链表(Linked List):链表是一种非常基础的数据结构，链表的实现和数组不同，链表中的元素是一个个的节点，不是存放在连续的地址空间中的，当需要添加元素时，在最后一个节点的尾部添加一个节点即可。C++中的list、以及Java中的LinkedList，都是链表，当时只是讲解了链表的使用，并没有讲解实现和源码。我们今天从增、删、改、查入手，详细讲解一下链表的源码。

构造器

我们直接看源码吧，看一下Java 11中的LinkedList是如何构造的。

和ArrayList不同的是，LinkedList有两个构造方法，因为不像ArrayList元素是存放在数组中的，可以指定数组的长度，链表是动态增删节点的，因此不存在初始化大小的说法。

1

我们关注一下常用的无参构造函数，有一个Collection参数的构造方法，其实就是将Collection类型的元素逐个添加到链表中，不是很常用，这里不过多赘述。

无参构造器

先看下我们最常用的无参构造，就一行代码

this.size = 0;

就是初始化链表的长度为0。

增加元素

我们下面将介绍链表最最重要的一个操作，增加元素，看一下链表是如何增加节点的。

一个泛型参数的add方法

1
1
1

会直接调用linkLast方法，顾名思义，就是在链表的最后增加元素。我们常把链表的开始称为头节点(HEAD)，链表的最后称为尾节点(TAIL)。linkLast就是在尾节点后增加新的节点，并将尾节点指向新增加的节点。

我们看一下linkLast方法是如何实现的。

先获取l = this.last，表示当前的尾节点，并创建一个新的节点称为newNode，可以看到Node的三参构造，分别是prev、item、next，也很好理解，就是节点的前一个节点(直接前驱)、当前节点值、下一个节点(直接后继)。

既然是尾插，所以新的节点是真正的尾节点，newNode的prev应该指向当前的尾节点，新节点的值就是传入的参数，新节点的next一定是null，因为它就是尾节点，无下一个节点。

并且让this.last = newNode，从这里也可以看出，last就是指代链表的尾部节点。

下面是一个if语句，如果l == null，表示当前链表没有尾部，说明一个元素都没有，那么新加入的节点也是头节点，所以first也应该指向新插入的节点。此时头部等于尾部，都等于链表的唯一一个节点。否则头节点不变化，让原来的尾节点的next等于最新的尾节点。

在链表中，初学者容易犯两点错误

  1. 我们一定要理清楚链表的时序关系，不管三七二十一，背答案，可能顺序写错，就会导致链表结构错误。
  2. 一定要做好链表的善后工作，比如一些同学可能会写newNode.prev = l，然后忘记写l.next = newNode。

一个int参数和一个泛型参数的add方法

1
1
1
1
1

和ArrayList一样，第一个参数表示插入的位置，第二个参数表示插入的元素。先检查插入的位置是否合法。

1
index >= 0 && index <= this.size

表示插入元素是合法的，如果不合法会抛出异常IndexOutOfBoundsException。

合法后，我们判断插入的位置是否等于链表的长度，如果等于，那就相当于尾插法，直接调用linkLast即可。否则是在前面插入元素。

在前面插入元素会调用linkBefore方法，我们看一下是如何操作的。传入的两个参数是插入的元素和一个节点。

我们先看一下节点是什么？是插入元素的上一个节点还是下一个节点？追踪node方法，可以看出LinkList对插入元素进行了优化

1
index < this.size >> 1;

这句代码很精髓，size >> 1等价于size / 2，就是看一下这个索引是在链表的前半部分还是后半部分。如果是前半部分，则从head开始向后查找，向后移动index个节点。如果index是0，就是head节点，index是1，就是head.next节点。

如果是后半部分，我们就从tail向前查找，向前移动size - index - 1个节点，如果index = size - 1，那么就是tail节点。

将index索引所在的节点succ找到后，插入元素是插入到该元素前面，前一个节点，记为pred。创建一个新的节点newNode，让其直接前驱指向pred，直接后继指向succ。如果直接前驱为null，表示插入的位置是HEAD，则让新的HEAD指向newNode，否则让直接前驱pred的next指向newNode，要记得也要让直接后继succ的prev指向newNode。

一个泛型参数的addFirst方法

1
1

addFirst会调用linkFirst方法，故名思意和linkLast相反，在头部添加元素，首先获取当前链表的头部f，然后创建新的节点，让其直接前驱为null，让其直接后继为f，表示新的头节点的下一个节点是以前的头节点。并且更新链表的头节点，指向刚刚插入的元素。如果以前的头节点为null，表示新节点是链表中唯一的节点，让尾节点也指向新的节点，否则让原来头节点的直接前驱为新创建的头节点。

一个泛型参数的addLast方法

1

addLast方法直接调用linkLast方法，小伙伴可以直接参考add方法即可。我们也可以看出add方法就等价于addLast在链表尾部插入元素。

删除元素

无参remove方法

1
1
1

无参remove方法会调用removeFirst方法，在removeFirst方法中，会先判断first是否为null，如果first为null，表示链表为空，抛出异常。否则会调用unlinkFirst方法。

在该方法中，先获取头节点f的下一个节点next，作为真正的头节点，并将原始头节点f的元素取出来，用于返回值，将f的next指向null。

如果next为null，表示原始链表就一个节点，删掉头节点后，链表为null，尾节点last也指向null，否则next的直接前驱为null，表示next是新的头节点。

一个int参数的remove方法

1
1
1
1

一个int参数，表示要删除的节点索引，首先会检查索引是否符合条件，不符合条件会抛出异常。

1
index >= 0 && index < this.size

这里插入的时候索引是要小于等于size，因为等于size - 1表示在尾部前面插入，等于size表示在尾部后面插入。但是删除的时候，索引必须小于size。这是插入和删除的差异。如果不合法会抛出异常IndexOutOfBoundsException。

调用node方法，获取要删除节点的下一个节点。node方法可以参考一个int参数和一个泛型参数的add方法。

找到node后，就需要调用unlink方法删除这个节点，此时需要找到该节点的直接前驱prev和直接后继next。如果直接前驱是null，此时删除的元素就是头节点，因此需要将头节点指向next。否则让直接前驱的下一个节点直接指向next，并且将node的prev指向null，表示它的直接前驱已经无法get到。

如果直接后继是null，此时删除的元素就说尾节点，此时需要将尾节点指向prev。否则让直接后继的前一个节点直接指向prev，并且将node的next指向null，表示它的直接后继已经无法get到。最后将node的值设为null，size–即可。

一个泛型参数的remove方法

1

这个和ArrayList的实现基本一样，就是从head开始向后遍历，如果两个节点相等，则会调用unlink方法删除该节点。

无参的removeFirst方法

1

我们在介绍无参remove方法时，介绍了removeFirst方法，它们是等价的，因此LinkedList默认是尾插头删，小伙伴们如果忘记是从哪边删除或者从哪边插入，可以类比队列，只能从队头出栈、队尾入栈，或者就调用addFirst、addLast、removeFirst、removeLast，总不会出问题。

无参的removeLast方法

1
1

removeLast就是从尾部删除一个元素，如果尾部为null，表示链表为空，抛出异常。

记尾部节点为l，前一个节点为prev，让尾部节点的直接前驱为null，尾部节点对应的值为null。如果直接前驱是null，说明原链表只有一个节点，因此删掉后要让head也指向null，否则prev是新的尾节点，让其next指向null，size–

修改元素

一个int和一个泛型参数的set方法

1

set方法没啥好说的，就是把对应索引上面的值修改。

首先检查索引是否满足条件，然后调用node方法，找到index对应的节点。最后将节点的item修改即可。

查找元素

一个int参数的get方法

1

get方法传入的参数表示节点的索引，先调用node方法，找到该节点，然后返回item即可。

无参的getFirst方法

1

getFirst其实就是返回头节点的item

无参的getLast方法

1

getLast其实就是返回尾节点的item

一个参数的indexOf方法

1

和ArrayList的indexOf非常接近，但是LinkedList是链表实现，需要从头节点一次向后遍历，如果两者相等，则返回对应的索引，如果到最后也没有找到，则返回-1。

一个参数的lastIndexOf方法

1

顾名思义，这个方法是从后向前查找元素对应的索引，找到相等时返回，如果遍历结束都没找到则返回-1。

注意：这里的相等判断的是equal方法，而不是==。
对于非基本类型来说，==是判断两个对象的地址是否相同，equal是可以被重写的，如果不重写和==一样，如果重写可以用来比较两个对象的值是否相等。

代码实现

讲解完毕后，要求不看源码，实现简单的Integer类型的增删改查数据结构，这里不涉及到扩容，因此代码也比较简单，就是要考虑指针的指向。

这一步是非常重要的，如果只是学习并不练习，会很快被遗忘，小伙伴们一定要注意，计算机不是理科而是工科，一定要亲手敲出来，才是真正的学会了。

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
class IntegerLinkedList {
    class Node {
        private int value;

        private Node prev;

        private Node next;

        Node (int value, Node prev, Node next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }
    }

    private Node head;

    private Node tail;

    private int size;

    IntegerLinkedList() {
        head = null;
        tail = null;
        size = 0;
    }

    public boolean add(int value) {
        addLast(value);
        return true;
    }

    public void add(int index, int value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + " Out Of Bounds [0, " + size + "]");
        }
        if (index == size) {
            addLast(value);
        } else {
            Node node = getIndexNode(index);
            addBefore(node, value);
        }
    }

    public void addFirst(int value) {
        if (size == 0) {
            Node newNode = new Node(value, null, null);
            head = newNode;
            tail = newNode;
            size++;
        } else {
            addBefore(head, value);
        }
    }

    public void addLast(int value) {
        Node newNode;
        if (size == 0) {
            newNode = new Node(value, null, null);
            head = newNode;
        } else {
            newNode = new Node(value, tail, null);
            tail.next = newNode;
        }
        tail = newNode;
        size++;
    }

    public int remove() {
        return removeFirst();
    }

    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + " Out Of Bounds [0, " + (size - 1) + "]");
        }
        Node node = getIndexNode(index);
        return removeNode(node);
    }

    public boolean remove(Integer value) {
        Node node = head;
        while (node != null) {
            if (node.value == value) {
                removeNode(node);
                return true;
            }
            node = node.next;
        }
        return false;
    }

    public int removeFirst() {
        return removeNode(head);
    }

    public int removeLast() {
        return removeNode(tail);
    }

    public int set(int index, int value) {
        if (index < 0 || index >= size) {
            throw new NoSuchElementException();
        }
        Node node = getIndexNode(index);
        int oldValue = node.value;
        node.value = value;
        return oldValue;
    }

    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new NoSuchElementException();
        }
        Node node = getIndexNode(index);
        return node.value;
    }

    public int getFirst() {
        if (size == 0) {
            throw new NoSuchElementException();
        } else {
            return head.value;
        }
    }

    public int getLast() {
        if (size == 0) {
            throw new NoSuchElementException();
        } else {
            return tail.value;
        }
    }

    public int indexOf(int value) {
        Node node = head;
        int index = 0;
        while (node != null) {
            if (node.value == value) {
                return index;
            }
            index++;
            node = node.next;
        }
        return -1;
    }

    public int lastIndexOf(int value) {
        Node node = tail;
        int index = size - 1;
        while (node != null) {
            if (node.value == value) {
                return index;
            }
            index--;
            node = node.prev;
        }
        return -1;
    }

    private Node getIndexNode(int index) {
        int midIndex = size >> 1;
        Node node;
        if (index < midIndex) {
            node = head;
            while (index-- > 0) {
                node = node.next;
            }
        } else {
            node = tail;
            while (size - index++ - 1 > 0) {
                node = node.prev;
            }
        }
        return node;
    }

    private void addBefore(Node node, int value) {
        Node prev = node.prev;
        Node newNode = new Node(value, prev, node);
        if (prev == null) {
            head = newNode;
        } else {
            prev.next = newNode;
        }
        node.prev = newNode;
        size++;
    }

    private int removeNode(Node node) {
        Node prev = node.prev;
        Node next = node.next;
        int value = node.value;
        if (prev == null) {
            head = next;
        } else {
            prev.next = next;
            node.prev = null;
            node.value = 0;
        }
        if (next == null) {
            tail = prev;
        } else {
            next.prev = prev;
            node.next = null;
            node.value = 0;
        }
        size--;
        return value;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("list = [");
        Node node = head;
        for (int i = 0; i < size - 1; i++) {
            builder.append(node.value).append(", ");
            node = node.next;
        }
        if (size >= 1) {
            builder.append(node.value);
        }
        return builder.append("], size = ").append(size).toString();
    }
}

下面写一下测试代码

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
class Solution {
    public static void main(String[] args) {
        IntegerLinkedList linkedList = new IntegerLinkedList();
        System.out.println(linkedList);
        linkedList.add(50);
        System.out.println(linkedList);
        linkedList.addFirst(20);
        System.out.println(linkedList);
        linkedList.addLast(60);
        System.out.println(linkedList);
        linkedList.add(1, 30);
        System.out.println(linkedList);
        linkedList.addFirst(10);
        System.out.println(linkedList);
        linkedList.add(3, 40);
        System.out.println(linkedList);
        linkedList.add(70);
        System.out.println(linkedList);
        linkedList.add(80);
        System.out.println(linkedList);
        System.out.println(linkedList.remove());
        System.out.println(linkedList);
        System.out.println(linkedList.remove(2));
        System.out.println(linkedList);
        System.out.println(linkedList.remove(Integer.valueOf(50)));
        System.out.println(linkedList);
        System.out.println(linkedList.removeFirst());
        System.out.println(linkedList);
        System.out.println(linkedList.removeLast());
        System.out.println(linkedList);
        System.out.println(linkedList.set(1, 80));
        System.out.println(linkedList);
        System.out.println(linkedList.get(1));
        System.out.println(linkedList.getFirst());
        System.out.println(linkedList.getLast());
        System.out.println(linkedList.indexOf(30));
        System.out.println(linkedList.lastIndexOf(80));
    }
}

输出结果为

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
list = [], size = 0
list = [50], size = 1
list = [20, 50], size = 2
list = [20, 50, 60], size = 3
list = [20, 30, 50, 60], size = 4
list = [10, 20, 30, 50, 60], size = 5
list = [10, 20, 30, 40, 50, 60], size = 6
list = [10, 20, 30, 40, 50, 60, 70], size = 7
list = [10, 20, 30, 40, 50, 60, 70, 80], size = 8
10
list = [20, 30, 40, 50, 60, 70, 80], size = 7
40
list = [20, 30, 50, 60, 70, 80], size = 6
true
list = [20, 30, 60, 70, 80], size = 5
20
list = [30, 60, 70, 80], size = 4
80
list = [30, 60, 70], size = 3
60
list = [30, 80, 70], size = 3
80
30
70
0
1

小结

  到目前为止，链表已经讲解完毕，小伙伴们有没有手写出来链表呢？在写代码时，我们只需要了解源码的逻辑，并不是要模仿照抄源码的实现。Java源码中的LinkedList类还有许多有趣的实现，这里不做过多赘述，只讲解最重要的增删改查，感兴趣的小伙伴们可以作为扩展阅读去探寻源码。

-------------本文结束感谢您的阅读-------------
0%