线性表 - 双向链表
# 概念
如果一个 Node 中有两个指针域,其中一个存储当前元素后继元素的地址信息,另外一个存储当前元素前驱元素的地址信息,则被称为双向链表。
# 双向链表实现
# 抽象数据类型
public class DoubleLinkList {
DoubleNode head;
int size;
public DoubleLinkList() {
head = new DoubleNode();
}
}
class DoubleNode {
Object data;
// 直接前驱指针
DoubleNode prior;
// 直接后继指针
DoubleNode next;
public DoubleNode() {
}
public DoubleNode(Object obj) {
data = obj;
}
@Override
public String toString() {
return data.toString();
}
}
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
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
# 插入结点
假设要将结点 s 插入到结点 p 和 p->next 之间,需要下面几步:
- 把 p 赋值给 s 的前驱指针,s->prior = p;
- 把 p->next 赋值给 s 的后继指针,s->next = p->next;
- 把 s 赋值给 p->next 的前驱指针,p->next->prior = s;
- 把 s 赋值给 p 的后继指针,p->next = s。
public boolean insert(Object obj, int i) {
if (i < 0 || i > size) {
System.out.println("插入位置不正确");
return false;
}
DoubleNode s = new DoubleNode(obj);
DoubleNode p = head;
for (int j = 0; j < i; j++) {
p = p.next;
}
s.prior = p;
s.next = p.next;
if (p.next != null) {
// 避免添加第0个结点出现空指针
p.next.prior = s;
}
p.next = s;
size++;
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 删除结点
要删除 p 结点,只需两步:
- 把 p->next 赋值给 p->prior 的后继指针,p->prior->next = p->next;
- 把 p->prior 赋值给 p->next 的前驱指针,p->next->prior = p->prior。
public DoubleNode remove(int i) {
if (i < 0 || i > size - 1) {
System.out.println("删除位置不正确");
return null;
}
DoubleNode p = head;
for (int j = 0; j <= i; j++) {
p = p.next;
}
if (p == null) {
// 没找到
return null;
} else {
// 找到了
p.prior.next = p.next;
if (p.next != null) {
// 避免删除最后一个结点出现空指针
p.next.prior = p.prior;
}
size--;
return p;
}
}
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 完整代码
package com.sqlboy.lineartable;
public class DoubleLinkList {
DoubleNode head;
int size;
public DoubleLinkList() {
head = new DoubleNode();
}
/**
* 打印链表
*/
public void show() {
DoubleNode node = head.next;
for (int i = 0; i < size; i++) {
if (i == 0) {
System.out.println(node + " , prior " + "null" + " , next " + node.next);
} else {
System.out.println(node + " , prior " + node.prior + " , next " + node.next);
}
node = node.next;
}
System.out.println();
}
/**
* 在指定位置插入新结点
*
* @param obj
* @param i
*/
public boolean insert(Object obj, int i) {
if (i < 0 || i > size) {
System.out.println("插入位置不正确");
return false;
}
DoubleNode s = new DoubleNode(obj);
DoubleNode p = head;
for (int j = 0; j < i; j++) {
p = p.next;
}
s.prior = p;
s.next = p.next;
if (p.next != null) {
// 避免添加第0个结点出现空指针
p.next.prior = s;
}
p.next = s;
size++;
return true;
}
/**
* 删除指定位置的元素
*
* @param i
* @return
*/
public DoubleNode remove(int i) {
if (i < 0 || i > size - 1) {
System.out.println("删除位置不正确");
return null;
}
DoubleNode p = head;
for (int j = 0; j <= i; j++) {
p = p.next;
}
if (p == null) {
// 没找到
return null;
} else {
// 找到了
p.prior.next = p.next;
if (p.next != null) {
// 避免删除最后一个结点出现空指针
p.next.prior = p.prior;
}
size--;
return p;
}
}
public static void main(String[] args) {
DoubleLinkList list = new DoubleLinkList();
list.insert(new Integer(0), 0);
list.insert(new Integer(1), 1);
list.insert(new Integer(2), 2);
list.insert(new Integer(3), 3);
list.show();
System.out.println(list.remove(3));
list.show();
}
}
class DoubleNode {
Object data;
// 直接前驱指针
DoubleNode prior;
// 直接后继指针
DoubleNode next;
public DoubleNode() {
}
public DoubleNode(Object obj) {
data = obj;
}
@Override
public String toString() {
return data.toString();
}
}
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
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
上次更新: 2023/11/01, 03:11:44