双向链表的实现

双向链表的优点是可以找到前一个节点位置
缺点是每个节点占用的空间大了并且插入和删除需要修改四个指针
代码实现:

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
package com.example.chapter1;

/**
* Created by toto on 17/3/8.
*/
/*双向列表
双向列表里面有两个节点,分表表示头节点和尾节点,可以理解为它们是头节点和尾节点的Copy
插入头最后替换mFristLinked 插入尾替换mLastLined
*/
public class DoubleLinked {
BothWayLink mFirstLinked = null;
BothWayLink mLastLinked = null;

boolean isEmpty() {
if (mFirstLinked == null) {
return true;
}
return false;
}

//在链表的头插入
BothWayLink insertFirst(long insertLinked) {
BothWayLink mNewLink = new BothWayLink(insertLinked);
if (mLastLinked == null) {
mLastLinked = mNewLink;
} else {
mFirstLinked.previous = mNewLink;

}
mNewLink.next = mFirstLinked;
mFirstLinked = mNewLink;
return mNewLink;
}

//在链表末尾插入
BothWayLink insertLast(long insertLinked) {
BothWayLink mNewLink = new BothWayLink(insertLinked);
if (mFirstLinked == null) {
mFirstLinked = mNewLink;
} else {
mLastLinked.next = mNewLink;
mNewLink.previous = mLastLinked;
}
mLastLinked = mNewLink;
return mNewLink;
}

//删除第一个
BothWayLink deleteFirst() {
BothWayLink tmp;
if (isEmpty()) {
return null;
}
tmp = mFirstLinked;
mFirstLinked = mFirstLinked.next;
mFirstLinked.previous = null;
if (mLastLinked.previous == null) {
mLastLinked = null;
}
return tmp;
}

//删除最后一个
BothWayLink deleteLast() {
BothWayLink tmp;
if (isEmpty()) {
return null;
}
tmp = mLastLinked;
if (mFirstLinked.next == null) {
mFirstLinked = null;
} else {
mLastLinked.previous.next = null;
}
mLastLinked = mLastLinked.previous;
return tmp;
}

//在节点之后删除
void insertAfter(long key, long data) {
if (isEmpty()) {
return;
}
BothWayLink tempLink = mFirstLinked;
while (tempLink != null && tempLink.mData != key) {
tempLink = tempLink.next;
}
if (tempLink == null) {
return;
}
BothWayLink newLink = new BothWayLink(data);
if (tempLink == mLastLinked) {
mLastLinked = newLink;
} else {
tempLink.next.previous = newLink;
newLink.next = tempLink.next;

}
tempLink.next = newLink;
newLink.previous = tempLink;

}

//删除指定的节点
void deleteKey(long key) {
if (isEmpty()) {
return;
}
BothWayLink currentLink = mFirstLinked;
while (currentLink != null && currentLink.mData != key) {
currentLink = currentLink.next;
}
if (currentLink == null) {
return;
}
if (currentLink == mFirstLinked) {
mFirstLinked = currentLink.next;
currentLink.next.previous = null;
} else if (currentLink == mLastLinked) {
mLastLinked = currentLink.previous;
currentLink.previous.next = null;
} else {
currentLink.previous.next = currentLink.next;
currentLink.next.previous = currentLink.previous;
}
}

//显示节点
void display() {
if (isEmpty()) {
return;
}
BothWayLink mCurrentLink = mFirstLinked;
while (mCurrentLink != null) {
mCurrentLink.showLink();
mCurrentLink = mCurrentLink.next;
}
}
}

class DoubleLinedApp {
public static void main(String[] args) {
DoubleLinked doubleLinked = new DoubleLinked();
doubleLinked.insertFirst(22);
doubleLinked.insertFirst(44);
doubleLinked.insertFirst(66);

doubleLinked.insertLast(11);
doubleLinked.insertLast(33);
doubleLinked.insertLast(55);

doubleLinked.display();
System.out.println("-----------------");

doubleLinked.deleteFirst();
doubleLinked.deleteLast();
doubleLinked.deleteKey(11);

doubleLinked.display();
System.out.println("-----------------");
doubleLinked.insertAfter(22, 77);
doubleLinked.insertAfter(33, 88);

doubleLinked.display();

}
}
谢谢您的鼓励~