|
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
|
package
com.datastructure.singlylinklist;
/** * 实现一个单链表
* 实现功能：
* 增加一个节点（头插法，尾插法）
* 删除一个节点（删除第一个节点，删除最后一个节点，删除任何一个节点）
* 查找（查找到一个list中的某个元素）
* @author Xinyuyu
*
*/
public
class SinglyLinkList <T> {
/*
* 实现一个节点的数据结构
* 数据域
* 指针域
*/
// header指向list的头
// tail指向list的尾
private
IntSLLNode header;
private
IntSLLNode tail;
class
IntSLLNode{
public
Object data;
public
IntSLLNode next;
//
public
IntSLLNode(Object data){
this(data, null);
}
public
IntSLLNode(Object data, IntSLLNode next){
this.data = data;
this.next = next;
}
}
public
SinglyLinkList(){
header = tail = null;
}
// 头插法增加一个节点
public
void addToHeader(Object o){
// 链表不为空的情况
// 链表为空的情况
header = new
IntSLLNode(o, header);
if(tail == null)
tail = header;
}
// 尾插法增加一个节点
public
void addToTail(Object o){
// 链表不为空的情况
// 链表为空的情况
IntSLLNode newNode = new
IntSLLNode(o);
if(!isEmpty()){
tail.next = newNode;
tail = newNode;
}else
tail = header = newNode;
}
// 删除第一个节点
public
Object deleteFromHeader() throws
Exception{
// 链表不为空切大于一个节点
// 链表仅有一个节点
// 链表为空
IntSLLNode node = header;
if(!isEmpty()){
header = header.next;
}else
if(!isEmpty() && header == tail){
tail = header = null;
}else{
// 链表为空抛出异常
throw
new Exception("SSL is empty");
}
return
node.data;
}
// 删除最后一个节点
public
Object delteFromTail() throws
Exception{
// 链表不是空且大于一个节点的时候
// 链表仅有一个节点的时候
// 链表是空的情况
IntSLLNode node = tail;
if(!isEmpty() && header != tail){
// 一个临时指针，指向头节点，遍历到倒数第二个节点出，将尾指针指向倒数第二个节点
IntSLLNode temp = header;
for(; temp.next != tail;){
temp = temp.next;
}
tail = temp;
temp.next = null;
}else
if(!isEmpty() && header == tail){
tail = header = null;
}else{
// 当列表为空的时候抛出异常
throw
new Exception("SSL is empty");
}
return
node.data;
}
// 删除链表中的某个节点
public
Object delete(Object o) throws
Exception{
// 链表不为空且包含大于一个节点
// 链表仅包含一个节点
// 链表为空的情况
// 删除的为第一个节点
if(o.equals(header.data)){
return
deleteFromHeader();
// 删除的为最后一个节点
}else
if(o.equals(tail.data)){
return
delteFromTail();
}else{
IntSLLNode temp = header;
if(!isEmpty() && header != tail){
for(; !temp.next.data.equals(o);){
temp = temp.next;
}
if(temp != null){
temp.next = temp.next.next;
temp = temp.next;
}
}else
if(!isEmpty() && header == tail){
if(header.equals(o)){
temp = header;
header = tail = null;
}
}else{
throw
new Exception("SSL is empty");
}
return
temp.data;
}
// 如果查找到就返回一个节点信息
// 查找不到
}
// 删除节点的另外一个写法(需要两个指针)
public
Object deletePro(Object o) throws
Exception{
// 链表不为空且大于一个节点
// 链表仅包含一个节点
// 链表为空
IntSLLNode node = null;
if(header.data.equals(o)){
return
deleteFromHeader();
}
if(!isEmpty() && header != tail){
IntSLLNode pre = header, las = header.next;
for(; las != null
&& !las.data.equals(o); ){
pre = pre.next;
las = las.next;
}
if(las != null)
pre.next = las.next;
else
return
delteFromTail();
node = las;
}else
if(!isEmpty() && header == tail){
if(header.equals(o));
tail = header = null;
}else{
throw
new Exception("SSL is empty");
}
return
node.data;
}
// 查找链表中的某个节点
public
Object find(Object o) throws
Exception{
// 链表为空
// 链表不为空
IntSLLNode temp = null;
if(!isEmpty()){
temp = header;
for(; temp != null
&& !temp.data.equals(o); ){
temp = temp.next;
}
if(temp == null)
return
null;
else
return
temp.data;
}else{
// 当链表为空的时候也就是不会查找到需要的节点
throw
new Exception("The object is not exist in the SLL");
}
}
// 判断链表是否为空
public
boolean isEmpty(){
return
header == null;
}
// 打印出链表
public
void printSinglyLinkList(String name){
System.out.print(name + " : ");
for(IntSLLNode tempNode = header; tempNode != null; tempNode = tempNode.next){
System.out.print(tempNode.data.toString() + "->");
}
}
// 清空列表
public
void emptySLL(){
header = tail = null;
}
} |
|
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
|
package
SinglyLinkList;
public class Persion {
private
String name;
private
int
age;
public
Persion(String name, int
age) {
this.name = name;
this.age = age;
}
public
String getName() {
return
name;
}
public
void setName(String name) {
this.name = name;
}
public
int getAge() {
return
age;
}
public
void setAge(int
age) {
this.age = age;
}
public
String toString(){
return
"[" + this.name + " age is "
+ this.age + "]";
}
// 需要重写equal方法来完成删除和查找
@Override
public
boolean equals(Object o) {
if(this.name.equals(((Persion) o).getName()) && this.age == ((Persion) o).getAge())
return
true;
else
return
false;
}
} |
|
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
|
package
SinglyLinkList;
import com.datastructure.singlylinklist.SinglyLinkList;
public class TestOfSinglyList {
public
static void main(String[] args) {
SinglyLinkList<Persion> singlyLinkList = new
SinglyLinkList<Persion>();
Persion p1 = new
Persion("张三", 34);
Persion p2 = new
Persion("李四", 24);
Persion p3 = new
Persion("王五", 44);
Persion p4 = new
Persion("李以", 44);
Persion p5 = new
Persion("王七", 44);
// 完成头插法
singlyLinkList.addToHeader(p1);
singlyLinkList.addToHeader(p2);
singlyLinkList.addToHeader(p3);
singlyLinkList.addToHeader(p4);
singlyLinkList.addToHeader(p5);
singlyLinkList.printSinglyLinkList("完成头插法");
System.out.println();
// System.out.println();// // 清空链表// singlyLinkList.emptySLL();// // 完成尾插法// singlyLinkList.addToTail(p1);// singlyLinkList.addToTail(p2);// singlyLinkList.addToTail(p3);// singlyLinkList.printSinglyLinkList("完成头插法");// System.out.println();// // 完成删除尾节点// try {// Persion p = (Persion)singlyLinkList.delteFromTail();// singlyLinkList.printSinglyLinkList("删除了最后一个节点");// System.out.println();// System.out.println("被删除的尾节点是 :" + p.getName() + " age is " + p.getAge());// } catch (Exception e) {// e.printStackTrace();// } // // 完成删除头节点// try {// Persion p = (Persion)singlyLinkList.deleteFromHeader();// singlyLinkList.printSinglyLinkList("删除了第一个节点");// System.out.println();// System.out.println("被删除的头节点是 :" + p.getName() + " age is " + p.getAge());// } catch (Exception e) {// e.printStackTrace();// } // 删除任意一个节点
//Persion p = new Persion("张三", 34);
try
{
singlyLinkList.deletePro(p5);
singlyLinkList.deletePro(p4);
singlyLinkList.deletePro(p3);
singlyLinkList.deletePro(p2);
singlyLinkList.deletePro(p1);
} catch
(Exception e) {
e.printStackTrace();
}
singlyLinkList.printSinglyLinkList("任意删除一个节点");
System.out.println();
try
{
System.out.println(singlyLinkList.find(p1));
} catch
(Exception e) {
e.printStackTrace();
}
}
} |