Data Structure LinkedList

Linked List is a sequence of links which contains items. Each link contains a connection to another link.

前言

    链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

单向链表

小结:

1)链表是以节点的方式来存储,是链式存储

2)每个节点包含 data 域, next 域:指向下一个节点.

3)如图:发现链表的各个节点不一定是连续存储.

4)链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定

链表图解:



单向链表代码:

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
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
import java.util.Stack;

/**
* @Auther: Arsenal
* @Date: 2020-03-08 10:28
* @Description: 链表
*/
public class SingleLinkedListDemo {
public static void main(String[] args) {
SingleLinkedList singleLinkedList = new SingleLinkedList();
HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
HeroNode heroNode2 = new HeroNode(3, "卢俊义", "玉麒麟");
HeroNode heroNode3 = new HeroNode(5, "吴用", "智多星");
HeroNode heroNode4 = new HeroNode(7, "公孙胜", "入云龙");

SingleLinkedList singleLinkedList1 = new SingleLinkedList();
HeroNode heroNode5 = new HeroNode(2, "唐僧", "唐三藏");
HeroNode heroNode6 = new HeroNode(4, "孙悟空", "齐天大圣");
HeroNode heroNode7 = new HeroNode(6, "猪八戒", "天蓬元帅");
HeroNode heroNode8 = new HeroNode(8, "沙僧", "卷帘大将");

// singleLinkedList.addHeroNode(heroNode3);
// singleLinkedList.addHeroNode(heroNode2);
// singleLinkedList.addHeroNode(heroNode4);
// singleLinkedList.addHeroNode(heroNode1);
// singleLinkedList.list();


//合并两个有序的单链表,合并之后的链表依然有序【课后练习.】
singleLinkedList.addHeroNodeByOrder(heroNode4);
singleLinkedList.addHeroNodeByOrder(heroNode3);
singleLinkedList.addHeroNodeByOrder(heroNode2);
singleLinkedList.addHeroNodeByOrder(heroNode1);
singleLinkedList.list();

singleLinkedList1.addHeroNodeByOrder(heroNode8);
singleLinkedList1.addHeroNodeByOrder(heroNode7);
singleLinkedList1.addHeroNodeByOrder(heroNode6);
singleLinkedList1.addHeroNodeByOrder(heroNode5);
singleLinkedList1.list();
System.out.println("================合并两个有序的单链表,合并之后的链表依然有序================");
HeroNode mergeTwoLinkedList = SingleLinkedList.mergeTwoLinkedList(singleLinkedList.getHead(), singleLinkedList1.getHead());
singleLinkedList1.list(mergeTwoLinkedList);

//从尾到头打印单链表 【百度,要求方式1:反向遍历 。 方式2:Stack栈】
// System.out.println("================从尾到头打印单链表================");
// SingleLinkedList.printReverseLinkedList(singleLinkedList.getHead());

//单链表的反转【腾讯面试题,有点难度】
// System.out.println("================反转链表================");
// SingleLinkedList.reverseLinkedList(singleLinkedList.getHead());
// singleLinkedList.list();


// singleLinkedList.addHeroNodeByOrder(heroNode4);
// singleLinkedList.addHeroNodeByOrder(heroNode3);
// singleLinkedList.addHeroNodeByOrder(heroNode2);
// singleLinkedList.addHeroNodeByOrder(heroNode1);
// singleLinkedList.list();
//
// System.out.println("================修改后链表信息================");
// HeroNode newHeroNode = new HeroNode(3, "老王", "隔壁老王");
// singleLinkedList.updateHeroNode(newHeroNode);
// singleLinkedList.list();
//
// System.out.println("================删除后链表信息================");
// singleLinkedList.delHeroNode(1);
// singleLinkedList.delHeroNode(4);
// singleLinkedList.list();
//
// System.out.println("================链表有效节点个数================");
// System.out.println(SingleLinkedList.getLinkedLength(singleLinkedList.getHead()));
//
// //查找单链表中的倒数第k个结点 【新浪面试题】
// System.out.println("================单链表中的倒数第k个结点================");
// System.out.println("result=" + SingleLinkedList.getLastIndexHeroNode(singleLinkedList.getHead(), 0));

}
}

/**
* 单向链表
*/
class SingleLinkedList {

private HeroNode head = new HeroNode(0, "", "");

/**
* 获得头节点
* @return
*/
public HeroNode getHead() {
return head;
}

/**
* 添加节点
* @param heroNode 节点
*/
public void addHeroNode(HeroNode heroNode) {
HeroNode temp = head;
while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
}
temp.next = heroNode;
}

/**
* 按顺序添加节点
* @param heroNode 节点
*/
public void addHeroNodeByOrder(HeroNode heroNode) {
HeroNode temp = head;
boolean flag = false; //是否找到该节点的标志
while (true) {
if (temp.next == null) {
break;
} else if (temp.next.no > heroNode.no) {
break; //找到了要插入的节点
} else if (temp.next.no == heroNode.no) {
flag = true; //已有存在该编号节点,不能插入
break;
}
temp = temp.next;
}

if (flag) {
System.out.printf("已有存在%d编号节点,不能插入\n", heroNode.no);
} else {
//插入节点
heroNode.next = temp.next;
temp.next = heroNode;
}
}

/**
* 更新节点
* @param newHeroNode 新节点
*/
public void updateHeroNode(HeroNode newHeroNode) {
HeroNode temp = head;
boolean flag = false; //是否找到该节点的标志
while (true) {
if (temp.next == null) {
break;
}
if (temp.no == newHeroNode.no) {
flag = true; //找到了要修改的节点
break;
}
temp = temp.next;
}

if (temp.next == null) {
System.out.println("链表为空");
}

if (flag) {
temp.name = newHeroNode.name;
temp.nickName = newHeroNode.nickName;
} else {
System.out.printf("没有编号%d节点\n", newHeroNode.no);
}
}

/**
* 删除节点
* @param no 要删除的节点编号
*/
public void delHeroNode(int no) {
HeroNode temp = head;
boolean flag = false; //是否找到该节点的标志
while (true) {
if (temp.next == null) {
break;
}

if (temp.next.no == no) {
flag = true;
break;
}
temp = temp.next;
}

if (flag) {
temp.next = temp.next.next;
} else {
System.out.printf("要删除的%d节点不存在\n", no);
}
}

/**
* 遍历展示节点信息
*/
public void list() {

HeroNode temp = head;
if (temp.next == null) {
System.out.println("链表为空");
return;
}

while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
System.out.println(temp);
}
}

public void list(HeroNode head) {
HeroNode temp = head;
if (temp.next == null) {
System.out.println("链表为空");
return;
}

while (true) {
if (temp.next == null) {
break;
}
temp = temp.next;
System.out.println(temp);
}
}

/**
* 单链表中有效节点的个数
* @param head 头节点
* @return 个数
*/
public static int getLinkedLength(HeroNode head) {
if (head.next == null) {
return 0;
}

HeroNode cur = head.next;
int length = 0;
while (cur != null) {
length++;
cur = cur.next;
}
return length;
}

/**
* 查找单链表中的倒数第k个结点 【新浪面试题】
* @param head 头节点
* @param index 倒数index个
* @return 倒数第index个结点
*/
public static HeroNode getLastIndexHeroNode(HeroNode head, int index) {
if (head.next == null) {
return null;
}

int size = getLinkedLength(head);

if (index <= 0 || index > size) {
return null;
}

HeroNode cur = head.next;
for (int i = 0; i < size - index; i++) {
cur = cur.next;
}
return cur;
}

/**
* 单链表的反转【腾讯面试题,有点难度】
* @param head 头节点
*/
public static void reverseLinkedList(HeroNode head) {
if (head.next == null || head.next.next == null) {
return; //空链表和单个元素链表无需反转
}
HeroNode reverseHead = new HeroNode(0, "", "");
HeroNode cur = head.next; //用来遍历链表
HeroNode next = null; //临时保存cur指向的下一个节点
while (cur != null) {
next = cur.next;
cur.next = reverseHead.next;
reverseHead.next = cur;
cur = next;
}
//实现head反转
head.next = reverseHead.next;
}

/**
* 从尾到头打印单链表 【百度,要求方式1:反向遍历 。 方式2:Stack栈】
* @param head 头节点
*/
public static void printReverseLinkedList(HeroNode head) {
if (head.next == null) {
System.out.println("队列为空");
return;
}
Stack<HeroNode> heroNodeStack = new Stack<>();
//压栈
HeroNode cur = head.next;
while (cur != null) {
heroNodeStack.push(cur);
cur = cur.next;
}

//弹栈,打印
cur = head.next;
while (cur != null) {
System.out.println(heroNodeStack.pop());
cur = cur.next;
}
}

/**
* 合并两个有序的单链表,合并之后的链表依然有序【课后练习.】
* @param head1 头节点1
* @param head2 头节点2
* @return 合并后链表头节点
*/
public static HeroNode mergeTwoLinkedList(HeroNode head1, HeroNode head2) {
if (head1.next == null) {
return head2;
}

if (head2.next == null) {
return head1;
}

HeroNode mergeHead = new HeroNode(0, "", "");

HeroNode cur1 = head1.next;
HeroNode cur2 = head2.next;
HeroNode mergeCur = mergeHead;
while (cur1 != null && cur2 != null) {
if (cur1.no <= cur2.no) {
mergeCur.next = cur1;
mergeCur = mergeCur.next;
cur1 = cur1.next;
} else {
mergeCur.next = cur2;
mergeCur = mergeCur.next;
cur2 = cur2.next;
}
}

// 任一为空,直接连接另一条链表
if (cur1 == null) {
mergeCur.next = cur2;
} else {
mergeCur.next = cur1;
}
return mergeHead;
}
}

/**
* 节点
*/
class HeroNode {
public int no;
public String name;
public String nickName;
public HeroNode next;

public HeroNode(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}

@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}

双向链表

简介:
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

代码:

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
/**
* @Auther: Arsenal
* @Date: 2020-03-09 21:08
* @Description: 双向链表
*/
public class DoubleLinkedListDemo {

public static void main(String[] args) {
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
Node node1 = new Node(1, "曹操", "曹孟德");
Node node2 = new Node(2, "刘备", "刘玄德");
Node node3 = new Node(3, "孙权", "孙仲谋");
// doubleLinkedList.addNodeToTail(node1);
// doubleLinkedList.addNodeToTail(node2);
// doubleLinkedList.addNodeToTail(node3);
//doubleLinkedList.list();

// System.out.println("=================修改节点=================");
// Node newNode = new Node(1, "老王", "隔壁老王");
// doubleLinkedList.update(newNode);
// doubleLinkedList.list();
// System.out.println("=================删除节点=================");
// doubleLinkedList.delNode(2);
// doubleLinkedList.list();
System.out.println("=================排序插入节点=================");
doubleLinkedList.addNodeByOrder(node2);
doubleLinkedList.addNodeByOrder(node3);
doubleLinkedList.addNodeByOrder(node1);
doubleLinkedList.list();

}
}

/**
* 双向链表
*/
class DoubleLinkedList {

private Node head = new Node(0, "", "");

public Node getHead() {
return head;
}

/**
* 按顺序添加节点
* @param newNode 需添加的节点
*/
public void addNodeByOrder(Node newNode) {

if (head.next == null) {
head.next = newNode;
newNode.pre = head;
return;
}
Node cur = head.next;
while (cur != null) {
if (head.next.no > newNode.no) {
//比第一个还小的情况
head.next.pre = newNode;
newNode.next = head.next;

head.next = newNode;
newNode.pre = head;
break;
} else if (cur.no > newNode.no) {
//中间情况
cur.pre = newNode;
newNode.next = cur;
cur.pre.next = newNode;
newNode.pre = cur.pre;
break;
} else if (cur.no == newNode.no) {
System.out.println("已存在" + newNode.no + "节点,不能添加");
break;
} else if (cur.next == null) {
//最末尾的情况
cur.next = newNode;
newNode.pre = cur;
break;
}
cur = cur.next;
}
}

/**
* 修改节点
* @param newNode 新的节点的值
*/
public void update(Node newNode) {

if (head.next == null) {
System.out.println("链表为空");
return;
}

Node cur = head.next;
boolean flag = false;
while (cur != null) {
if (cur.no == newNode.no) {
flag = true;
break;
}
cur = cur.next;
}

if (flag) {
//找到要修改的节点
cur.name = newNode.name;
cur.nickName = newNode.nickName;
} else {
System.out.println("要修改的" + newNode.no + "节点不存在");
}

}

/**
* 删除节点
* @param no 需删除节点的编号
*/
public void delNode(int no) {
if (head.next == null) {
System.out.println("链表为空");
return;
}
Node cur = head.next;
boolean flag = false;
while (cur != null) {
if (cur.no == no) {
flag = true;
break;
}
cur = cur.next;
}

if (flag) {
//找到要删除的节点
cur.pre.next = cur.next;
if (cur.next != null) { //判断如果是最后一个元素,那该元素的next为空,需排除空指针的情况
cur.next.pre = cur.pre;
}
} else {
System.out.println("要删除的" + no + "节点不存在");
}
}

/**
* 在链表尾部添加节点
* @param node
*/
public void addNodeToTail(Node node) {
Node cur = head;
//找到最后一个节点
while (true) {
if (cur.next == null) {
break;
}
cur = cur.next;
}
cur.next = node;
node.pre = cur;
}

/**
* 遍历链表
*/
public void list() {
if (head.next == null) {
System.out.println("链表为空");
return;
}

Node cur = head.next;
while (cur != null) {
System.out.println(cur);
cur = cur.next;
}

}
}

/**
* 节点
*/
class Node {
public int no; //编号
public String name; //名字
public String nickName; //昵称
public Node pre; //前一个节点
public Node next; //下一个节点

public Node(int no, String name, String nickName) {
this.no = no;
this.name = name;
this.nickName = nickName;
}

@Override
public String toString() {
return "Node{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}

单向循环链表

简介:
链式的存储结构,在逻辑上是连续的,每次通过一个指针来指向下一个节点将其链接起来。

构建一个单向的环形链表思路:

  1. 先创建第一个节点, 让 first 指向该节点,并形成环形;
  2. 后面当我们每创建一个新的节点,就把该节点,加入到已有的环形链表中即可。

遍历环形链表:

  1. 先让一个辅助指针(变量) curBoy,指向first节点;
  2. 然后通过一个while循环遍历 该环形链表即可 curBoy.next == first 结束。

Josephu 问题:
设编号为1,2,… n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m 的那个人出列,它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。

n = 5 , 即有5个人
k = 1, 从第一个人开始报数
m = 2, 数2下

解决思路:

  1. 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点.
    补充: 小孩报数前,先让 first 和 helper 移动 k - 1次
  2. 当小孩报数时,让first 和 helper 指针同时 的移动 m - 1 次
  3. 这时就可以将first 指向的小孩节点 出圈
    first = first .next
    helper.next = first
    原来first 指向的节点就没有任何引用,就会被回收

出圈的顺序
2->4->1->5->3

代码:

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
/**
* @Auther: Arsenal
* @Date: 2020-03-10 23:56
* @Description: 单向环形链表
* Josephu 问题:
* 设编号为1,2,… n的n个人围坐一圈,约定编号为k(1<=k<=n)的人从1开始报数,数到m 的那个人出列,
* 它的下一位又从1开始报数,数到m的那个人又出列,依次类推,直到所有人出列为止,由此产生一个出队编号的序列。
* <p>
* n = 5 , 即有5个人
* k = 1, 从第一个人开始报数
* m = 2, 数2下
* <p>
* 出圈的顺序
* 2->4->1->5->3
*/
public class Josephu {
public static void main(String[] args) {
SingleCircleLinkedList singleCircleLinkedList = new SingleCircleLinkedList(5);
singleCircleLinkedList.showBoy();
System.out.println("============出圈的顺序============");
singleCircleLinkedList.boyOut(1, 2, 5);
}
}

/**
* 单向环形链表
*/
class SingleCircleLinkedList {
Boy first = null;

/**
* 构造器初始化单向环形链表
* @param number 节点数
*/
public SingleCircleLinkedList(int number) {
if (number < 1) {
System.out.println("无法创建个数为" + number + "的环形链表");
return;
}
Boy curBoy = null;
for (int i = 1; i <= number; i++) {
Boy boy = new Boy(i);
//该节点为第一个节点时
if (i == 1) {
first = boy;
first.setNext(first); // 构成环
curBoy = first; // 让curBoy指向第一个小孩
} else { //非第一个节点时
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}

/**
* 遍历单向循环链表
*/
public void showBoy() {
if (first == null) {
System.out.println("空链表");
return;
}
Boy cur = first;
while (true) {
System.out.println("小孩的编号:" + cur.getNo());
if (cur.getNext() == first) { // 说明已经遍历完毕
break;
}
cur = cur.getNext();
}

}

/**
* 小孩出圈
* @param startNo 从第几个开始数
* @param countNum 数几下
* @param nums 初始人数
*/
public void boyOut(int startNo, int countNum, int nums) {

// 先对数据进行校验
if (first == null || startNo < 1 || startNo > nums) {
System.out.println("参数输入有误, 请重新输入");
return;
}

// 创建要给辅助指针,帮助完成小孩出圈
Boy helper = first;
// 需求创建一个辅助指针(变量) helper , 事先应该指向环形链表的最后这个节点
while (true) {
if (helper.getNext() == first) { // 说明helper指向最后小孩节点
break;
}
helper = helper.getNext();
}
//小孩报数前,先让 first 和 helper 移动 k - 1次
for (int i = 0; i < startNo - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
//当小孩报数时,让first 和 helper 指针同时 的移动 m - 1 次, 然后出圈
//这里是一个循环操作,知道圈中只有一个节点
while (true) {
if (first == helper) { //说明链表中只剩一个节点
break;
}
//按数的次数移动
for (int i = 0; i < countNum - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
//此时first即为要出圈的小孩,打印之
System.out.println("编号为:" + first.getNo() + " 的小孩出圈");
//小孩出圈
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最后留在圈中的小孩编号%d \n", first.getNo());
}
}

/**
* 节点
*/
class Boy {
private int no; //编号
private Boy next; //下一个节点

public Boy(int no) {
this.no = no;
}

public int getNo() {
return no;
}

public void setNo(int no) {
this.no = no;
}

public Boy getNext() {
return next;
}

public void setNext(Boy next) {
this.next = next;
}
}

延伸

    链表
    双向链表
    链表实战(带图分析)
    数据结构–双向链表
    单向循环链表
    韩顺平数据结构和算法
    Linked List Data Structure
    Data Structure and Algorithms - Linked List
    经典算法–约瑟夫环问题的三种解法
    (单向、单向循环、双向、双向循环)链表学习总结

Content
  1. 1. 前言
  2. 2. 单向链表
  3. 3. 双向链表
  4. 4. 单向循环链表
  5. 5. 延伸