本文实例讲述了C#数据结构之双向链表(DbLinkList)。分享给大家供大家参考，具体如下：
这是继上一篇《C#数据结构之单链表(LinkList)实例详解》的继续，对于双向链接，节点上除了Next属性外，还要有Prev属性用来指向前一个节点，DbNode定义如下：
|
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
|
namespace 线性表
{
public class DbNode<T>
{
private T data;
private DbNode<T> prev;
private DbNode<T> next;
public DbNode(T data, DbNode<T> next,DbNode<T> prev)
{
this.data = data;
this.next = next;
this.prev = prev;
}
public DbNode(T data, DbNode<T> next)
{
this.data = data;
this.next = next;
this.prev = null;
}
public DbNode(DbNode<T> next)
{
this.data = default(T);
this.next = next;
this.prev = null;
}
public DbNode(T data)
{
this.data = data;
this.next = null;
this.prev = null;
}
public DbNode()
{
data = default(T);
next = null;
prev = null;
}
public T Data
{
set { this.data = value; }
get { return this.data; }
}
public DbNode<T> Prev
{
get { return prev; }
set { prev = value; }
}
public DbNode<T> Next
{
get { return next; }
set { next = value; }
}
}
}
|
双链表的插入操作要稍微复杂一点，示意图如下：
同样对于删除操作，也要额外处理prev指向
完整实现DbLinkList<T>：
|
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
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
|
using System;
using System.Text;
namespace 线性表
{
public class DbLinkList<T> : IListDS<T>
{
private DbNode<T> head;
public DbNode<T> Head
{
get { return head; }
set { head = value; }
}
public DbLinkList()
{
head = null;
}
/// <summary>
/// 类索引器
/// </summary>
/// <param name="index"></param>
/// <returns></returns>
public T this[int index]
{
get
{
return this.GetItemAt(index);
}
}
/// <summary>
/// 返回单链表的长度
/// </summary>
/// <returns></returns>
public int Count()
{
DbNode<T> p = head;
int len = 0;
while (p != null)
{
len++;
p = p.Next;
}
return len;
}
/// <summary>
/// 清空
/// </summary>
public void Clear()
{
head = null;
}
/// <summary>
/// 是否为空
/// </summary>
/// <returns></returns>
public bool IsEmpty()
{
return head == null;
}
/// <summary>
/// 在最后附加元素
/// </summary>
/// <param name="item"></param>
public void Append(T item)
{
DbNode<T> d = new DbNode<T>(item);
DbNode<T> n = new DbNode<T>();
if (head == null)
{
head = d;
return;
}
n = head;
while (n.Next != null)
{
n = n.Next;
}
n.Next = d;
d.Prev = n;
}
//前插
public void InsertBefore(T item, int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
//在最开头插入
if (i == 0)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = head;//把"头"改成第二个元素
head.Prev = q;
head = q;//把自己设置为"头"
return;
}
DbNode<T> n = head;
DbNode<T> d = new DbNode<T>();
int j = 0;
//找到位置i的前一个元素d
while (n.Next != null && j < i)
{
d = n;
n = n.Next;
j++;
}
if (n.Next == null) //说明是在最后节点插入(即追加)
{
DbNode<T> q = new DbNode<T>(item);
n.Next = q;
q.Prev = n;
q.Next = null;
}
else
{
if (j == i)
{
DbNode<T> q = new DbNode<T>(item);
d.Next = q;
q.Prev = d;
q.Next = n;
n.Prev = q;
}
}
}
/// <summary>
/// 在位置i后插入元素item
/// </summary>
/// <param name="item"></param>
/// <param name="i"></param>
public void InsertAfter(T item, int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("List is empty or Position is error!");
return;
}
if (i == 0)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = head.Next;
head.Next.Prev = q;
head.Next = q;
q.Prev = head;
return;
}
DbNode<T> p = head;
int j = 0;
while (p != null && j < i)
{
p = p.Next;
j++;
}
if (j == i)
{
DbNode<T> q = new DbNode<T>(item);
q.Next = p.Next;
if (p.Next != null)
{
p.Next.Prev = q;
}
p.Next = q;
q.Prev = p;
}
else {
Console.WriteLine("Position is error!");
}
}
/// <summary>
/// 删除位置i的元素
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T RemoveAt(int i)
{
if (IsEmpty() || i < 0)
{
Console.WriteLine("Link is empty or Position is error!");
return default(T);
}
DbNode<T> q = new DbNode<T>();
if (i == 0)
{
q = head;
head = head.Next;
head.Prev = null;
return q.Data;
}
DbNode<T> p = head;
int j = 0;
while (p.Next != null && j < i)
{
j++;
q = p;
p = p.Next;
}
if (j == i)
{
p.Next.Prev = q;
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("The node is not exist!");
return default(T);
}
}
/// <summary>
/// 获取指定位置的元素
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public T GetItemAt(int i)
{
if (IsEmpty())
{
Console.WriteLine("List is empty!");
return default(T);
}
DbNode<T> p = new DbNode<T>();
p = head;
if (i == 0)
{
return p.Data;
}
int j = 0;
while (p.Next != null && j < i)
{
j++;
p = p.Next;
}
if (j == i)
{
return p.Data;
}
else
{
Console.WriteLine("The node is not exist!");
return default(T);
}
}
//按元素值查找索引
public int IndexOf(T value)
{
if (IsEmpty())
{
Console.WriteLine("List is Empty!");
return -1;
}
DbNode<T> p = new DbNode<T>();
p = head;
int i = 0;
while (!p.Data.Equals(value) && p.Next != null)
{
p = p.Next;
i++;
}
return i;
}
/// <summary>
/// 元素反转
/// </summary>
public void Reverse()
{
DbLinkList<T> result = new DbLinkList<T>();
DbNode<T> t = this.head;
result.Head = new DbNode<T>(t.Data);
t = t.Next;
//(把当前链接的元素从head开始遍历，逐个插入到另一个空链表中，这样得到的新链表正好元素顺序跟原链表是相反的)
while (t!=null)
{
result.InsertBefore(t.Data, 0);
t = t.Next;
}
this.head = result.head;//将原链表直接挂到"反转后的链表"上
result = null;//显式清空原链表的引用，以便让GC能直接回收
}
//得到某个指定的节点(为了下面测试从后向前遍历)
private DbNode<T> GetNodeAt(int i){
if (IsEmpty())
{
Console.WriteLine("List is empty!");
return null;
}
DbNode<T> p = new DbNode<T>();
p = head;
if (i == 0)
{
return p;
}
int j = 0;
while (p.Next != null && j < i)
{
j++;
p = p.Next;
}
if (j == i)
{
return p;
}
else
{
Console.WriteLine("The node is not exist!");
return null;
}
}
/// <summary>
/// 测试用prev属性从后面开始遍历
/// </summary>
/// <returns></returns>
public string TestPrevErgodic()
{
DbNode<T> tail = GetNodeAt(Count() - 1);
StringBuilder sb = new StringBuilder();
sb.Append(tail.Data.ToString() + ",");
while (tail.Prev != null)
{
sb.Append(tail.Prev.Data.ToString() + ",");
tail = tail.Prev;
}
return sb.ToString().TrimEnd(',');
}
public override string ToString()
{
StringBuilder sb = new StringBuilder();
DbNode<T> n = this.head;
sb.Append(n.Data.ToString() + ",");
while (n.Next != null)
{
sb.Append(n.Next.Data.ToString() + ",");
n = n.Next;
}
return sb.ToString().TrimEnd(',');
}
}
}
|
测试代码片段：
|
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
|
Console.WriteLine("-------------------------------------");
Console.WriteLine("双链表测试开始...");
DbLinkList<string> dblink = new DbLinkList<string>();
dblink.Head = new DbNode<string>("x");
dblink.InsertBefore("w", 0);
dblink.InsertBefore("v", 0);
dblink.Append("y");
dblink.InsertBefore("z", dblink.Count());
Console.WriteLine(dblink.Count());//5
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink[1]);//w
Console.WriteLine(dblink[0]);//v
Console.WriteLine(dblink[4]);//z
Console.WriteLine(dblink.IndexOf("z"));//4
Console.WriteLine(dblink.RemoveAt(2));//x
Console.WriteLine(dblink.ToString());//v,w,y,z
dblink.InsertBefore("x", 2);
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink.GetItemAt(2));//x
dblink.Reverse();
Console.WriteLine(dblink.ToString());//z,y,x,w,v
dblink.InsertAfter("1", 0);
dblink.InsertAfter("2", 1);
dblink.InsertAfter("6", 5);
dblink.InsertAfter("8", 7);
dblink.InsertAfter("A", 10);//Position is error!
Console.WriteLine(dblink.ToString()); //z,1,2,y,x,w,6,v,8
string _tail = dblink.GetItemAt(dblink.Count()-1);
Console.WriteLine(_tail);
Console.WriteLine(dblink.TestPrevErgodic());//8
Console.ReadKey(); //8,v,6,w,x,y,2,1,z
|
当然从上面的测试代码中，似乎并不能看出双链表的优点，双链表的好处在于，如果需要在链表中，需要通过某个节点得到它的前驱节点时，双链表直接用prev属性就能找到；而单链表要做到这一点，必须再次从Head节点开始一个一个用Next向下找，这样时间复杂度从O(n)降到O(1)，显然更有效率。
注：如果把双链表再做一下改造，让头尾接起来，即Head的Prev属性指向最后一个节点(就叫做Tail吧)，同时把Tail节点的Next属性指向Head节点，就形成了所谓的“循环双向链表”
当然，这样的结构可以在链表中再增加一个Tail节点属性，在做元素插入或删除时，可以循环到底以更新尾节点Tail(当然这样会给插入/删除元素带来一些额外的开销)，但是却可以给GetItemAt(int i)方法带来优化的空间，比如要查找的元素在前半段时，可以从Head开始用next向后找；反之，如果要找的元素在后半段，则可以从Tail节点用prev属性向前找。
注：.Net中微软已经给出了一个内置的双向链表System.Collections.Generic.LinkedList<T>，在了解双链表的原理后，建议大家直接系统内置的链表。
希望本文所述对大家C#程序设计有所帮助。