链表
链表的定义
链表
是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点
(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分: 一个是存储数据元素的数据域
,另一个是存储下一个结点地址的指针域
.
链表的使用场景
- 数据量较小.
- 不需要预先知道数据规模.
- 适应于频繁的插入操作.
链表的实现方式
单向链表
- 首先定义一个链表
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
30package pers.huangyuhui.linkedlist;
/**
* @ClassName: ListNode
* @Description: 单向链表
* @author: HuangYuhui
* @date: Apr 15, 2019 8:59:50 PM
*
*/
public class SinglyListNode<E> {
private E data;
private SinglyListNode<E> next;// the pointer
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public SinglyListNode<E> getNext() {
return next;
}
public void setNext(SinglyListNode<E> next) {
this.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
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
156package pers.huangyuhui.linkedlist;
/**
* @ClassName: SinglyLinkedList
* @Description: 操作单向链表
* @author: HuangYuhui
* @date: Apr 15, 2019 8:54:46 PM
*
*/
public class SinglyLinkedList<T> {
SinglyListNode<T> headNode;
public void createLinkedList() {
headNode = new SinglyListNode<T>();
// headNode.setData(0);// attention: the header node is zero default
}
// get the header node of the linked list
public T getHeaderNode() {
return headNode.getData();
}
// get the length of the linked list
public int getListLength(/* ListNode headNode */) {
int length = 0;
SinglyListNode<T> currentNode = headNode;
while (currentNode != null) {
currentNode = currentNode.getNext();
length++;
}
return length;
}
// add a new node into the linked list by specified position
public SinglyListNode<T> insertInLinked(SinglyListNode<T> nodeToInsert, int position) {
if (headNode == null) {
System.err.println("Error: the linked list is empty !");
return nodeToInsert;
}
int size = getListLength();
if (position > size + 1 || position < 1) {
System.err.println("Position of node to insert is invalid. The vaild inputs are 1 to " + (size + 1));
return headNode;
}
if (position == 1) {
nodeToInsert.setNext(headNode);
headNode = nodeToInsert;
return nodeToInsert;
} else {
int count = 1;
SinglyListNode<T> previousNode = headNode;
while (count < position - 1) {
previousNode = previousNode.getNext();// 待插节点的前节点
count++;
}
SinglyListNode<T> currentNode = previousNode.getNext();// 待插节点的后节点
nodeToInsert.setNext(currentNode);
previousNode.setNext(nodeToInsert);
}
return headNode;
}
// delete the node by the specified position in the linked node
public boolean deleteNodeFromLinkedList(/* ListNode headNode, */ int position) {
int size = getListLength();
if (position > size || position < 1) {
System.err.println("Position of node to insert is invalid. The vaild inputs are 1 to" + (size + 1));
return false;
}
if (position == 1) {
SinglyListNode<T> currentNode = headNode.getNext();
headNode = currentNode;
return true;
} else {// 删除中间或表尾结点
int count = 1;
SinglyListNode<T> previousNode = headNode.getNext();
while (count < position) {
previousNode = previousNode.getNext(); // 找到待删节点的前节点
count++;
}
SinglyListNode<T> currentNode = previousNode.getNext();// 待删节点
previousNode.setNext(currentNode.getNext());
currentNode = null;
}
return true;
}
// delete the singly linked list
public boolean destroyLinkedList(/* ListNode headNode */) {
if (headNode == null) {
System.err.println("Error: the singly linked list is empty !");
return false;
}
System.out.print("delete the node: ");
while (headNode != null) {
System.out.print(headNode.getData() + " , ");
headNode = headNode.getNext();
}
System.out.println();
return true;
}
// Iterate through all the data in the linked list
public boolean traverseNode( /* ListNode headNode */) {
if (headNode == null) {
System.err.println("Error: the linked node is empty !");
return false;
}
SinglyListNode<T> currentNode = headNode;
System.out.print("All of node: ");
while (currentNode != null) {
System.out.print(currentNode.getData() + " , ");
currentNode = currentNode.getNext();
}
System.out.println();
return true;
}
// Test
public static void main(String[] args) {
SinglyLinkedList<String> list = new SinglyLinkedList<String>();
// 定义待插入链表的节点
SinglyListNode<String> a = new SinglyListNode<String>();
a.setData("A");
SinglyListNode<String> b = new SinglyListNode<String>();
b.setData("B");
SinglyListNode<String> c = new SinglyListNode<String>();
c.setData("C");
// 向单向链表中添加新的节点
list.createLinkedList();
list.insertInLinked(a, 1);
list.insertInLinked(b, 2);
list.insertInLinked(c, 1);
System.out.println("The size of linked list: " + list.getListLength());
System.out.println("The header node : " + list.getHeaderNode());
list.traverseNode();
System.out.println("Delete the node which the position is first: " + list.deleteNodeFromLinkedList(1));
list.traverseNode();
System.out.println("Delete all of node: " + list.destroyLinkedList());
System.out.println("The size of linked list: " + list.getListLength());
list.traverseNode();
}
} - 程序运行结果
1
2
3
4
5
6
7
8
9The size of linked list: 4
The header node : C
All of node: C , A , B , null ,
Delete the node which the position is first: true
All of node: A , B , null ,
delete the node: A , B , null ,
Delete all of node: true
The size of linked list: 0
Error: the linked node is empty !
双向链表
定义链表
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
39package pers.huangyuhui.linkedlist;
/**
* @ClassName: BidirectionalLinkList
* @Description: 双向链表
* @author: HuangYuhui
* @date: Apr 16, 2019 2:31:09 PM
*
*/
public class DoubleListNode<E> {
private E data;
private DoubleListNode<E> next;// the pointer
private DoubleListNode<E> previous;
public E getData() {
return data;
}
public void setData(E data) {
this.data = data;
}
public DoubleListNode<E> getNext() {
return next;
}
public void setNext(DoubleListNode<E> next) {
this.next = next;
}
public DoubleListNode<E> getPrevious() {
return previous;
}
public void setPrevious(DoubleListNode<E> previous) {
this.previous = previous;
}
}操作双向链表的示例程序
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
166package pers.huangyuhui.linkedlist;
/**
* @ClassName: CircularList
* @Description: 操作循环链表
* @author: HuangYuhui
* @date: Apr 16, 2019 2:28:27 PM
*
*/
public class DoubleLinkedList<T> {
DoubleListNode<T> headNode;
// initialize the circular list
public void createCircularList() {
headNode = new DoubleListNode<T>();// Attention: the header node is empty default
// headNode.setData(0);
}
// get the length of the circular list
public int getLength() {
int length = 0;
DoubleListNode<T> currentNode = headNode;
while (currentNode != null) {
currentNode = currentNode.getNext();
length++;
}
return length;
}
// get the header node of the double linked list
public T getHeaderNode() {
if (headNode == null) {
System.err.println("Error: the double linked list is empty !");
return null;
}
return headNode.getData();
}
// add new node into the double linked list by the specified position
public DoubleListNode<T> insertNode(DoubleListNode<T> newNode, int position) {
if (headNode == null) {
System.err.println("Error: the double linked list is empty !");
}
int size = getLength();
if (position < 1 || position > size + 1) {
System.err.println("Position of node to insert is invalid. The vaild inputs are 1 to " + (size + 1));
return headNode;
}
if (position == 1) {
newNode.setNext(headNode);
headNode.setPrevious(newNode);
headNode = newNode;// 更新头结点
return headNode;
} else {
int count = 1;
DoubleListNode<T> previousNode = headNode;
while (count < position - 1) {
previousNode = previousNode.getNext();
count++;
}
DoubleListNode<T> currentNode = previousNode.getNext();// 找到待插位置的节点
newNode.setNext(currentNode);
if (currentNode != null) {// 如果待插位置的节点不是尾节点
currentNode.setPrevious(newNode);
}
previousNode.setNext(newNode);
newNode.setPrevious(previousNode);
}
return headNode;
}
// delete node by the spcified position in the double linked list
public boolean deleteNode(int position) {
if (headNode == null) {
System.err.println("Error: the circular list is empty !");
return false;
}
if (position == 1) {
DoubleListNode<T> secondNode = headNode.getNext();
secondNode.setPrevious(null);
headNode = secondNode;// as the header node
} else {
int count = 1;
//// `previousNode`与`headNode`操作的是同一个对象哟 ! ////
DoubleListNode<T> previousNode = headNode;
while (count < position - 1) {
previousNode = previousNode.getNext();// 待删节点的前节点
count++;
}
DoubleListNode<T> currentNode = previousNode.getNext();// 待删节点
DoubleListNode<T> laterNode = currentNode.getNext();// 待删节点的后节点
previousNode.setNext(laterNode);
if (laterNode != null) {
laterNode.setPrevious(previousNode);
currentNode = null;
}
}
return true;
}
// Iterate through all the data in the linked list
public void traverseNode() {
DoubleListNode<T> node = headNode;
if (node == null) {
System.err.println("Error: the circular list is empty !");
}
while (node != null) {
System.out.println("the node: " + node.getData());
node = node.getNext();
}
}
// destroy the double linked list
public void destroyList() {
if (headNode == null) {
System.out.println("Error: the circular list is empty !");
}
while (headNode != null) {
System.out.println("delete the node: " + headNode.getData());
headNode = headNode.getNext();
}
}
// Test
public static void main(String[] args) {
// CircularList<Integer> list = new CircularList<Integer>();
DoubleLinkedList<Character> list = new DoubleLinkedList<Character>();
// 初始化待插节点
DoubleListNode<Character> a = new DoubleListNode<Character>();
a.setData('a');
DoubleListNode<Character> b = new DoubleListNode<Character>();
b.setData('b');
DoubleListNode<Character> c = new DoubleListNode<Character>();
c.setData('c');
// 向双向链表中添加新节点
list.createCircularList();
list.insertNode(a, 1);
list.insertNode(b, 2);
list.insertNode(c, 3);
System.out.println("-------- traverse --------");
list.traverseNode();
System.out.println("--------------------------");
System.out.println("The header node: " + list.getHeaderNode());
System.out.println("The length of the circular list: " + list.getLength());
System.out.println("Delete the node which the position is one: " + list.deleteNode(1));
System.out.println("-------- traverse --------");
list.traverseNode();
System.out.println("--------------------------");
System.out.println("The header node: " + list.getHeaderNode());
System.out.println("The length of the circular list: " + list.getLength());
System.out.println();
list.destroyList();
System.out.println("The header node: " + list.getHeaderNode());
}
}程序运行结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22-------- traverse --------
the node: a
the node: b
the node: c
the node: null
--------------------------
The header node: a
The length of the circular list: 4
Delete the node which the position is one: true
-------- traverse --------
the node: b
the node: c
the node: null
--------------------------
The header node: b
The length of the circular list: 3
delete the node: b
delete the node: c
delete the node: null
The header node: null
Error: the double linked list is empty !
循环链表
定义一个链表
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
31package pers.huangyuhui.linkedlist;
/**
* @ClassName: CircularListNode
* @Description: 循环链表
* @author: HuangYuhui
* @date: Apr 17, 2019 9:52:23 AM
*
*/
public class ListNode<T> {
private T data;
private ListNode<T> next;
public T getData() {
return data;
}
public void setData(T data) {
this.data = data;
}
public ListNode<T> getNext() {
return next;
}
public void setNext(ListNode<T> next) {
this.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
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
219package pers.huangyuhui.linkedlist;
/**
* @ClassName: CircularLinkedList
* @Description: 操作循环链表
* @author: HuangYuhui
* @param <T>
* @date: Apr 16, 2019 7:25:36 PM
*
*/
public class CircularLinkedList<T> {
// get the length of the circular linked list
public int getLength(ListNode<T> headNode) {
int length = 0;
ListNode<T> currentNode = headNode;
while (currentNode != null) {
currentNode = currentNode.getNext();
length++;
if (currentNode == headNode) {
break;
}
}
return length;
}
// traverse the node of the circular linked list
public void traverseNode(ListNode<T> headNode) {
ListNode<T> currentNode = headNode;
while (currentNode != null) {
System.out.print(currentNode.getData() + " -> ");
currentNode = currentNode.getNext();
if (currentNode == headNode) {
break;
}
}
System.out.print("headNode(" + currentNode.getData() + ")\n");
}
// add new node at the tail of linked list
public void insertAtListTail(ListNode<T> headNode, ListNode<T> newNode) {
ListNode<T> currentNode = headNode;
while (currentNode.getNext() != headNode) {
//// 注意: 由于`currentNode`无变化,导致`currentNode.getNext() != headNode`继而进入进入死循环 !////
// currentNode.setNext(currentNode.getNext());
currentNode = currentNode.getNext();
}
newNode.setNext(newNode);
if (headNode == null) {
headNode = newNode;
} else {
newNode.setNext(headNode);
currentNode.setNext(newNode);
}
}
// add new node at the header of linked list
public ListNode<T> insertAtListHeader(ListNode<T> headNode, ListNode<T> newNode) {
ListNode<T> currentNode = headNode;
while (currentNode.getNext() != headNode) {
currentNode = currentNode.getNext();// 尾节点
}
newNode.setNext(newNode);// 指针指向自身
if (headNode == null) {
headNode = newNode;
}
newNode.setNext(headNode);
currentNode.setNext(newNode);
// 注意: 此时链表头结点已更新! 所以应该返回更新后的头节点继而避免遍历时出现死循环!!!
headNode = newNode;
return headNode;
}
// add the new node by the specified index
public ListNode<T> insertNodeByIndex(ListNode<T> headNode, ListNode<T> newNode, int position) {
if (headNode == null) {
System.out.println("Error: the circular list is empty !");
return null;
} else if (position == 1) {
insertAtListHeader(headNode, newNode);
} else if (position == getLength(headNode)) {
insertAtListTail(headNode, newNode);
} else {
ListNode<T> currentNode = headNode;
ListNode<T> temp = headNode;
for (int i = 0; i < position - 1; i++) {
temp = currentNode;// 待插节点的前节点
currentNode = currentNode.getNext();// 待插节点
}
temp.setNext(newNode);
newNode.setNext(currentNode);
}
return headNode;
}
// delete the last node
public void deleteLastNode(ListNode<T> headNode) {
ListNode<T> temp = headNode;
ListNode<T> currentNode = headNode;
if (headNode == null) {
System.err.println("Error: the circular list is empty !");
}
while (currentNode.getNext() != headNode) {
temp = currentNode; // 尾节点的前一个节点
currentNode = currentNode.getNext();
}
temp.setNext(headNode);
currentNode = null;
}
// delete the header node
public ListNode<T> deleteHeaderNode(ListNode<T> headNode) {
ListNode<T> currentNode = headNode;
if (headNode == null) {
System.err.println("Error: the circular list is empty !");
return null;
}
while (currentNode.getNext() != headNode) {
// currentNode.setNext(currentNode.getNext());//死循环
currentNode = currentNode.getNext();
}
currentNode.setNext(headNode.getNext());
// 注意: 此时链表头结点已更新! 所以应该返回更新后的头节点继而避免遍历时出现死循环!!!
headNode = headNode.getNext();
return headNode;
}
// delete the node by the specified index
public ListNode<T> deleteNodeByIndex(ListNode<T> headNode, int position) {
if (headNode == null) {
System.out.println("Error: the circular linked list is empty !");
return null;
} else if (position == 1) {
deleteHeaderNode(headNode);
} else if (position == getLength(headNode)) {
deleteLastNode(headNode);
} else {
ListNode<T> currentNode = headNode;
ListNode<T> temp = headNode;
for (int i = 0; i < position - 1; i++) {
temp = currentNode;// 待删节点的前节点
currentNode = currentNode.getNext();// 待删节点
}
temp.setNext(currentNode.getNext());
}
return headNode;
}
// Test
public static void main(String[] args) {
// 初始化链表头结点
CircularLinkedList<Integer> list = new CircularLinkedList<>();
ListNode<Integer> headNode = new ListNode<>();
headNode.setData(1);// 初始化链表头结点
headNode.setNext(headNode);// 节点指针指向自身
// 初始化待插入的链表节点
ListNode<Integer> a = new ListNode<>();
a.setData(2);
ListNode<Integer> b = new ListNode<>();
b.setData(3);
ListNode<Integer> c = new ListNode<>();
c.setData(4);
ListNode<Integer> d = new ListNode<>();
d.setData(100);
ListNode<Integer> e = new ListNode<>();
e.setData(101);
ListNode<Integer> f = new ListNode<>();
f.setData(0);
// 向链表的尾部添加三个节点
System.out.print("the origin node: ");
list.insertAtListTail(headNode, a);
list.insertAtListTail(headNode, b);
list.insertAtListTail(headNode, c);
list.traverseNode(headNode);
System.out.println("the length of the list: " + list.getLength(headNode));
// 向链表中添加两个头结点
System.out.print("add two header node: ");
ListNode<Integer> newHeadNode = list.insertAtListHeader(headNode, d);
// 注意: 由于`头结点`已在`insertAtListHeader`中已更新所以要向`traverseNode`传入新的头结点
ListNode<Integer> newHeadNode2 = list.insertAtListHeader(newHeadNode, e);
list.traverseNode(newHeadNode2);
System.out.println("the length of the list: " + list.getLength(headNode));
// 在链表的指定位置上插入新的节点
System.out.print("Insert the new node at position 3: ");
list.insertNodeByIndex(headNode, f, 3);
list.traverseNode(newHeadNode2);
System.out.println("the length of the list: " + list.getLength(headNode));
// 删除链表的尾节点
System.out.print("delete the tail node: ");
list.deleteLastNode(newHeadNode2);
list.traverseNode(newHeadNode2);
System.out.println("the length of the list: " + list.getLength(headNode));
// 注意: 由于`头结点`已在`deleteHeaderNode`中已更新所以要向`traverseNode`传入新的头结点
ListNode<Integer> newHeadNode3 = list.deleteHeaderNode(newHeadNode2);
System.out.print("delete the header node: ");
list.traverseNode(newHeadNode3);
System.out.println("the length of the list: " + list.getLength(headNode));
// 删除链表中指定位置的节点
ListNode<Integer> newHeadNode4 = list.deleteNodeByIndex(newHeadNode3, 4);
System.out.print("delete the fourth node: ");
list.traverseNode(newHeadNode4);
System.out.println("the length of the list: " + list.getLength(headNode));
}
}程序运行结果
1
2
3
4
5
6
7
8
9
10
11
12the origin node: 1 -> 2 -> 3 -> 4 -> headNode(1)
the length of the list: 4
add two header node: 101 -> 100 -> 1 -> 2 -> 3 -> 4 -> headNode(101)
the length of the list: 6
Insert the new node at position 3: 101 -> 100 -> 1 -> 2 -> 0 -> 3 -> 4 -> headNode(101)
the length of the list: 7
delete the tail node: 101 -> 100 -> 1 -> 2 -> 0 -> 3 -> headNode(101)
the length of the list: 6
delete the header node: 100 -> 1 -> 2 -> 0 -> 3 -> headNode(100)
the length of the list: 5
delete the fourth node: 100 -> 1 -> 2 -> 3 -> headNode(100)
the length of the list: 4
推荐书籍
- 上述示例程序主要参考本书籍:《数据结构与算法经典问题解析》—— 纳拉辛哈·卡路曼希[著]
- 很认真的说这是我大二至今看过的最好的一本关于数据结构与算法的书籍哟 ! 其针对不同问题提供多个具有不同复杂度的解决方案.兼顾自学教材和面试辅导的不同需求呢 !
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment