关于数据结构中链表的介绍和代码实现
1 单链表
1.1 介绍
- （1）链表是以节点的方式来存储
- （2）每个节点包含data域，next域
- （3）链表各个节点之间未必是连续的
- （4）链表分带头节点的链表和没有头结点的链表，根据实际的需求来确定
1.2 思路
- （1）链表新增数据
- 尾插法：循环遍历链表，找到
结点.next == null的节点，即尾节点，在尾节点插入数据 - 在链表节点之间插入：找到要插入位置的前一个节点，将前一节点.next指向插入数据，将插入数据.next指向原来位置的节点
- （2）删除链表的数据
- 找到要删除位置的前一个节点，将
前一个节点.next == 删除结点.next，Java的垃圾回收机制，会自动收回没有被指向的节点
1.3 代码实现
- 以下例子是手写的一个单链表类，提供增，删，改的操作
- （1）创建单链表类和子类节点类
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
179public class SingleLinkedList {
//创建子类Node节点
private class Node {
public String data; //数据
public Node next; //下一个节点
public Node(String data) {
this.data = data;
}
public String toString() {
return "Node{ data = " + data + " }";
}
}
private Node headNode; //头结点
//构造对象时，自动创建头结点
public SingleLinkedList() {
headNode = new Node("");
}
/**
* 链表添加数据（尾插法）
* @param data 数据
*/
public void addData(String data) {
//设置中间变量，避免修改头结点
Node temp = headNode;
//循环遍历找到尾结点（next==null）
while(temp.next != null) {
temp = temp.next;
}
//尾结点的next插入新增结点
temp.next = new Node(data);
}
/**
* 在指定下标插入链表数据
* @param data 数据
* @param index 下标
*/
public void addDataByIndex(String data, int index) {
Node temp = headNode.next;
if(temp == null && index != 0) {
System.out.println("error：链表为空，index只能从0号位置插入数据！");
return;
}
if(index > getSize()) {
System.out.println("error：index越界，请重新确认index的大小！");
return;
}
if(index != 0) {
//循环遍历，找到指定Index前一个Node
int count = 0;
while(count != index-1) {
temp = temp.next;
count ++;
}
}else {
temp = headNode;
}
//插入Node，修改链表的指向（node的next结点继承前一个节点temp的next，temp的next指向node）
Node node = new Node(data);
node.next = temp.next;
temp.next = node;
}
/**
* 通过index更新链表结点
* @param data 数据
* @param index 下标
*/
public void updateDataByIndex(String data, int index) {
Node temp = headNode.next;
if(temp == null) {
System.out.println("error：链表为空，没有数据可改！");
return;
}
if(index > getSize()-1) {
System.out.printf("error：index越界，链表的长度为%d，请重新确认index大小！\n", getSize());
return;
}
//找出结点，并修改数据
int count = 0;
while (count != index) {
temp = temp.next;
count ++;
}
temp.data = data;
}
/**
* 通过index删除结点
* @param index 下标
*/
public void deleteDataByIndex(int index) {
Node temp = headNode.next;
if(temp == null) {
System.out.println("error：链表为空，没有数据可删！");
return;
}
if(index > getSize()-1) {
System.out.printf("error：index越界，链表的长度为%d，请重新确认index大小！\n", getSize());
return;
}
int count = 0;
if(index == 0) {
temp = headNode;
}else {
while(count != index-1) {
temp = temp.next;
count ++;
}
}
//修改结点指向，删除结点
temp.next = temp.next.next;
}
/**
* 打印单链表
*/
public void printLinkedList() {
Node temp = headNode.next;
if(temp == null) {
System.out.println("链表为空！");
return;
}
System.out.println("单链表为：");
int count = 0;
while(temp != null) {
System.out.print(count + " - ");
System.out.println(temp);
count ++;
temp = temp.next;
}
}
/**
* 获取链表的大小（不算头结点）
* @return int
*/
public int getSize() {
Node temp = headNode.next;
if(temp == null) {
return 0;
}
int count = 0;
while(temp != null) {
count ++;
temp = temp.next;
}
return count;
}
}
- （2）测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void SingleLinkedListTest() {
//1、创建单链表并添加数据
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.addData("hello");
linkedList.addData("world");
linkedList.printLinkedList();
//2、插入测试（节点间插入）
linkedList.addDataByIndex(" - ", 1);
linkedList.printLinkedList();
//3、修改测试
linkedList.updateDataByIndex("Java", 2);
linkedList.printLinkedList();
//4、删除测试
linkedList.deleteDataByIndex(1);
linkedList.printLinkedList();
}
2 面试题
2.1 查找单链表中倒数第k个节点
- 思路：找出所有有效节点的个数，减去k，得到节点的下标，通过该下标获取节点即可
- （1）代码实现
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/**
* 逆序获取数据（取出倒数数据）
* @param index 下标
*/
public void getDataByReverseIndex(int index) {
Node temp = headNode.next;
//空链表判断
if(temp == null) {
System.out.println("链表为空，没有数据可取！");
return;
}
//获取链表长度（方法在前面写好，就直接拿来用）
int size = getSize();
//数据合法检验
if(index < 1 || index > size) {
System.out.println("数据不合法，请重新确认index的大小！");
return;
}
//遍历找出相同下标节点
int count = 0;
while(count != size - index) {
temp = temp.next;
count ++;
}
System.out.println(temp);
}
- （2）测试
1
2
3
4
5
6
7
8
9
10
11
public void SingleLinkedListTest() {
//1、创建单链表并添加数据
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.addData("hello");
linkedList.addData("world");
linkedList.printLinkedList();
//2.取倒数第1个节点测试
linkedList.getDataByReverseIndex(1);
}
2.2 单链表反转
- 思路：
- 自己创建一个新的头结点reverseHead
- 遍历原来的链表，每遍历一个节点，就在reverseHead的链表中插入数据（头插法），即从第一个位置插入数据，操作方法和节点间插入数据一致
- 遍历完毕后，就将原来链表的头结点.next == reverseHead.next来修改链表指向
- （1）代码实现
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/**
* 反转单链表
*/
public void reverseLinkedList() {
//创建反转头结点
Node reverseHead = new Node("");
Node temp = headNode.next;
//判断空链表
if(temp == null) {
System.out.println("链表为空，没有数据可以反转！");
return;
}
//链表节点是否只有一个（一个不需反转）
if (temp.next.next == null) {
return;
}
//遍历原来节点，并插入（头插法）
while(temp != null) {
//将节点取出，并后移（避免原链表断链）
Node reverseTemp = temp;
temp = temp.next;
//头插法（节点间插入）
reverseTemp.next = reverseHead.next;
reverseHead.next = reverseTemp;
}
//修改头结点的next
headNode.next = reverseHead.next;
}
- （2）测试
1
2
3
4
5
6
7
8
9
10
11
12
public void SingleLinkedListTest() {
//1、创建单链表并添加数据
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.addData("hello");
linkedList.addData("world");
linkedList.printLinkedList();
//2. 链表反转
linkedList.reverseLinkedList();
linkedList.printLinkedList();
}
2.3 逆序打印
- 思路
- 第一种：可以向链表逆序，再进行打印，再逆序回来，变回原表（不推荐）
- 第二种：可以使用递归来实现，递归跳出条件为节点为空
- 第三种：使用栈来实现，栈的效果就是先进后出（后面详细讲，暂时使用API来实现栈）
- （1）递归实现
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/**
* 通过递归逆序打印
*/
public void reversePrintByRecursion() {
Node temp = headNode.next;
if(temp == null) {
System.out.println("链表为空！");
return;
}
//递归
System.out.println("逆序链表为：");
int count = 0;
recursion(temp, count);
}
/**
* 逆序递归主要实体
* @param temp 结点
* @param count 下标
* @return int
*/
private int recursion(Node temp, int count) {
//递归跳出条件
if(temp == null) {
return count;
}
//递归
count = recursion(temp.next, count);
//打印
System.out.print(count + " - ");
System.out.println(temp);
return ++count;
}
- （2）递归测试
1
2
3
4
5
6
7
8
9
10
11
public void SingleLinkedListTest() {
//1、创建单链表并添加数据
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.addData("hello");
linkedList.addData("world");
linkedList.printLinkedList();
//2. 逆序打印
linkedList.reversePrintByRecursion();
}
- （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/**
* 用栈实现逆序打印
*/
public void reversePrintByStack() {
Node temp = headNode.next;
//判断空链表
if (temp == null) {
System.out.println("链表为空！");
return;
}
//引入java.util.Stack来用栈（官方包）
Stack<Node> nodeStack = new Stack<>();
//入栈
while (temp != null) {
nodeStack.add(temp);
temp = temp.next;
}
//出栈打印
System.out.println("逆序单链表为：");
int count = 0;
while (nodeStack.size() > 0) {
System.out.print(count + " - ");
Node popNode = nodeStack.pop();
System.out.println(popNode);
count ++;
}
}
- （4）栈测试
1
2
3
4
5
6
7
8
9
10
11
public void SingleLinkedListTest() {
//1、创建单链表并添加数据
SingleLinkedList linkedList = new SingleLinkedList();
linkedList.addData("hello");
linkedList.addData("world");
linkedList.printLinkedList();
//2. 逆序打印
linkedList.reversePrintByStack();
}