数据结构系列之链表的数据结构

数据结构系列之链表的数据结构

在上一章的学习中，我们知道了数组的基本概念和相关特性，接着本博客继续学习数据结构中一个比较常用的数据结构，链表。ps：本博客基于java中的数据结构。

1、什么是链表？

链表是由一系列节点组成的很常见的数据结构，每一个节点都包含一个值和指向下一个节点的指针。“头”节点指向序列的第一个节点，序列的最后一个节点指向NULL（对于单链表）。链表也是线性的顺序存储数据，不过在内存地址上是不连续的。

画图表示单链表：

2、链表和数组的对比

在上一章节，学习了数组，所以这一章和数组做对比：

• 数组在内存地址是连续的，与数组不同，链接的节点（链接）不需要连续出现在内存中
• 链表的大小不需要提前声明，只有内存允许就可以
• 链表是动态的，所以新增移除节点都是控制指针就可以，所以链表的新增移除操作都是比较快的，这个和数组相反
• 数组是通过下标指针就可以直接访问节点数据，而链表需要全局遍历，所以数组的访问速度是比较快，链接相反
• 链表的数据结构需要更多的内存，因为链表不止要保存数据，还要保存下一个节点的指针

3、链表的类型分类

数据结构中支持如下几种类型的链表：

• 单链表：在单链表中，节点的遍历只能往前遍历，指针从Head节点开始
• 双向链表：双向链表的遍历导航可以和单链表一样往前遍历，也可以后腿，往后遍历
• 循环链表：循环链表是一种特别的链表，其最后一个节点的next指针指向第一个节点，也即第一个节点的previous节点为最后一个节点

4、单链表的简介

由图看出链表的特性：

• 1、 Head节点指向第1个节点
• 2、 最后一个节点指针指向null
• 3、 每一个节点都存储数据和指向下一个节点的指针

5、双向链表简介

画图表示双向链表：

由图可以归纳双向链表的特性：

• 1、Head节点指向链表的第一个节点
• 2、每一个节点都有一个存储数据的节点，和指向下一个节点的next指针、指向上一个节点的prev指针
• 3、第一个节点的prev指针指向null
• 4、最好一个节点的next指针指向null

6、循环单向链表

画图表示循环单向链表：

由图归纳循环单向链表的特性：

• 1、 Head节点指向第1个节点
• 2、Tail (Last) 指针指向列表的最后一个节点。
• 3、每个节点都有存储数据的区域和一个指向下一个节点的指针
• 4、最后一个节点的next指针指向第一个节点

7、链表的基本操作

本章节以最简单的单链表，介绍链表的基本操作，开发语言基于Java

需要构建一个链表的节点模型，单链表只需要保存数据，加上一个next指针就行：

 private static class Node<T> { public T data; public Node next; Node(T data) { this.data = data; next = null; }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
 

• 新增节点
  这种情况，直接将新增节点附加到链表的后面，这里分情况：
  • 1、如果是empty的链表，直接将新节点作为head节点
  • 2、其它节点，直接附加到链表最后面既可

 /**
 * 链表新增节点，直接附加到链表最后面
 * @Date 2021/08/04 13:54
 * @Param [list, data]
 * @return void
 */
public static <T> void add(MySinglyLinkedList<T> list , T data) { Node<T> newNode = new Node<T>(data); // 单链表是empty的，将新增的节点直接作为head节点 if (list.head == null) { list.head = newNode; } else { // 其它情况直接在链表后面附加上新节点 Node<T> currentNode = list.head; while (currentNode.next != null) { currentNode = currentNode.next; } // 将新增的节点作为最后一个节点 currentNode.next = newNode; }
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
 

如上的方法，都是固定在链表最后面加上的，然后可以实现在指定节点后面加上节点，这里分三步进行：

• 1、创建新的节点，赋值数据
• 2、将新节点的指针指向前驱节点原来的next节点
• 3、将前驱节点的指针指向新建的节点

/**
 * 在指定前驱节点后面附加新节点 <br>
 * @Date 2021/08/04 14:26
 * @Param prevNode 前驱节点
 * @Param data 新增节点数据
 * @return void
 */
public static <T> void addAfter(Node<T> prevNode , T data) { if (prevNode == null) { System.out.println("前驱节点不能为null"); } // 原本链表0->2，创建新节点1 Node<T> newNode = new Node<T>(data); // 将新节点的指针指向前驱节点原本的next节点 1->2 newNode.next = prevNode.next; // 将前驱节点的next指针指向新节点 0->1 prevNode.next = newNode;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

• 移除节点
  移除节点，可以在指定位置移除节点，这里可以分为几种情况：
  • 1、移除第一个节点。
  • 2、移除任何中间元素。
  • 3、移除最后一个元素。

/**
 * 指定下标移除链表节点 <br>
 * @Date 2021/08/04 14:34
 * @Param [list, pos]
 * @return void
 */
public static <T> void removeAtPosition(MySinglyLinkedList<T> list , int pos) { // 当前节点 Node<T> currentNode = list.head; // 记录前一个节点 Node<T> prevNode = null; // 下标计数器 int counter = 0; if (currentNode != null) { // 移除第一个节点 if (pos == 0) { // 指针移动，节点往后移，再将下一个节点置为head节点 list.head = currentNode.next; } else { while (currentNode!= null) { // 找到移除节点要节点位置 if (counter == pos) { prevNode.next = currentNode.next; break; } else { // 记录前驱节点 prevNode = currentNode; // 往后遍历 currentNode = currentNode.next; // 记录指针位置 counter++; } } } }

}

  

 

  
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
 

/**
 * 通过数据找到节点，移除节点 <br>
 * @Date 2021/08/04 15:12
 * @return void
 */
public static <T> void removeByValue(MySinglyLinkedList<T> list , T data) { Node<T> currentNode = list.head; Node<T> prevNode = null; if (currentNode != null) { // 第一个节点 if (currentNode.data == data) { // 节点移动，改变head节点 list.head = currentNode.next; } else { while (currentNode != null && currentNode.data != data) { prevNode = currentNode; currentNode = currentNode.next; } // 找到了节点 if (currentNode != null) { // 节点移动 prevNode.next = currentNode.next; System.out.println(String.format("移除节点：%s" , data)); } else { // 找不到对应节点 System.out.println("遍历不到对应data的节点"); } } }
}

  

 

  
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
 

• 链表size
  这个逻辑就比较容易理解了，直接遍历，统计就行

/**
 * 统计单遍历节点数量 <br>
 * @Date 2021/08/04 16:25
 * @Param [list]
 * @return int
 */
public static <T> int size(MySinglyLinkedList<T> list) { int counter = 0; Node<T> currentNode = list.head; while (currentNode.next != null) { currentNode = currentNode.next; counter ++; } return counter;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
 

• 链表查询
  变量查找的，可以通过递归，也可以用while循环

/**
 * 查询单链表<br>
 * @Date 2021/08/04 16:24
 * @Param [head, data]
 * @return boolean
 */
public static <T> boolean search(Node<T> head, T data) { if (head == null) { return false; } if (head.data == data) { return true; } // 递归查找 return search(head.next , data);
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

8、Java实现链表实例

/**
 * 单链表java代码实现
 * @date 2021/08/04
 */
public class MySinglyLinkedList<T> { public Node<T> head; private static class Node<T> { public T data; public Node next; Node(T data) { this.data = data; next = null; } } /** * 链表新增节点，直接附加到链表最后面 * @Date 2021/08/04 13:54 * @Param [list, data] * @return void */ public static <T> void add(MySinglyLinkedList<T> list , T data) { Node<T> newNode = new Node<T>(data); // 单链表是empty的，将新增的节点直接作为head节点 if (list.head == null) { list.head = newNode; } else { // 其它情况直接在链接后面附加上新节点 Node<T> currentNode = list.head; while (currentNode.next != null) { currentNode = currentNode.next; } // 将新增的节点作为最后一个节点 currentNode.next = newNode; } } /** * 在指定前驱节点后面附加新节点 <br> * @Date 2021/08/04 14:26 * @Param prevNode 前驱节点 * @Param data 新增节点数据 * @return void */ public static <T> void addAfter(Node<T> prevNode , T data) { if (prevNode == null) { System.out.println("前驱节点不能为null"); } // 原本链表0->2，创建新节点1 Node<T> newNode = new Node<T>(data); // 将新节点的指针指向前驱节点原本的next节点 1->2 newNode.next = prevNode.next; // 将前驱节点的next指针指向新节点 0->1 prevNode.next = newNode; } /** * 指定下标移除链表节点 <br> * @Date 2021/08/04 14:34 * @Param [list, pos] * @return void */ public static <T> void removeAtPosition(MySinglyLinkedList<T> list , int pos) { // 当前节点 Node<T> currentNode = list.head; // 记录前一个节点 Node<T> prevNode = null; // 下标计数器 int counter = 0; if (currentNode != null) { // 移除第一个节点 if (pos == 0) { // 指针移动，节点往后移，再将下一个节点置为head节点 list.head = currentNode.next; } else { while (currentNode!= null) { // 找到移除节点要节点位置 if (counter == pos) { prevNode.next = currentNode.next; break; } else { // 记录前驱节点 prevNode = currentNode; // 往后遍历 currentNode = currentNode.next; // 记录指针位置 counter++; } } } } } /** * 通过数据找到节点，移除节点 <br> * @Date 2021/08/04 15:12 * @return void */ public static <T> void removeByValue(MySinglyLinkedList<T> list , T data) { Node<T> currentNode = list.head; Node<T> prevNode = null; if (currentNode != null) { // 第一个节点 if (currentNode.data == data) { // 节点移动，改变head节点 list.head = currentNode.next; } else { while (currentNode != null && currentNode.data != data) { prevNode = currentNode; currentNode = currentNode.next; } // 找到了节点 if (currentNode != null) { // 节点移动 prevNode.next = currentNode.next; System.out.println(String.format("移除节点：%s" , data)); } else { // 找不到对应节点 System.out.println("遍历不到对应data的节点"); } } } } /** * 打印单链表数据 <br> * @Date 2021/08/04 16:24 * @Param [list] * @return void */ public static <T> void printLinkedList(MySinglyLinkedList<T> list) { Node<T> currentNode = list.head; while (currentNode != null) { if (currentNode.next != null) { System.out.print(String.format("%s -> ", currentNode.data)); } else { System.out.print(String.format("%s", currentNode.data)); } currentNode = currentNode.next; } System.out.println(); } /** * 查询单链表<br> * @Date 2021/08/04 16:24 * @Param [head, data] * @return boolean */ public static <T> boolean search(Node<T> head, T data) { if (head == null) { return false; } if (head.data == data) { return true; } // 递归查找 return search(head.next , data); } /** * 统计单遍历节点数量 <br> * @Date 2021/08/04 16:25 * @Param [list] * @return int */ public static <T> int size(MySinglyLinkedList<T> list) { int counter = 0; Node<T> currentNode = list.head; while (currentNode.next != null) { currentNode = currentNode.next; counter ++; } return counter; } public static MySinglyLinkedList<Integer> buildLinedList() { MySinglyLinkedList<Integer> list = new MySinglyLinkedList<Integer>(); MySinglyLinkedList.add(list , 0); MySinglyLinkedList.add(list , 1); MySinglyLinkedList.add(list , 2); MySinglyLinkedList.add(list , 3); MySinglyLinkedList.add(list , 4); MySinglyLinkedList.add(list , 5); MySinglyLinkedList.add(list , 6); MySinglyLinkedList.add(list , 7); MySinglyLinkedList.add(list , 8); MySinglyLinkedList.add(list , 9); MySinglyLinkedList.add(list , 10); return list; } public static void main(String[] args) { MySinglyLinkedList<Integer> list = buildLinedList(); System.out.println(String.format("linked list size : %s" , size(list))); // 打印验证，0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 printLinkedList(list); // 在head节点的下一个节点后面加上新节点 addAfter(list.head.next , 11); // 打印验证，0 -> 1 -> 11 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 printLinkedList(list); // 重置链表 list = buildLinedList(); // 在对应位置移除链表节点 removeAtPosition(list , 1); // 打印验证，0 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 printLinkedList(list); // 重置链表 list = buildLinedList(); // 根据数据移除链表节点 removeByValue(list , 10); // 打印验证 ，0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 printLinkedList(list); // 重置链表 list = buildLinedList(); Node headNode = list.head; if (search(headNode , 5)) { System.out.println("查找到对应的节点"); } else { System.out.println("不能查找到对应节点"); } }

}



  

 

  
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
  
242
  
243
  
244
 

9、参考文档资料

https://www.javadevjournal.com/data-structure/linked-list/

文章来源: smilenicky.blog.csdn.net，作者：smileNicky，版权归原作者所有，如需转载，请联系作者。

原文链接：smilenicky.blog.csdn.net/article/details/119276857