-
c#数据结构之双向链表
理论基础：
在结点中设两个引用域，一个保存直接前驱结点的地址，叫prev，一个直接后继结点的地址，叫next，这样的链表就是双向链表(Doubly Linked List)。
双向链表的结点结构示意图如上，双向链表结点的定义与单链表的结点的定义很相似，因此，双向链表节点类的实现可以参考单链表的节点类。
C#实现：
1接口
引用线性表的接口IListDS<T>
2实现
（1）双向链表节点类，参考单链表的节点类
Code
[copy to clipboard]
CODE:
1 public class DBNode<T>
2 {
3 private T data; //数据域
4 private DBNode<T> next; //后继
5 private DBNode<T> prev; //前驱
6 public T Data
7 {
8 get { return data; }
9 set { data = value; }
10 }
11 public DBNode<T> Next
12 {
13 get { return next; }
14 set { next = value; }
15 }
16 public DBNode<T> Prev
17 {
18 get { return prev; }
19 set { prev = value; }
20 }
21 public DBNode()
22 {
23 data = default(T);
24 prev = null;
25 next = null;
26 }
27 public DBNode(T val)
28 {
29 data = val;
30 next = null;
31 prev = null;
32 }
33 }
(2) 双向链表操作类实现
注意：由于双向链表的结点有两个引用，所以，在双向链表中插入和删除结点比单链表要复杂。双向链表中结点的插入分为在结点之前插入和在结点之后插入，插入操作要对四个引用进行操作
同样，删除操作也需要多多注意，其他的操作和单链表类似,不再赘述.
Code
[copy to clipboard]
CODE:
1public class DBLinkList<T> : IListDS<T>
2 {
3 private DBNode<T> header;
4 public DBNode<T> Header
5 {
6 get
7 {
8 return header;
9 }
10 set
11 {
12 header = value;
13 }
14 }
15 public DBLinkList()
16 {
17 header = new DBNode<T>();
18 header.Next = null;
19 header.Prev = null;
20 }
21 /**//// <summary>
22 /// 获取长度
23 /// </summary>
24 /// <returns></returns>
25 public int GetLength()
26 {
27 DBNode<T> p = header;
28 int len = 0;
29 while (p != null)
30 {
31 ++len;
32 p = p.Next;
33 }
34 return len;
35 }
36 /**//// <summary>
37 /// 清空操作
38 /// </summary>
39 public void Clear()
40 {
41 header = null;
42 }
43 /**//// <summary>
44 /// 判断线性表是否为空
45 /// </summary>
46 /// <returns></returns>
47 public bool IsEmpty()
48 {
49 if (header.Data==null)
50 {
51 return true;
52 }
53 else
54 {
55 return false;
56 }
57 }
58 /**//// <summary>
59 /// 查找节点
60 /// </summary>
61 /// <param name="i"></param>
62 /// <returns></returns>
63 private DBNode<T> FindNode(int i)
64 {
65 if (IsEmpty())
66 {
67 Console.Write("list is empty");
68 return null;
69 }
70 if (i < 1)
71 {
72 Console.Write("Index is error");
73 return null;
74 }
75 DBNode<T> current = new DBNode<T>();
76 current = header;
77 int j = 1;
78 while (current.Next != null && j < i)
79 {
80 ++j;
81 current = current.Next;
82 }
83 return current;
84 }
85 /**//// <summary>
86 /// 插入操作,在第i个节点前面
87 /// </summary>
88 /// <param name="item"></param>
89 /// <param name="i"></param>
90 public void Insert(T item, int i)
91 {
92 DBNode<T> current = FindNode(i);
93 DBNode<T> newNode = new DBNode<T>(item);
94 if (current != null)
95 {
96 current.Prev.Next = newNode;
97 newNode.Next = current;
98 newNode.Prev = current.Prev;
99 current.Prev = newNode;
100 }
101 else
102 {
103 Console.Write("the node is not exist!");
104 }
105 }
106 /**//// <summary>
107 /// 插入操作,在第i个节点后面插入item
108 /// </summary>
109 /// <param name="item"></param>
110 /// <param name="i"></param>
111 public void InsertBack(T item, int i)
112 {
113 DBNode<T> current = FindNode(i);
114 DBNode<T> newNode = new DBNode<T>(item);
115 if (current != null)
116 {
117 current.Next.Prev = newNode;
118 newNode.Prev = current;
119 newNode.Next = current.Next;
120 current.Next = newNode;
121 }
122 else
123 {
124 Console.Write("the node is not exist!");
125 }
126 }
127 /**//// <summary>
128 /// 附加操作,线性表未满，将值为item的新元素添加到末尾
129 /// </summary>
130 /// <param name="item"></param>
131 public void Append(T item)
132 {
133 DBNode<T> newNode = new DBNode<T>(item);
134 DBNode<T> p = new DBNode<T>();
135 if (header == null)
136 {
137 header = newNode;
138 return;
139 }
140 p = header;
141
142 while (p.Next != null)
143 {
144 p = p.Next;
145 }
146 p.Next = newNode;
147 }
148
149 /**//// <summary>
150 /// 删除操作
151 /// </summary>
152 /// <param name="i"></param>
153 /// <returns></returns>
154 public T Delete(int i)
155 {
156 DBNode<T> current = FindNode(i);
157 if (current != null)
158 {
159 current.Prev.Next = current.Next;
160 current.Next.Prev = current.Prev;
161 current.Prev = null;
162 current.Next = null;
163 return current.Data;
164 }
165 else
166 {
167 Console.Write("the node is not exist!");
168 return default(T);
169 }
170 }
171 /**//// <summary>
172 /// 取表元
173 /// </summary>
174 /// <param name="i"></param>
175 /// <returns></returns>
176 public T GetElem(int i)
177 {
178 DBNode<T> current = FindNode(i);
179 if (current != null)
180 {
181 return current.Data;
182 }
183 else
184 {
185 Console.Write("the node is not exist!");
186 return default(T);
187 }
188 }
189
190 /**//// <summary>
191 /// 按值查找
192 /// </summary>
193 /// <param name="value"></param>
194 /// <returns>-1:链表或参数异常;0:节点不存在;1:值代表的位置</returns>
195 public int Locate(T value)
196 {
197 if (IsEmpty())
198 {
199 Console.Write("list is empty");
200 return -1;
201 }
202 if (value == null)
203 {
204 Console.Write("value is empty");
205 return -1;
206 }
207 DBNode<T> current = new DBNode<T>();
208 current = header;
209 int result = 0;
210
211 while (current.Next != null)
212 {
213 if (current.Data.Equals(value))
214 {
215 result=1;
217 }
218 }
219 return result;
220 }
221 }
此外，循环链表的基本操作与单链表大体相同，只是判断链表结束的条件并不是判断结点的引用域是否为空，
而是判断结点的引用域是否为头引用，其它没有较大的变化，有兴趣的朋友可以写写。
(2) 双向链表操作类实现
注意：由于双向链表的结点有两个引用，所以，在双向链表中插入和删除结点比单链表要复杂。双向链表中结点的插入分为在结点之前插入和在结点之后插入，插入操作要对四个引用进行操作
同样，删除操作也需要多多注意，其他的操作和单链表类似,不再赘述.
Code
[copy to clipboard]
CODE:
1public class DBLinkList<T> : IListDS<T>
2 {
3 private DBNode<T> header;
4 public DBNode<T> Header
5 {
6 get
7 {
8 return header;
9 }
10 set
11 {
12 header = value;
13 }
14 }
15 public DBLinkList()
16 {
17 header = new DBNode<T>();
18 header.Next = null;
19 header.Prev = null;
20 }
21 /**//// <summary>
22 /// 获取长度
23 /// </summary>
24 /// <returns></returns>
25 public int GetLength()
26 {
27 DBNode<T> p = header;
28 int len = 0;
29 while (p != null)
30 {
31 ++len;
32 p = p.Next;
33 }
34 return len;
35 }
36 /**//// <summary>
37 /// 清空操作
38 /// </summary>
39 public void Clear()
40 {
41 header = null;
42 }
43 /**//// <summary>
44 /// 判断线性表是否为空
45 /// </summary>
46 /// <returns></returns>
47 public bool IsEmpty()
48 {
49 if (header.Data==null)
50 {
51 return true;
52 }
53 else
54 {
55 return false;
56 }
57 }
58 /**//// <summary>
59 /// 查找节点
60 /// </summary>
61 /// <param name="i"></param>
62 /// <returns></returns>
63 private DBNode<T> FindNode(int i)
64 {
65 if (IsEmpty())
66 {
67 Console.Write("list is empty");
68 return null;
69 }
70 if (i < 1)
71 {
72 Console.Write("Index is error");
73 return null;
74 }
75 DBNode<T> current = new DBNode<T>();
76 current = header;
77 int j = 1;
78 while (current.Next != null && j < i)
79 {
80 ++j;
81 current = current.Next;
82 }
83 return current;
84 }
85 /**//// <summary>
86 /// 插入操作,在第i个节点前面
87 /// </summary>
88 /// <param name="item"></param>
89 /// <param name="i"></param>
90 public void Insert(T item, int i)
91 {
92 DBNode<T> current = FindNode(i);
93 DBNode<T> newNode = new DBNode<T>(item);
94 if (current != null)
95 {
96 current.Prev.Next = newNode;
97 newNode.Next = current;
98 newNode.Prev = current.Prev;
99 current.Prev = newNode;
100 }
101 else
102 {
103 Console.Write("the node is not exist!");
104 }
105 }
106 /**//// <summary>
107 /// 插入操作,在第i个节点后面插入item
108 /// </summary>
109 /// <param name="item"></param>
110 /// <param name="i"></param>
111 public void InsertBack(T item, int i)
112 {
113 DBNode<T> current = FindNode(i);
114 DBNode<T> newNode = new DBNode<T>(item);
115 if (current != null)
116 {
117 current.Next.Prev = newNode;
118 newNode.Prev = current;
119 newNode.Next = current.Next;
120 current.Next = newNode;
121 }
122 else
123 {
124 Console.Write("the node is not exist!");
125 }
126 }
127 /**//// <summary>
128 /// 附加操作,线性表未满，将值为item的新元素添加到末尾
129 /// </summary>
130 /// <param name="item"></param>
131 public void Append(T item)
132 {
133 DBNode<T> newNode = new DBNode<T>(item);
134 DBNode<T> p = new DBNode<T>();
135 if (header == null)
136 {
137 header = newNode;
138 return;
139 }
140 p = header;
141
142 while (p.Next != null)
143 {
144 p = p.Next;
145 }
146 p.Next = newNode;
147 }
148
149 /**//// <summary>
150 /// 删除操作
151 /// </summary>
152 /// <param name="i"></param>
153 /// <returns></returns>
154 public T Delete(int i)
155 {
156 DBNode<T> current = FindNode(i);
157 if (current != null)
158 {
159 current.Prev.Next = current.Next;
160 current.Next.Prev = current.Prev;
161 current.Prev = null;
162 current.Next = null;
163 return current.Data;
164 }
165 else
166 {
167 Console.Write("the node is not exist!");
168 return default(T);
169 }
170 }
171 /**//// <summary>
172 /// 取表元
173 /// </summary>
174 /// <param name="i"></param>
175 /// <returns></returns>
176 public T GetElem(int i)
177 {
178 DBNode<T> current = FindNode(i);
179 if (current != null)
180 {
181 return current.Data;
182 }
183 else
184 {
185 Console.Write("the node is not exist!");
186 return default(T);
187 }
188 }
189
190 /**//// <summary>
191 /// 按值查找
192 /// </summary>
193 /// <param name="value"></param>
194 /// <returns>-1:链表或参数异常;0:节点不存在;1:值代表的位置</returns>
195 public int Locate(T value)
196 {
197 if (IsEmpty())
198 {
199 Console.Write("list is empty");
200 return -1;
201 }
202 if (value == null)
203 {
204 Console.Write("value is empty");
205 return -1;
206 }
207 DBNode<T> current = new DBNode<T>();
208 current = header;
209 int result = 0;
210
211 while (current.Next != null)
212 {
213 if (current.Data.Equals(value))
214 {
215 result=1;
217 }
218 }
219 return result;
220 }
221 }
此外，循环链表的基本操作与单链表大体相同，只是判断链表结束的条件并不是判断结点的引用域是否为空，
而是判断结点的引用域是否为头引用，其它没有较大的变化，有兴趣的朋友可以写写。
