在單鏈表分析中，我們可以知道每個結點只有一個指向后繼結點的next域，倘若此時已知當前結點p，需要查找其前驅結點，那么就必須從head頭指針遍歷至p的前驅結點，操作的效率很低，因此如果p有一個指向前驅結點的next域，那效率就高多了，對于這種一個結點中分別包含了前驅結點域pre和后繼結點域next的鏈表，稱之為雙鏈表。本篇我們將從以下結點來分析雙鏈表
雙鏈表的設計與實現
雙鏈表的主要優點是對于任意給的結點，都可以很輕易的獲取其前驅結點或者后繼結點，而主要缺點是每個結點需要添加額外的next域，因此需要更多的空間開銷，同時結點的插入與刪除操作也將更加耗時，因為需要更多的指針指向操作。雙鏈表的結構圖如下：
創建headdoubleilinkedlist類并實現ilinekedlist接口(和上篇博文的接口一樣)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
/** * created by zejian on 2016/10/23. * 雙鏈表的實現,帶頭結點(不帶數據)的雙鏈表,為了更高的效率該類包含指向尾部的指針tail */public class headdoubleilinkedlist<t> implements ilinkedlist<t> { protected dnode<t> head; //不帶數據的頭結點 protected dnode<t> tail; //指向尾部的指針 public headdoubleilinkedlist(){ //初始化頭結點 this.head =this.tail= new dnode<>(); } //先省略其他代碼 ........} |
結點類結構如下：
|
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
|
package com.zejian.structures.linkedlist.doublelinked;/** * created by zejian on 2016/10/23. * 雙鏈表結點 */public class dnode<t> { public t data; public dnode<t> prev, next;//前繼指針和后繼指針 public dnode(t data, dnode<t> prev, dnode<t> next) { this.data = data; this.prev = prev; this.next = next; } public dnode(t data) { this(data, null, null); } public dnode() { this(null, null, null); } public string tostring() { return this.data.tostring(); }} |
通過上篇的分析，我們對鏈表的插入、刪除、查找、替換等操作也比較熟悉了，因此針對雙鏈表的實現，主要分析其插入、刪除、查找、替換等方法，其他沒有分析的看實現源碼即可（最后會給出雙鏈表的實現代碼）
雙鏈表的插入操作分析與實現
我們先來看看雙鏈表的插入，雖然有不帶數據的頭結點，但是由于是雙向鏈表，所以在插入雙鏈表時需分兩種情況，一種是在插入空雙鏈表和尾部插入，另一種是雙鏈表的中間插入，如下圖在空雙鏈表插入值x：
從圖可以看出（a）和（b）屬于同種情況，需要注意front.next != null的情況，否則就會拋空指針，而（c）的情況屬于中間插入無需無需理會front.next != null的條件，因為中間插入時無論如何其后繼結點時不會為null的，插入方法的實現代碼如下：
|
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
|
/** * 插入結點 * @param index * @param data * @return */@overridepublic boolean add(int index, t data) { if(index<0||data==null) throw new nullpointerexception("index < 0 || data == null"); int j = 0; dnode<t> front = this.head; //查找要插入結點位置的前一個結點 while (front.next != null && j < index) { j++; front = front.next; } //創建需要插入的結點,并讓其前繼指針指向front,后繼指針指向front.next dnode<t> q = new dnode<t>(data, front, front.next); //空雙鏈表插入和尾部插入，無需此操作 if(front.next != null) { //更改front.next的前繼指針 front.next.prev = q; } //更改front的后繼指針 front.next = q; //在尾部插入時需要注意更新tail指向 if(front==this.tail){ this.tail=q; } return true;} |
雙鏈表的刪除操作分析與實現
雙鏈表的刪除操作與插入操作原理上是相似的，我們可以看出（a）（b）是屬于同種情況，需要防止 p.next.prev拋空指針的情況，而對于（c）情況則無需關系 p.next.prev的值，刪除的具體實現如下：
|
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
|
/** * 根據下標刪除結點 * 1.頭刪除 * 2.中間刪除 * 3.尾部刪除,更新tail指向 * @param index 下標起始值為0 * @return */ @override public t remove(int index) { int size=length(); t temp=null; if(index<0||index>=size||isempty()){ return temp; } dnode<t> p=this.head; int j=0; //頭刪除/尾刪除/中間刪除,查找需要刪除的結點(要刪除的當前結點因此i<=index) while (p!=null&&j<=index){ p=p.next; j++; } //當雙鏈表只有一個結點時或尾部刪除時,無需此步 if(p.next!=null){ p.next.prev=p.prev; } p.prev.next=p.next; //如果是尾結點 if (p==this.tail) { this.tail = p.prev;//更新未結點的指向 } temp=p.data; return temp; } |
雙鏈表的查值操作分析與實現
雙鏈表的查找值的操作與單鏈表并沒有什么區別，只要找到需要查找的當前結點獲取其值即可，如下：
代碼實現如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
@overridepublic t get(int index) { if (index>=0) { int j=0; //注意起始結點為this.head.next //如果起始點為this.head時，j的判斷為j<=index， //因為需要尋找的是當前結點而不是前一個結點。 dnode<t> pre=this.head.next; while (pre!=null && j<index) { j++; pre=pre.next; } if (pre!=null) return pre.data; } return null;} |
雙鏈表的替換值操作分析與實現
雙鏈表的替換值過程，需要先查找到需要替換的結點，這個過程跟獲取值的過程是一樣的，找到結點后直接替換值并返回舊值即可。比較簡單直接上代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
@overridepublic t set(int index, t data) { t old=null; if (index>0&&data!=null){ int j=0; dnode<t> pre =this.head.next; //查找需要替換的位置 while (pre!=null&&j<index){ j++; pre=pre.next; } if (pre!=null){ old=pre.data; //替換數據 pre.data=data; } } return old;} |
ok~，到此雙鏈表的主要操作實現已分析完，下面給出雙鏈表的實現源碼：
|
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
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
|
package com.zejian.structures.linkedlist.doublelinked;import com.zejian.structures.linkedlist.ilinkedlist;/*** created by zejian on 2016/10/23.* 雙鏈表的實現,帶頭結點(不帶數據)的雙鏈表,為了更高的效率該類包含指向尾部的指針tail*/public class headdoubleilinkedlist<t> implements ilinkedlist<t> { protected dnode<t> head; //不帶數據的頭結點 protected dnode<t> tail; //指向尾部的指針 public headdoubleilinkedlist(){ this.head =this.tail= new dnode<>(); //初始化頭結點 } /** * 傳入一個數組,轉換成鏈表 * @param array */ public headdoubleilinkedlist(t[] array) { this(); if (array!=null && array.length>0) { this.head.next = new dnode<t>(array[0]); tail =this.head.next; tail.prev=this.head; int i=1; while (i<array.length) { tail.next=new dnode<t>(array[i++]); tail.next.prev=tail; tail = tail.next; } } } @override public boolean isempty() { return head.next==null; } @override public int length() { int length=0; dnode<t> pre=head.next; while (pre!=null){ length++; pre=pre.next; } return length; } @override public t get(int index) { if (index>=0) { int j=0; dnode<t> pre=this.head.next; while (pre!=null && j<index) { j++; pre=pre.next; } if (pre!=null) return pre.data; } return null; } @override public t set(int index, t data) { t old=null; if (index>0&&data!=null){ int j=0; dnode<t> pre =this.head.next; //查找需要替換的位置 while (pre!=null&&j<index){ j++; pre=pre.next; } if (pre!=null){ old=pre.data; //替換數據 pre.data=data; } } return old; } /** * 插入結點 * @param index * @param data * @return */ @override public boolean add(int index, t data) { if(index<0||data==null) throw new nullpointerexception("index < 0 || data == null"); int j = 0; dnode<t> front = this.head; //查找要插入結點位置的前一個結點 while (front.next != null && j < index) { j++; front = front.next; } //創建需要插入的結點,并讓其前繼指針指向front,后繼指針指向front.next dnode<t> q = new dnode<t>(data, front, front.next); //空雙鏈表插入,需要確保front.next不為空 if(front.next != null) { //更改front.next的前繼指針 front.next.prev = q; } //更改front的后繼指針 front.next = q; //在尾部插入時需要注意更新tail指向 if(front==this.tail){ this.tail=q; } return true; } /** * 尾部添加 * @param data * @return */ @override public boolean add(t data) { if (data==null) return false; //創建新結點,并把其前繼指針指向tail dnode<t> q = new dnode<t>(data, tail, null); tail.next=q; //更新尾部結點 this.tail=q; return true; } /** * 根據下標刪除結點 * 1.頭刪除 * 2.中間刪除 * 3.尾部刪除,更新tail指向 * @param index 下標起始值為0 * @return */ @override public t remove(int index) { int size=length(); t temp=null; if(index<0||index>=size||isempty()){ return temp; } dnode<t> p=this.head; int j=0; //頭刪除/尾刪除/中間刪除,查找需要刪除的結點(要刪除的當前結點因此i<=index) while (p!=null&&j<=index){ p=p.next; j++; } //當鏈表只要一個結點時,無需此步 if(p.next!=null){ p.next.prev=p.prev; } p.prev.next=p.next; //如果是尾結點 if (p==this.tail) { this.tail = p.prev;//更新未結點的指向 } temp=p.data; return temp; } /** * 根據data刪除結點,無需像單向鏈表那樣去存儲要刪除結點的前一個結點 * 1.頭刪除 * 2.中間刪除 * 3.尾部刪除,更新tail指向 * @param data * @return */ @override public boolean removeall(t data) { boolean isremove=false; if(data==null||isempty()) return isremove; //注意這里的起點,如果起點為this.head,那么情況區別如同前面的根據index的刪除實現 dnode<t> p=this.head.next; //頭刪除/尾刪除/中間刪除(size>1),查找所有需要刪除的結點 while (p!=null){ if(data.equals(p.data)){ if (p==this.tail){ //如果是尾結點 this.tail=p.prev;//更新未結點的指向 p.prev=null; this.tail.next=null; }else { //如果是在中間刪除,更新前繼和后繼指針指向 p.prev.next=p.next; p.next.prev=p.prev; } isremove=true; p=p.next;//繼續查找 }else { p=p.next; } } return isremove; } /** * 清空鏈表 */ @override public void clear() { this.head.next=null; this.tail=this.head; } @override public boolean contains(t data) { if(data==null){ return false; } dnode<t> p=this.head.next; while (p!=null){ if (data.equals(p.data)){ return true; }else { p=p.next; } } return false; } @override public string tostring() { string str="("; dnode<t> pre = this.head.next; while (pre!=null) { str += pre.data; pre = pre.next; if (pre!=null) str += ", "; } return str+")"; } public static void main(string[] args){ string[] letters={"a","b","c","d","z","e","f"};// string[] letters={"a"}; headdoubleilinkedlist<string> list=new headdoubleilinkedlist<>(letters); system.out.println("list.get(3)->"+list.get(3)); system.out.println("list:"+list.tostring()); system.out.println("list.add(4,y)—>"+list.add(0,"y")); system.out.println("list:"+list.tostring()); system.out.println("list.add(z)—>"+list.add("z")); system.out.println("list:"+list.tostring()); system.out.println("list.contains(z)->"+list.contains("z")); system.out.println("list.set(4,p)-->"+list.set(4,"p")); system.out.println("list:"+list.tostring()); system.out.println("list.remove(6)-->"+list.remove(6));// system.out.println("list.remove(z)->"+list.removeall("z")); system.out.println("list:"+list.tostring()); }} |
循環雙鏈表的設計與實現
如果雙鏈表的最后一個結點的next指針域指向頭結點，而頭結點的prev指針指向頭最后一個結點，則構成了雙鏈表（circular doubly linkedlist），其結構如下圖示：
在循環雙鏈表中我們不再需要尾指向結點，因為整個鏈表已構成循環，在頭結點head的位置也可以輕松獲取到尾部結點的位置。對于循環雙鏈表的插入、刪除操作也無需區分位置操作的情況，這是由于循環雙鏈表的本身的特殊性，使p.next.pre永遠不可能為null，因此我們在插入和刪除時代碼實現相對簡單些。下面我們先分析一下循環雙鏈表的插入操作，圖示如下：
我們可以看出（a）（b）（c）三種情況都無需關系位置插入的區別，其代碼實現如下：
|
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
|
/** * 根據index插入 * 循環鏈表中無論是prev還是next都不存在空的情況,因此添加時 * 無論是頭部還是尾部還是中,都視為一種情況對待 * @param index * @param data * @return */@overridepublic boolean add(int index, t data) { int size=length(); if(data==null||index<0||index>=size) return false; int j=0; dnode<t> p=this.head; //尋找插入點的位置 while (p.next!=head&&j<index){ p=p.next; j++; } //創建新結點,如果index=3,那么插入的位置就是第4個位置 dnode<t> q=new dnode<>(data,p,p.next); p.next=q; p.next.prev=q; return true;} |
循環雙鏈表的刪除操作圖示如下：
雙鏈表的刪除操作圖示
同樣地，從圖中我們也可以發現由于循環雙鏈表的特性，（a）（b）（c）三種情況都無需區分操作位置，其代碼實現如下：
|
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
|
@overridepublic t remove(int index) { t old = null; int size=length(); if (index<0||index>=size) return old; int j=0; dnode<t> p=this.head.next; while (p!=head && j<index) { j++; p = p.next; } if (p!=head) { old = p.data; p.prev.next = p.next; p.next.prev = p.prev; } return old;} |
至于循環雙鏈表的查找值、替換值等操作與雙鏈表并沒有多大的區別，但是需要特別注意的是在遍歷循環雙鏈表時，結束標志不再是尾部結點是否為空，而是尾結點的next指針是否指向頭結點head。好~，下面我們給出循環雙鏈表的實現代碼：
|
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
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
|
package com.zejian.structures.linkedlist.doublelinked;import com.zejian.structures.linkedlist.ilinkedlist;/*** created by zejian on 2016/10/24.* 循環雙鏈表,帶空頭結點(不含數據),循環鏈表可以不需要尾部指針*/public class loopheaddilinkedlist<t> implements ilinkedlist<t> { protected dnode<t> head; //不帶數據的頭結點// protected dnode<t> tail; //指向尾部的指針 public loopheaddilinkedlist(){ this.head = new dnode<>();//初始化頭結點 this.head.next=head; this.head.prev=head; } /** * 傳入一個數組,轉換成鏈表 * @param array */ public loopheaddilinkedlist(t[] array) { this(); if (array!=null && array.length>0) { dnode<t> p= new dnode<>(array[0]); head.next=p; head.prev=p; p.prev=head; p.next=head; int i=1; while (i<array.length) { p.next=new dnode<>(array[i++],p,head); head.prev=p.next; p=p.next; } } } @override public boolean isempty() { return this.head.next==head;//循環雙鏈表的后繼指針指向自己說明是空鏈表 } @override public int length() { int length=0; dnode<t> p=this.head.next; while (p!=this.head){ length++; p=p.next; } return length; } @override public t get(int index) { if (index>=0) { int j=0; dnode<t> p=this.head.next; while (p!=head && j<index) { j++; p=p.next; } if (p!=head) return p.data; } return null; } /** * 根據index修改data * @param index * @param data * @return 返回被替換的data */ @override public t set(int index, t data) { if (data==null){ return null; } if(index>=0){ int j=0; dnode<t> p=this.head.next; while (p!=head&&j<index){ j++; p=p.next; } //如果不是頭結點 if(p!=head){ t old = p.data; p.data=data; return old; } } return null; } /** * 根據index添加 * 循環鏈表中無論是prev還是next都不存在空的情況,因此添加時 * 無論是頭部還是尾部還是中,都視為一種情況對待 * @param index * @param data * @return */ @override public boolean add(int index, t data) { int size=length(); if(data==null||index<0||index>=size) return false; int j=0; dnode<t> p=this.head; //尋找插入點的位置 while (p.next!=head&&j<index){ p=p.next; j++; } //創建新結點,如果index=3,那么插入的位置就是第4個位置 dnode<t> q=new dnode<>(data,p,p.next); p.next=q; p.next.prev=q; return true; } /** * 尾部添加 * @param data * @return */ @override public boolean add(t data) { if(data==null) return false; //創建新結點,讓前繼指針指向head.pre,后繼指針指向head dnode<t> p=new dnode<>(data,head.prev,head); //更新tail后繼指針的指向 this.head.prev.next=p; this.head.prev=p; return true; } @override public t remove(int index) { t old = null; int size=length(); if (index<0||index>=size) return old; int j=0; dnode<t> p=this.head.next; while (p!=head && j<index) { j++; p = p.next; } if (p!=head) { old = p.data; p.prev.next = p.next; p.next.prev = p.prev; } return old; } @override public boolean removeall(t data) { boolean isremove=false; if(data==null){ return isremove; } dnode<t> p=this.head.next; while (p!=head){ if(data.equals(p.data)){ p.prev.next=p.next; p.next.prev=p.prev; isremove=true; } p=p.next; } return isremove; } @override public void clear() { this.head.prev = head; this.head.next = head; } @override public boolean contains(t data) { if (data==null){ return false; } dnode<t> p=this.head.next; while (p!=head){ if(data.equals(p.data)){ return false; } p=p.next; } return false; } @override public string tostring() { string str="("; dnode<t> p = this.head.next; while (p!=head) { str += p.data.tostring(); p = p.next; if (p!=head) str += ", "; } return str+")"; } public static void main(string[] args){ string[] letters={"a","b","c","d","z","e","f"}; loopheaddilinkedlist<string> list=new loopheaddilinkedlist<>(letters); system.out.println("init list-->"+list.tostring()); system.out.println("list.get(3)->"+list.get(3)); system.out.println("list:"+list.tostring()); system.out.println("list.add(4,y)—>"+list.add(4,"y")); system.out.println("list:"+list.tostring()); system.out.println("list.add(z)—>"+list.add("z")); system.out.println("list:"+list.tostring()); system.out.println("list.contains(z)->"+list.contains("z")); system.out.println("list.set(4,p)-->"+list.set(4,"p")); system.out.println("list:"+list.tostring()); system.out.println("list.remove(3)-->"+list.remove(3)); system.out.println("list.remove(z)->"+list.removeall("z")); system.out.println("list:"+list.tostring()); }} |
排序循環雙鏈表的實現
所謂的排序循環雙鏈表指的是在插入元素時，不再根據index標志，而是根據值的大小尋找插入位置，但是有個插入值data必須是t或者t的父類而且實現了comoarable接口。排序循環雙鏈表的實現比較簡單，我們只需繼承前面的循環雙鏈表并重寫add方法即可，主要代碼實現如下：
|
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
|
package com.zejian.structures.linkedlist.doublelinked;/*** created by zejian on 2016/11/6.* 升序排序鏈表，繼承loopheaddilinkedlist*/public class sortloopheaddilinkedlist<t extends comparable<? extends t>> extends loopheaddilinkedlist<t> { /** * 順序插入 * @param data * @return */ @override public boolean add(t data) { if(data==null||!(data instanceof comparable)) throw new nullpointerexception("data can\'t be null or data instanceof comparable must be true"); comparable cmp =data;//這里需要轉一下類型,否則idea編輯器上檢驗不通過. //如果data值比最后一個結點大,那么直接調用父類方法,在尾部添加. if(this.isempty() || cmp.compareto(this.head.prev.data) > 0){ return super.add(data); } dnode<t> p=this.head.next; //查找插入點 while (p!=head&&cmp.compareto(p.data)>0) p=p.next; dnode<t> q=new dnode<>(data,p.prev,p); p.prev.next=q; p.prev=q; return true; } public static void main(string[] args){ sortloopheaddilinkedlist<integer> list=new sortloopheaddilinkedlist<>(); list.add(50); list.add(40); list.add(80); list.add(20); system.out.println("init list-->"+list.tostring()); }} |
雙鏈表的執行效率分析
其實上一篇已分析得差不多了，這里再簡單說明一下，鏈表在插入和刪除元素時執行效率比較高，從插入操作來看，我們假設front指向的是雙向鏈表中的一個結點，此時插入front的后繼結點或者是前驅結點所消耗的時間為常數時間o(1),這點在插入front的前驅結點的效率比單鏈表有所改善，無需從頭結點開始遍歷，但是上述都是從已知雙向鏈表中front結點的情況下討論的。如果從實現代碼的操作上看，無論是插入還是刪除，都需要查找插入結點或刪除結點，而這個過程訪問結點所花費的時間的是o(n)，因此雙鏈表的插入或刪除操作或是查值操作，其時間復雜度都為o(n),至于為什么說鏈表更適合插入刪除，這點上一篇我們已討論過，這里就不重復了。最后給出一張關于鏈表、數組、動態數組的比較表：
| 傳遞參數 | 鏈表 | 動態數組 |
|---|---|---|
| 索引 | o(n) | o(1) |
| 在最前端插入或刪除 | o(1) | o(n) |
| 在最末端插入 | o(n) | o(1),如果數組空間沒有被填滿;o(n),如果數組空間已填滿 |
| 在最末端刪除 | o(n) | o(1) |
| 在中間插入 | o(n) | o(n) |
| 在中間刪除 | o(n) | o(n) |
| 空間浪費 | o(n) | o(n) |
異或高效存儲雙鏈表的設計原理概要
在上述分析的雙鏈表的實現中，都是需要一個指向后繼結點的正向指針和一個指向前驅結點的反向指針，出于此點的考慮，我們需要在構造一個結點類時需要一個數據域data、一個指向后繼結點的指針next以及一個指向前驅結點的指針prev。但為了設計更高效節省存儲空間，一種基于指針差運算存儲高效的雙向鏈表就誕生了。這種鏈表的每個結點仍然與單鏈表一樣僅使用一個指針域來設計雙向鏈表，新的雙向鏈表結點類結構如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
package com.zejian.structures.linkedlist.xorlinked;/** * created by zejian on 2016/11/6. * 異或結點 */public class xornode<t> { public t data; public xornode<t> ptrdiff;//異或指針 public xornode() { } public xornode(t data, xornode<t> ptrdiff) { this.data = data; this.ptrdiff = ptrdiff; }} |
其中的ptrdiff字段存儲了后繼結點與前驅結點的地址差，指針的差通過異或運行（對異或不熟悉的可以看博主的另一篇文章：java運算符）來實現的，我們這里使用⊕表示異或操作，則有如下計算：
pridiff=后繼結點的地址⊕前驅結點的地址
如上圖，我們采用異或差值來計算各個結點的位置：
- a的next域為head⊕b
- b的next域為a⊕c
- c的next域為b⊕d
- d的next域為c⊕null
那么為什么可以這么計算呢？我們先來了解一下異或的特性：
- x⊕x=0
- x⊕0=x
- x⊕y=y⊕x
- (x⊕y)⊕z=x⊕(y⊕z)
所以我們可以很容易利用上述的異或特性找到結點的對象，比如指向p想從結點c移動到結點b，已知c的ptrdiff值為b⊕d,那么就需要將結點c的ptrdiff的值與結點d的地址執行異或運算，這時就可以得到b的地址了，計算過程如下：
|
1
|
(b ⊕ d) ⊕ d = b ⊕(d ⊕ d) = b ⊕ 0 =b |
如果想從c結點移動到d結點，那么此時的計算如下：
|
1
|
(b ⊕ d) ⊕ b = d ⊕(b ⊕ b) =b ⊕ 0 = d |
因此在確實可以通過一個next的指針域來實現雙向鏈表的移動，而且這種存儲高效的雙向鏈表還可以節省空間開銷。實際上，存儲高效的雙鏈表介紹來自《數據結構與算法經典問題分析》一書，不過博主發現，這種存儲高效的鏈表，使用c語言比較容易實現，因為c語言可以通過指針(地址)獲取到對象直接操作，但在java語言中，博主并沒有想到如何實現這種存儲高效的鏈表，至少目前還沒想到可行的方案，google了一把實現語言都是c，沒找到java的實現，不過博主想來想去都感覺這種存儲高效的鏈表不太適合java來實現（僅個人觀點），若有實現方案的還望留言告知，感謝呢。不過這樣算法設計思想方式還是蠻有不錯的。ok~，關于雙向鏈表，我們暫且聊到這里。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://blog.csdn.net/javazejian/article/details/53047590
