使用java实现单链表----（java中的引用就是指针）转载自：https://www.cnblogs.com/zhongyimeng/p/9945332.html
|
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
|
//一直以为java中没有指针，其实java的引用就是指针，只不过堆栈中的引用储存了在堆中的地址，可以看做java中的指针。<br>public class sibgleLink<E> { // 结点内部类
private class Node {
private Object data;
private Node next = null;
public Node() {
data = null;
}
// 带数据的构造函数
public Node(E data) {
this.data = data;
}
}
private Node head; // 头引用（指针）
private Node rear; // 尾引用（指针）
private Node point; // 临时引用（指针）
private int length = 1; // 链表长度
// 带参数的构造函数
public sibgleLink(E e) {
head = new Node();
head.data = e;
rear = head;
length = 1;
}
// 尾插法
public void add(E elem) {
point = new Node(elem);
rear.next = point;
rear = point;
length++;
}
// 遍历节点
public void traverse() {
point = head; // 移动临时引用到头结点
if (head != null)
System.out.print("[" + head.data + "]");
while (point.next != null) {
System.out.print("->[" + point.next.data + "]");
point = point.next;
}
System.out.println();
}
// 返回长度
public int length() {
return this.length;
}
// 清除
public boolean clear() {
while (head.next.next != null) {
head.next = head.next.next;
}
head.next = null;
rear = head;
point = null;
length = 1;
return true;
}
// 插入元素
public boolean insert(int x, E data) {
// 工作节点
point = head;
int wz = 1;
if (x == 1) {
Node n = new Node(data);
n.next = head;
head = n;
length++;
return true;
}
if (x < 1 || x > this.length) {
return false;
} else {
while (point.next != null && wz < x - 1) {
point = point.next;
wz++;
}
// 放入一个节点
Node n = new Node(data);
n.next = point.next;
point.next = n;
length++;
return true;
}
}
// 删除
public boolean del(int x) {
point = head;
int wz = 1;
if (x < 0 || x > length) {
return false;
} else if (x == length) {
point = head;
while (point.next != null) {
point = rear;
point.next = null;
length--;
}
} else {
while (point.next != null && wz < x - 1) {
point = point.next;
wz++;
}
Node d = point.next;
point.next = point.next.next;
d = null;
return true;
}
return false;
}
// 更改
public boolean change(int x, E data) {
point = head;
int wz = 1;
if (x < 0 || x > length) {
return false;
} else {
while (point.next != null && wz < x) {
point = point.next;
wz++;
}
point.data = data;
return true;
}
}
// 移动指针
private Node movePoint(int position) {
if (position < 0)
return head;
if (position > length)
return rear;
if (position >= 0 && position <= length) {
point = head;
while (point != null) {
if (position == 0)
break;
position--;
point = point.next;
}
}
return point;
}
public E find(int position) {
if (position >= 0 && position < length) {
Node tmp = movePoint(position);
return (E) tmp.next.data;
}
return null;
}
// test
public static void main(String[] args) {
sibgleLink<Integer> si = new sibgleLink<Integer>(0);
si.add(5);
si.add(6);
si.insert(2, 2);
si.traverse();
si.del(3);
si.traverse();
si.change(3, 77);
si.traverse();
System.out.println(si.length());
}
} |
结果：
|
1
2
3
4
|
[0]->[2]->[5]->[6]
[0]->[2]->[6]
[0]->[2]->[77]
4 |