数组的砖块整齐排列，逐个紧贴。链表的砖块分散各处，连接的藤蔓自由地穿梭于砖缝之间。
刷过力扣的读者肯定对单链表非常熟悉，力扣上的单链表节点定义如下：
1
2
3
4
5
|
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
|
这仅仅是一个最简单的单链表节点，方便力扣出算法题来考你。在实际的编程语言中，我们使用的链表节点会稍微复杂一点，类似这样：
1
2
3
4
5
6
7
8
9
10
11
|
class Node<E> {
E val;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.val = element;
this.next = next;
this.prev = prev;
}
}
|
主要区别有两个：
1、编程语言标准库一般都会提供泛型，即你可以指定 val 字段为任意类型，而力扣的单链表节点的 val 字段只有 int 类型。
2、编程语言标准库一般使用的都是双链表而非单链表。单链表节点只有一个 next 指针，指向下一个节点；而双链表节点有两个指针，prev 指向前一个节点，next 指向下一个节点。
有了 prev 前驱指针，链表支持双向遍历，但由于要多维护一个指针，增删查改时会稍微复杂一些，后面带大家实现双链表时会具体介绍。
为什么需要链表
前面介绍了 数组（顺序存储）的底层原理，说白了就是一块连续的内存空间，有了这块内存空间的首地址，就能直接通过索引计算出任意位置的元素地址。
链表不一样，一条链表并不需要一整块连续的内存空间存储元素。链表的元素可以分散在内存空间的天涯海角，通过每个节点上的 next, prev 指针，将零散的内存块串联起来形成一个链式结构。
这样做的好处很明显，首先就是可以提高内存的利用效率，链表的节点不需要挨在一起，给点内存 new 出来一个节点就能用，操作系统会觉得这娃好养活。
另外一个好处，它的节点要用的时候就能接上，不用的时候拆掉就行了，从来不需要考虑扩缩容和数据搬移的问题，理论上讲，链表是没有容量限制的（除非把所有内存都占满，这不太可能）。
当然，不可能只有好处没有局限性。数组最大的优势是支持通过索引快速访问元素，而链表就不支持。
这个不难理解吧，因为元素并不是紧挨着的，所以如果你想要访问第 3 个链表元素，你就只能从头结点开始往顺着 next 指针往后找，直到找到第 3 个节点才行。
上面是对链表这种数据结构的基本介绍，接下来我们就结合代码实现单/双链表的几个基本操作。
几个关键点
下面我会分别用双链表和单链给出一个简单的 MyLinkedList 代码实现，包含了基本的增删查改功能。这里给出几个关键点，等会你看代码的时候可以着重注意一下。
关键点一、同时持有头尾节点的引用
在力扣做题时，一般题目给我们传入的就是单链表的头指针。但是在实际开发中，用的都是双链表，而双链表一般会同时持有头尾节点的引用。
因为在软件开发中，在容器尾部添加元素是个非常高频的操作，双链表持有尾部节点的引用，就可以在 O(1)O(1) 的时间复杂度内完成尾部添加元素的操作。
对于单链表来说，持有尾部节点的引用也有优化效果。比如你要在单链表尾部添加元素，如果没有尾部节点的引用，你就需要遍历整个链表找到尾部节点，时间复杂度是 O(n)O(n)；如果有尾部节点的引用，就可以在 O(1)O(1) 的时间复杂度内完成尾部添加元素的操作。
细心的读者可能会说，即便如此，如果删除一次单链表的尾结点，那么之前尾结点的引用就失效了，还是需要遍历一遍链表找到尾结点。
是的，但你再仔细想想，删除单链表尾结点的时候，是不是也得遍历到倒数第二个节点（尾结点的前驱），才能通过指针操作把尾结点删掉？那么这个时候，你不就可以顺便把尾结点的引用给更新了吗？
关键点二、虚拟头尾节点
在上一篇文章 链表基础 中我提到过「虚拟头尾节点」技巧，它的原理很简单，就是在创建双链表时就创建一个虚拟头节点和一个虚拟尾节点，无论双链表是否为空，这两个节点都存在。这样就不会出现空指针的问题，可以避免很多边界情况的处理。
举例来说，假设虚拟头尾节点分别是 dummyHead 和 dummyTail，那么一条空的双链表长这样：
1
|
dummyHead <-> dummyTail
|
如果你添加 1,2,3 几个元素，那么链表长这样：
1
|
dummyHead <-> 1 <-> 2 <-> 3 <-> dummyTail
|
你以前要把在头部插入元素、在尾部插入元素和在中间插入元素几种情况分开讨论，现在有了头尾虚拟节点，无论链表是否为空，都只需要考虑在中间插入元素的情况就可以了，这样代码会简洁很多。
当然，虚拟头结点会多占用一点内存空间，但是比起给你解决的麻烦，这点空间消耗是划算的。
对于单链表，虚拟头结点有一定的简化作用，但虚拟尾节点没有太大作用。
虚拟节点是内部实现，对外不可见
虚拟节点是你内部实现数据结构的技巧，对外是不可见的。比如按照索引获取元素的 get(index) 方法，都是从真实节点开始计算索引，而不是从虚拟节点开始计算。
关键点三、内存泄露？
在前文 动态数组实现 中，我提到了删除元素时，要注意内存泄露的问题。那么在链表中，删除元素会不会也有内存泄露的问题呢？
尤其是这样的写法，你觉得有没有问题：
1
2
3
4
5
6
|
// 假设单链表头结点 head = 1 -> 2 -> 3 -> 4 -> 5
// 删除单链表头结点
head = head.next;
// 此时 head = 2 -> 3 -> 4 -> 5
|
细心的读者可能认为这样写会有内存泄露的问题，因为原来的那个头结点 1 的 next 指针没有断开，依然指向着节点 2。
但实际上这样写是 OK 的，因为 Java 的垃圾回收的判断机制是看这个对象是否被别人引用，而并不会 care 这个对象是否还引用着别人。
那个节点 1 的 next 指针确实还指向着节点 2，但是并没有别的指针引用节点 1 了，所以节点 1 最终会被垃圾回收器回收释放。所以说这个场景和数组中删除元素的场景是不一样的，你可以再仔细思考一下。
不过呢，删除节点时，最好还是把被删除节点的指针都置为 null，这是个好习惯，不会有什么代价，还可能避免一些潜在的问题。所以在下面的实现中，无论是否有必要，我都会把被删除节点上的指针置为 null。
双链表代码实现
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
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
|
import java.util.NoSuchElementException;
public class MyLinkedList<E> {
// 虚拟头尾节点
final private Node<E> head, tail;
private int size;
// 双链表节点
private static class Node<E> {
E val;
Node<E> next;
Node<E> prev;
Node(E val) {
this.val = val;
}
}
// 构造函数初始化虚拟头尾节点
public MyLinkedList() {
this.head = new Node<>(null);
this.tail = new Node<>(null);
head.next = tail;
tail.prev = head;
this.size = 0;
}
// ***** 增 *****
public void addLast(E e) {
Node<E> x = new Node<>(e);
Node<E> temp = tail.prev;
// temp <-> x
temp.next = x;
x.prev = temp;
x.next = tail;
tail.prev = x;
// temp <-> x <-> tail
size++;
}
public void addFirst(E e) {
Node<E> x = new Node<>(e);
Node<E> temp = head.next;
// head <-> temp
temp.prev = x;
x.next = temp;
head.next = x;
x.prev = head;
// head <-> x <-> temp
size++;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) {
addLast(element);
return;
}
// 找到 index 对应的 Node
Node<E> p = getNode(index);
Node<E> temp = p.prev;
// temp <-> p
// 新要插入的 Node
Node<E> x = new Node<>(element);
p.prev = x;
temp.next = x;
x.prev = temp;
x.next = p;
// temp <-> x <-> p
size++;
}
// ***** 删 *****
public E removeFirst() {
if (size < 1) {
throw new NoSuchElementException();
}
// 虚拟节点的存在是我们不用考虑空指针的问题
Node<E> x = head.next;
Node<E> temp = x.next;
// head <-> x <-> temp
head.next = temp;
temp.prev = head;
x.prev = null;
x.next = null;
// head <-> temp
size--;
return x.val;
}
public E removeLast() {
if (size < 1) {
throw new NoSuchElementException();
}
Node<E> x = tail.prev;
Node<E> temp = tail.prev.prev;
// temp <-> x <-> tail
tail.prev = temp;
temp.next = tail;
x.prev = null;
x.next = null;
// temp <-> tail
size--;
return x.val;
}
public E remove(int index) {
checkElementIndex(index);
// 找到 index 对应的 Node
Node<E> x = getNode(index);
Node<E> prev = x.prev;
Node<E> next = x.next;
// prev <-> x <-> next
prev.next = next;
next.prev = prev;
x.prev = x.next = null;
// prev <-> next
size--;
return x.val;
}
// ***** 查 *****
public E get(int index) {
checkElementIndex(index);
// 找到 index 对应的 Node
Node<E> p = getNode(index);
return p.val;
}
public E getFirst() {
if (size < 1) {
throw new NoSuchElementException();
}
return head.next.val;
}
public E getLast() {
if (size < 1) {
throw new NoSuchElementException();
}
return tail.prev.val;
}
// ***** 改 *****
public E set(int index, E val) {
checkElementIndex(index);
// 找到 index 对应的 Node
Node<E> p = getNode(index);
E oldVal = p.val;
p.val = val;
return oldVal;
}
// ***** 其他工具函数 *****
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private Node<E> getNode(int index) {
checkElementIndex(index);
Node<E> p = head.next;
// TODO: 可以优化，通过 index 判断从 head 还是 tail 开始遍历
for (int i = 0; i < index; i++) {
p = p.next;
}
return p;
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
// 检查 index 索引位置是否可以存在元素
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// 检查 index 索引位置是否可以添加元素
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
private void display() {
System.out.println("size = " + size);
for (Node<E> p = head.next; p != tail; p = p.next) {
System.out.print(p.val + " <-> ");
}
System.out.println("null");
System.out.println();
}
public static void main(String[] args) {
MyLinkedList<Integer> list = new MyLinkedList<>();
list.addLast(1);
list.addLast(2);
list.addLast(3);
list.addFirst(0);
list.add(2, 100);
list.display();
// size = 5
// 0 <-> 1 <-> 100 <-> 2 -> 3 -> null
}
}
|
单链表代码实现
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
|
import java.util.NoSuchElementException;
public class MyLinkedList2<E> {
private static class Node<E> {
E val;
Node<E> next;
Node(E val) {
this.val = val;
this.next = null;
}
}
private Node<E> head;
// 实际的尾部节点引用
private Node<E> tail;
private int size;
public MyLinkedList2() {
this.head = new Node<>(null);
this.tail = head;
this.size = 0;
}
public void addFirst(E e) {
Node<E> newNode = new Node<>(e);
newNode.next = head.next;
head.next = newNode;
if (size == 0) {
tail = newNode;
}
size++;
}
public void addLast(E e) {
Node<E> newNode = new Node<>(e);
tail.next = newNode;
tail = newNode;
size++;
}
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size) {
addLast(element);
return;
}
Node<E> prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node<E> newNode = new Node<>(element);
newNode.next = prev.next;
prev.next = newNode;
size++;
}
public E removeFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
Node<E> first = head.next;
head.next = first.next;
if (size == 1) {
tail = head;
}
size--;
return first.val;
}
public E removeLast() {
if (isEmpty()) {
throw new NoSuchElementException();
}
Node<E> prev = head;
while (prev.next != tail) {
prev = prev.next;
}
E val = tail.val;
prev.next = null;
tail = prev;
size--;
return val;
}
public E remove(int index) {
checkElementIndex(index);
Node<E> prev = head;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node<E> nodeToRemove = prev.next;
prev.next = nodeToRemove.next;
// 删除的是最后一个元素
if (index == size - 1) {
tail = prev;
}
size--;
return nodeToRemove.val;
}
// ***** 查 *****
public E getFirst() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return head.next.val;
}
public E getLast() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return getNode(size - 1).val;
}
public E get(int index) {
checkElementIndex(index);
Node<E> p = getNode(index);
return p.val;
}
// ***** 改 *****
public E set(int index, E element) {
checkElementIndex(index);
Node<E> p = getNode(index);
E oldVal = p.val;
p.val = element;
return oldVal;
}
// ***** 其他工具函数 *****
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
// 检查 index 索引位置是否可以存在元素
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// 检查 index 索引位置是否可以添加元素
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
}
// 返回 index 对应的 Node
// 注意：请保证传入的 index 是合法的
private Node<E> getNode(int index) {
Node<E> p = head.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p;
}
public static void main(String[] args) {
MyLinkedList2<Integer> list = new MyLinkedList2<>();
list.addFirst(1);
list.addFirst(2);
list.addLast(3);
list.addLast(4);
list.add(2, 5);
System.out.println(list.removeFirst()); // 2
System.out.println(list.removeLast()); // 4
System.out.println(list.remove(1)); // 5
System.out.println(list.getFirst()); // 1
System.out.println(list.getLast()); // 3
System.out.println(list.get(1)); // 3
}
}
|
