SingleLinkedList独立实现

现在对Java原生数据结构特感兴趣,于是决定自己动手实现一些类,比如这个List类,在熟习了单链表和双链表的数据结构之后,终于实现了,代码如下:

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
package hk.inso.service;

/**
* Created by IntelliJ IDEA.
* Date: 8/10/15 6:09 PM
* Author: Richard
*/
public class SingleLinkedList<E> {

private static class Node<E> {

private E element;
private Node next;

public Node(E element) {
//constructor with args
this.element = element;
}

public Node() {
//constructor without args
}

@Override
public String toString() {
return element.toString();
}
}

private Node first;
private Node last;

/**
* 添加元素到链表头部
* @param element
*/
public void add(E element) {
Node<E> node = new Node<E>(element);
linkFirst(node);
}
/**
* 添加元素到链表尾部
* @param element
*/
public void addLast(E element) {
Node<E> node = new Node<E>(element);
linkLast(node);
}

/**
* 根据索引移除元素
* @param index
*/
public void remove(int index) {
if (index == 0) {
unlinkFirst();
}
else{
Node node = getNode(index);
unlink(node);
}

}

/**
* 移除链表中最后一个元素
*/
public void removeLast() {
unlinkLast();
}

/**
* 将元素插入指定链表索引为止
* @param index
* @param element
*/
public void insert(int index, E element) {
Node<E> node1 = new Node<E>(element);
if(index == 0) {
linkFirst(node1);
} else {
Node node2 = getNode(index);
link(node1, node2);
}
}

/**
* 获取某个元素
* @param index
* @return
*/
public E get(int index) {
Node<E> node = getNode(index);
E element = node.element;
return element;
}

/**
* 统计链表里面所有元素的个数
* @return 总的元素的个数
*/
public int size() {
int count = 0;
Node node = first;
while (node != null) {
count++;
node = node.next;
}
return count;
}

/**
* toString方法实现
* @return
*/
@Override
public String toString() {
Node node = first;
StringBuilder stringBuilder = new StringBuilder();
if(node == null) {
return "{}";
}
while (node != null) {
stringBuilder.append("[" + node.element.toString() +"],");
node = node.next;
}
String result = stringBuilder.toString();
int index = result.lastIndexOf(",");
return result.substring(0, index);

}

/**
* 插入结点到链表中间
* 插入前
* node2->node3->node4
* 插入后
* node2->node1->node3->node4
* @param node1 要插入的结点
* @param node2 插入结点位置结点
*/
private void link(Node node1, Node node2) {
node1.next = node2;
Node prevNode = getPrevNode(node2);
prevNode.next = node1;
}

/**
* 插入结点到链表首部
* @param node
*/
private void linkFirst(Node node) {

if(first == null || last == null) {
first = last = node;
} else {
node.next = first;
first = node;
}

}

/**
* 插入结点到链表尾部
* @param node
*/
private void linkLast(Node node) {
last.next = node;
last = node;
}

/**
* 从链表中间移除当前结点
* @param node
*/
private void unlink(Node node) {
Node prevNode = getPrevNode(node);
prevNode.next = node.next;
}

/**
* 移除头部的结点
*/
private void unlinkFirst() {
first = first.next;
}

/**
* 移除尾部的结点
*/
private void unlinkLast() {
Node prevNode = getPrevNode(last);
prevNode.next = null;
last = prevNode;
}

/**
* 寻找当前结点的前一个结点
* @param node 当前结点
* @return
*/
private Node getPrevNode(Node node) {
//这里多走了一步
// Node nodeItr = first.next;
Node nodeItr = first;
Node prevNode = new Node();
while (!nodeItr.equals(node)) {
prevNode = nodeItr;
nodeItr = nodeItr.next;
}
return prevNode;
}

/**
* 根据索引查找链表中得数据
* @param index
* @return 链表结点
*/
private Node getNode(int index) {
Node node = first;
Node currentNode = new Node();
if (index == 0) {
//continue
}

if (index >= size()) {
throw new IndexOutOfBoundsException(errMessage(index));
}
else {
int i = 0;
while (i <= index) {
if(node != null) {
currentNode = node;
//注意这里有递增
node = node.next;
}
i++;
}
}
return currentNode;
}

/**
* 错误消息显示
* @param index
* @return
*/
private String errMessage(int index) {
return "Size: "+ size() + ", index: "+ index;
}

}

测试代码:

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
package hk.inso.test;

import hk.inso.service.SingleLinkedList;

/**
* Created by IntelliJ IDEA.
* Date: 8/11/15 4:58 PM
* Author: Richard
*/
public class TestSingleLinkedList {

public static void main(String[] args) {

SingleLinkedList<User> list = new SingleLinkedList<User>();
list.add(new User(5, "Jimmy", "Girl"));
list.add(new User(7, "Tom", "Boy"));
list.addLast(new User(6, "Amy", "Girl"));
System.out.println(list.toString());
}
}

class User {

private int age;
private String name;
private String gender;

public User(int age, String name, String gender) {
this.age = age;
this.name = name;
this.gender = gender;
}

public int getAge() {
return age;
}

public void setAge(int age) {
this.age = age;
}

public String getName() {
return name;
}

public void setName(String name) {
this.name = name;
}

public String getGender() {
return gender;
}

public void setGender(String gender) {
this.gender = gender;
}

@Override
public String toString() {
return "User{" +
"age=" + age +
", name='" + name + '\'' +
", gender='" + gender + '\'' +
'}';
}
}

以上代码均测试通过!

分享到