一、JAVA单向链表的操作（增加节点、查找节点、删除节点）
|
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
|
class
Link {
// 链表类
class
Node {
// 保存每一个节点，此处为了方便直接定义成内部类
private
String data;
// 节点的内容
private
Node next;
// 保存下一个节点
public
Node(String data) {
// 通过构造方法设置节点内容
this
.data = data;
}
public
void
add(Node node) {
// 增加节点
if
(
this
.next ==
null
) {
// 如果下一个节点为空，则把新节点加入到next的位置上
this
.next = node;
}
else
{
// 如果下一个节点不为空，则继续找next
this
.next.add(node);
}
}
public
void
print() {
// 打印节点
if
(
this
.next !=
null
) {
System.out.print(
this
.data +
"-->"
);
this
.next.print();
}
else
{
System.out.print(
this
.data +
"\n"
);
}
}
public
boolean
search(String data) {
// 内部搜索节点的方法
if
(
this
.data.equals(data)) {
return
true
;
}
if
(
this
.next !=
null
) {
return
this
.next.search(data);
}
else
{
return
false
;
}
}
public
void
delete(Node previous, String data) {
// 内部删除节点的方法
if
(
this
.data.equals(data)) {
previous.next =
this
.next;
}
else
{
if
(
this
.next !=
null
) {
this
.next.delete(
this
, data);
}
}
}
}
private
Node root;
// 定义头节点
public
void
addNode(String data) {
// 根据内容添加节点
Node newNode =
new
Node(data);
// 要插入的节点
if
(
this
.root ==
null
) {
// 没有头节点，则要插入的节点为头节点
this
.root = newNode;
}
else
{
// 如果有头节点，则调用节点类的方法自动增加
this
.root.add(newNode);
}
}
public
void
print() {
// 展示列表的方法
if
(root !=
null
) {
// 当链表存在节点的时候进行展示
this
.root.print();
}
}
public
boolean
searchNode(String data) {
// 在链表中寻找指定内容的节点
return
root.search(data);
// 调用内部搜索节点的方法
}
public
void
deleteNode(String data) {
// 在链表中删除指定内容的节点
if
(root.data.equals(data)) {
// 如果是头节点
if
(root.next !=
null
) {
root = root.next;
}
else
{
root =
null
;
}
}
else
{
root.next.delete(
this
.root, data);
}
}
}
|
测试：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public
class
TestMain {
public
static
void
main(String[] args) {
Link l =
new
Link();
l.addNode(
"A"
);
l.addNode(
"B"
);
l.addNode(
"C"
);
l.addNode(
"D"
);
System.out.println(
"原链表："
);
l.print();
String searchNode =
"B"
;
System.out.println(
"查找节点:"
+ searchNode);
String result = l.searchNode(searchNode)?
"找到!"
:
"没找到!"
;
System.out.println(
"查找结果："
+ result);
System.out.println(
"删除节点："
+ searchNode);
l.deleteNode(searchNode);
System.out.println(
"删除节点后的链表："
);
l.print();
}
}
|
测试结果如下：
|
1
2
3
4
5
6
7
|
原链表：
A-->B-->C-->D
查找节点:B
查找结果：找到!
删除节点：B
删除节点后的链表：
A-->C-->D
|
二、双向链表的简单实现
|
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
|
public
class
DoubleLink<T> {
/**
* Node<AnyType>类定义了双向链表中节点的结构，它是一个私有类， 而其属性和构造函数都是公有的，这样，其父类可以直接访问其属性
* 而外部类根本不知道Node类的存在。
*
* @author ZHB
*
* @param <T>
* 类型
* @param Data
* 是节点中的数据
* @param pre
* 指向前一个Node节点
* @param next
* 指向后一个Node节点
*/
private
class
Node<T> {
public
Node<T> pre;
public
Node<T> next;
public
T data;
public
Node(T data, Node<T> pre, Node<T> next) {
this
.data = data;
this
.pre = pre;
this
.next = next;
}
public
Node() {
this
.data =
null
;
this
.pre =
null
;
this
.next =
null
;
}
}
// 下面是DoubleLinkedList类的数据成员和方法
private
int
theSize;
private
Node<T> Header;
private
Node<T> Tail;
/*
* 构造函数 我们构造了一个带有头、尾节点的双向链表 头节点的Next指向尾节点 为节点的pre指向头节点 链表长度起始为0。
*/
public
DoubleLink() {
theSize =
0
;
Header =
new
Node<T>(
null
,
null
,
null
);
Tail =
new
Node<T>(
null
, Header,
null
);
Header.next = Tail;
}
public
void
add(T item) {
Node<T> aNode =
new
Node<T>(item,
null
,
null
);
Tail.pre.next = aNode;
aNode.pre = Tail.pre;
aNode.next = Tail;
Tail.pre = aNode;
theSize++;
}
public
boolean
isEmpty() {
return
(
this
.theSize ==
0
);
}
public
int
size() {
return
this
.theSize;
}
public
T getInt(
int
index) {
if
(index >
this
.theSize -
1
|| index <
0
)
throw
new
IndexOutOfBoundsException();
Node<T> current = Header.next;
for
(
int
i =
0
; i < index; i++) {
current = current.next;
}
return
current.data;
}
public
void
print() {
Node<T> current = Header.next;
while
(current.next !=
null
) {
System.out.println(current.data.toString());
current = current.next;
}
}
public
static
void
main(String[] args) {
DoubleLink<String> dLink =
new
DoubleLink<String>();
dLink.add(
"zhb"
);
dLink.add(
"zzb"
);
dLink.add(
"zmy"
);
dLink.add(
"zzj"
);
System.out.println(
"size : "
+ dLink.size());
System.out.println(
"isEmpty? : "
+ dLink.isEmpty());
System.out.println(
"3 : "
+ dLink.getInt(
2
));
dLink.print();
}
}
|
本文转自Work Hard Work Smart博客园博客，原文链接：http://www.cnblogs.com/linlf03/p/5278629.html，如需转载请自行联系原作者
