单向链表练习

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。

  1 using System;
  2
  3 namespace LinkClass
  4 {
  5     class Program
  6     {
  7         static void Main(string[] args)
  8         {
  9             LinkedList lkList = new LinkedList("MyLinkList");
10             lkList.AddNode("FirstNode");
11             lkList.AddNode("SecondNode");
12             lkList.AddNode("ThirdNode");
13             lkList.AddNode("FourthNode");
14             lkList.AddNode("FifthNode");
15             lkList.AddNode("SixthNode");
16             lkList.PrintAllNode();
17             lkList.DeleteNode("FourthNode");
18             lkList.PrintAllNode();
19             lkList.AddNode("FourthNode", "ThirdNode");
20             lkList.PrintAllNode();
21             lkList.DeleteNode("FourtsssshNode");
22             lkList.PrintAllNode();
23             lkList.SearchNode("SeventhNode");
24             lkList.PrintNode("FirstNode");
25
26             Console.ReadLine();
27         }
28     }
29
30     class Node
31     {
32         //单向链表的一个节点应该有三个字段，分别保存节点数据、节点名称和下一个节点
33         private object data;
34         private string name;
35         private Node next;
36
37         //属性
38         public Node Next
39         {
40             get { return next; }
41             set { next = value; }
42         }
43         public object Data
44         {
45             get { return data; }
46             set { data = value; }
47         }
48         public string Name
49         {
50             get { return name; }
51         }
52
53         //构造函数
54         public Node(string name)
55         {
56             this.name = name;
57             this.data = null;
58             this.next = null;
59         }
60         public Node()
61         {
62         }
63     }
64
65     class LinkedList
66     {
67         private int nodeCount;
68         private Node headNode;
69         private string listName;
70
71         public LinkedList(string listName)
72         {
73             this.nodeCount = 1;
74
75             this.headNode = new Node("HeadNode");
76             //为headNode赋值，这样确保调用AddNode()方法的时候不会出现空引用异常。
77             //当然AddNode()方法做过首节点的null判断后，就不需要这样定义构造函数了。
78
79             this.listName = listName;
80         }
81
82
83         public void AddNode1(string nodeName)
84         {
85             Node newNode = new Node(nodeName);
86             Node current = this.headNode;
87             while (current.Next != null)
88             {
89                 current = current.Next;
90             }
91             //第一版：这样写是有错误的，若headNode为null，则current为null，
92             //此时while循环会出现空引用异常。
93             //所以对headNode必须先判断是否为空，或者在构造函数中为headNode赋值。
94
95             current.Next = newNode;
96             nodeCount++;
97         }
98
99
100         /// <summary>
101         /// 第二版直接插入一个新节点，默认在最后插入，这是正确的实现:
102         /// </summary>
103         /// <param name="nodeName">要插入的节点的名称</param>
104         public void AddNode(string nodeName)
105         {
106             Node newNode = new Node(nodeName);
107
108             if (headNode == null)
109             {
110                 headNode = newNode;
111                 nodeCount++;
112             }
113             else
114             {
115                 Node current = this.headNode;
116                 while (current.Next != null)
117                 {
118                     current = current.Next;
119                 }
120
121                 current.Next = newNode;
122                 nodeCount++;
123             }
124         }
125
126         /// <summary>
127         /// 在指定节点(名称)后插入新节点
128         /// </summary>
129         /// <param name="nodeName"></param>
130         /// <param name="afterNode"></param>
131         //public void AddNode(string nodeName, Node afterNode)
132         //这是第一版定义的，位置节点参数是用node声明的，
133         //那样不合理，因为链表中无法直接引用节点。
134         public void AddNode(string nodeName, string afterNodeName)
135         //这是第二版，用string类型传入节点名称，这个比较合理。
136         {
137             Node current = this.headNode;
138             Node newNode = new Node(nodeName);
139             while (current.Name != afterNodeName)
140             {
141                 current = current.Next;
142             }
143             newNode.Next = current.Next;
144             current.Next = newNode;
145             this.nodeCount++;  //第一版忘记处理计数器了
146         }
147
148         /// <summary>
149         /// 删除某个节点
150         /// </summary>
151         /// <param name="nodeName">要删除的节点的名称</param>
152         public void DeleteNode(string nodeName)
153         {
154             if (headNode.Name.Equals(nodeName))
155             {
156                 headNode = headNode.Next;
157                 this.nodeCount--;
158                 Console.WriteLine("Delete successfully!");
159             }
160             else
161             {
162                 Node current = new Node();
163                 current = this.headNode;
164                 while (!current.Next.Name.Equals(nodeName))
165                 {
166                     current = current.Next;
167                     if (current.Next == null)
168                     {
169                         Console.WriteLine("Delete Failed!");
170                         return;  //关键！
171                     }
172                 }
173                 current.Next = current.Next.Next;
174                 this.nodeCount--; //第一版忘记了把计数器减一
175                 Console.WriteLine("Delete successfully!");
176
177             }
178         }
179
180
181         /// <summary>
182         /// 调用FindPreNode()方法实现的节点删除
183         /// </summary>
184         /// <param name="nodeName"></param>
185         public void DeleteNode2(string nodeName)
186         {
187             Node preNode = FindPreNode(nodeName);
188             if (preNode == null)
189                 Console.WriteLine("Delete failed!");
190             else
191             {
192                 preNode.Next = preNode.Next.Next;
193                 nodeCount--;
194                 Console.WriteLine("Delete successfully!");
195             }
196         }
197
198
199         /// <summary>
200         /// 查找某个节点
201         /// </summary>
202         /// <param name="nodeName">要查找的节点的名称</param>
203         public void SearchNode(string nodeName)
204         {
205             Node current = this.headNode;
206             while (!current.Name.Equals(nodeName))
207             {
208                 current = current.Next;
209                 if (current == null)
210                 //第二版增加的，查找到最后节点还没找到，则current值为null，必须先判断。
211                 //第一版的没有做判断，若节点不存在，则会发生nullreferenceexception。
212                 {
213                     Console.WriteLine("The node {0} is not found!", nodeName);
214                     return;      //如果为空，那就是没有找到，直接返回。
215                 }
216             }
217             Console.WriteLine("The node {0} is found!", current.Name);
218         }
219
220         /// <summary>
221         /// 利用find()方法实现节点搜索
222         /// </summary>
223         /// <param name="nodeName"></param>
224         public void FindNode(string nodeName)
225         {
226             Node current = Find(nodeName);
227             if (current == null)
228             {
229                 Console.WriteLine("The node {0} is not found!", nodeName);
230             }
231             else
232             {
233                 Console.WriteLine("The node {0} is found!", current.Name);
234             }
235         }
236
237         /// <summary>
238         /// 打印所有节点
239         /// </summary>
240         public void PrintAllNode()
241         {
242             Node current = new Node();
243             current = this.headNode;
244             Console.WriteLine("There are {0} nodes: ", nodeCount);
245             Console.Write(headNode.Name + " -> ");
246             while (current.Next != null)
247             {
248                 Console.Write(current.Next.Name + " -> ");
249                 //这里用current.Next来判断，否则无法打印出最后一个节点，
250                 //但是这样一来就无法打印出第一个节点，因此前面要先打印第一个节点。
251
252                 current = current.Next;
253             }
254
255         }
256
257         /// <summary>
258         /// 类中有好几个方法都要查找节点，因此可以作为一个方法独立出来，利于复用
259         /// </summary>
260         /// <param name="nodeName"></param>
261         /// <returns>返回找到的节点</returns>
262         public Node Find(string nodeName)
263         {
264             Node current = this.headNode;
265
266             while (!current.Name.Equals(nodeName))
267             {
268                 current = current.Next;
269                 if (current == null) //current的值可能为null，所以必须加if判断。
270                 {
271                     //Console.WriteLine("{0} is not existed!", nodeName);
272                     return null;
273                 }
274             }
275             return current;
276         }
277
278
279         /// <summary>
280         /// 查找某节点的前一个节点
281         /// </summary>
282         /// <param name="curNodeName">某节点名称</param>
283         /// <returns>该节点的前一个节点</returns>
284         public Node FindPreNode(string curNodeName)
285         {
286             Node preNode = null;
287             Node current = this.headNode;
288             while (!current.Next.Name.Equals(curNodeName))
289             {
290                 current = current.Next;
291                 if (current == null)
292                 {
293                     //Console.WriteLine("Not find!");
294                     return null;
295                 }
296             }
297             preNode = current;
298             return preNode;
299         }
300
301
302         /// <summary>
303         /// 利用Find()方法实现的索引器
304         /// </summary>
305         /// <param name="nodeName"></param>
306         /// <returns></returns>
307         public Node this[string nodeName]
308         {
309             get
310             {
311                 Node current = Find(nodeName);
312                 return current;
313             }
314         }
315
316         /// <summary>
317         /// 利用索引器打印某个节点
318         /// </summary>
319         /// <param name="nodeName"></param>
320         public void PrintNode(string nodeName)
321         {
322             Console.WriteLine(this[nodeName].Name);
323         }
324     }
325 }