什么是链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（元素）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
牺牲随机访问，换取快速插入和删除。
单向链表
单向链表又称单链表，是链表的一种，链表的链接方向是单向的，对单链表的访问要通过顺序读取从头部开始。
一个完整的单向链表包含一个head头节点，和一个tail尾节点，而尾节点的next指针域指向一个null空对象。好了，了解了一个单向链表的内部结构后，下面我门来创建一个我们自己的单链表。
首先，创建一个内部类，实例代表一个链表结点。
1
2
3
4
5
6
7
8
9
10
| public final class Node {
private T data;
private Node next;
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
|
定义三个成员变量header、tail和size，分别用于保存头节点、尾节点和链表的节点数
1
2
3
| private Node header = null;
private Node tail = null;
private int size = 0;
|
添加
简单构建一个添加的方法，添加前我门首先要判断其是否是一个空的链表，如果header == null即为一个空链表，创建一个结点作为header头节点，让tail尾节点指向新建结点的引用，注意这里的指向是指tail尾节点指向而不是tail尾节点的next指针域指向
如果header != null，创建一个新结点，尾节点next指针指向新节点的引用，让新节点作为尾节点使用。
在尾部添加元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
* 添加一条数据，默认在尾部插入
*
* @param element
*/
public void add(T element) {
if (header == null) {
header = new Node(element, tail);
tail = header;
} else {
Node node = new Node(element, null);
tail.next = node;
tail = node;
}
size++;
}
|
删除
由于其链式的数据结构，删除时我们只需要改变要删除结点前置结点next指针指向的引用即可，然后置空要删除结点next的指针域。这就是为什么相对于其他线性表插入和删除较快的原因，插入和删除时我们不需要重新移位其他数据。
具体代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
* 根据索引删除节点
*
* @param index
* @return
*/
public T delete(int index) {
checkElementIndex(index);
Node delNode = null;
if (index == 0) {
delNode = header;
header = header.next;
} else {
Node prevNode = getNodeByIndex(index - 1);
delNode = prevNode.next;
prevNode.next = delNode.next;
delNode.next = null;
}
size--;
return delNode.data;
}
|
查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
* 获取索引处的数据
*
* @param index
* @return
*/
public T get(int index) {
checkElementIndex(index);
return getNodeByIndex(index).data;
}
private Node getNodeByIndex(int index) {
Node x = header;
for (int i = 0; i < index; i++)
x = x.next;
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
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
|
* Created by okycode
* <p>
* Description
*/
public class SimpleLinkedList<T> {
private Node header = null;
private Node tail = null;
private int size = 0;
* 定义一个链表结点内部类
*/
public final class Node {
private T data;
private Node next;
public Node(T data, Node next) {
this.data = data;
this.next = next;
}
}
* 返回链表长度
*
* @return
*/
public int size() {
return size;
}
* 获取索引处的数据
*
* @param index
* @return
*/
public T get(int index) {
checkElementIndex(index);
return getNodeByIndex(index).data;
}
* 添加一条数据，默认在尾部插入
*
* @param element
*/
public void add(T element) {
if (header == null) {
header = new Node(element, tail);
tail = header;
} else {
Node node = new Node(element, null);
tail.next = node;
tail = node;
}
size++;
}
* 在任意位置插入一条数据
*
* @param index
* @param element
*/
public void add(T element, int index) {
checkElementIndex(index);
if (header == null) {
add(element);
} else {
if (index == 0) {
addFirst(element);
} else {
Node prevNode = getNodeByIndex(index - 1);
prevNode.next = new Node(element, prevNode.next);
}
}
size++;
}
* 根据索引删除节点
*
* @param index
* @return
*/
public T delete(int index) {
checkElementIndex(index);
Node delNode = null;
if (index == 0) {
delNode = header;
header = header.next;
} else {
Node prevNode = getNodeByIndex(index - 1);
delNode = prevNode.next;
prevNode.next = delNode.next;
delNode.next = null;
}
size--;
return delNode.data;
}
* 清除链表
*/
public void clear() {
header = null;
tail = null;
size = 0;
}
* 在头部添加一条数据，效率高相比于尾插
*
* @param element
*/
public void addFirst(T element) {
Node node = new Node(element, header);
header = node;
if (tail == null) {
tail = header;
}
size++;
}
private Node getNodeByIndex(int index) {
Node x = header;
for (int i = 0; i < index; i++)
x = x.next;
return x;
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: " + index + ", Size: " + size;
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for (Node current = header; current != null; current = current.next) {
sb.append(current.data.toString() + ",");
}
int len = sb.length();
return sb.delete(len - 2, len).append("]").toString();
}
}
|
如何反转一个单链表
详细见代码注解，这里值得注意的是，我门在反转结点指针时要临时纪录结点后继结点防止断链。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public static void reverse(SimpleLinkedList sll) {
if (sll == null) return;
Node pre = sll.header;
Node cur = sll.header.next;
Node tmp;
while (cur != null) {
tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
sll.header.next = null;
|
