概述
由于最近在工作中需要用到树形结构来解决一些问题，所以萌生了系统学习“数据结构和算法”的想法，于是乎从最简单的表结构开始。由于数组是最简单的表结构的实现，也是各个编程语言内置的数据类型，所以不做更多的记录。表结构中以下实现打算学习：
- LinkedList
- Stack
- Queue
- HashTable
- Dictionary
本篇为学习数据结构的第一篇随笔，从最简单的单向链表开始吧。
实现（C#）
平台：dotNet Core 1.0， C#
IDE：VSCode
如果考虑算法复用的话，可以实现泛型。
1 public class SingleLinkedList
2 {
3 //Inner class, represents a node of linked list. Each node consists of data and a link to next node
4 class Node
5 {
6 public Node() { }
7 public Node(object item)
8 {
9 Data = item;
10 Next = null;
11 }
12 public object Data { get; set; }
13 public Node Next { get; set; }
14
15 public override string ToString()
16 {
17 return "Node:" + Data.ToString();
18 }
19 }
20
21 public SingleLinkedList()
22 {
23 header = null;
24 }
25
26 #region Public API
27
28 //Add item before first node
29 public void AddFirst(object item)
30 {
31 if (header == null)
32 {
33 header = new Node(item);
34 }
35 else
36 {
37 var newNode = new Node(item);
38 newNode.Next = header;
39 header = newNode;
40 }
41 }
42
43 //Add item after last node
44 public void AddLast(object item)
45 {
46 if (header == null)
47 {
48 header = new Node(item);
49 }
50 else
51 {
52 LastNode().Next = new Node(item);
53 }
54 }
55
56 public void Insert(int index, object item)
57 {
58 if (index < 0) throw new ArgumentOutOfRangeException();
59 if (index == 0)
60 {
61 AddFirst(item);
62 return;
63 }
64 if (header == null) throw new ArgumentOutOfRangeException();
65
66 var node = GetNode(index - 1);
67 var newNode = new Node(item);
68 newNode.Next = node.Next;
69 node.Next = newNode;
70 }
71
72 public object Get(int index)
73 {
74 return GetNode(index).Data;
75 }
76
77 //Find index of specified data
78 public int IndexOf(object item)
79 {
80 if (header == null) return -1;
81
82 var curIndex = 0;
83 for (var cur = new Node { Next = header }; cur.Next != null; cur = cur.Next, curIndex++)
84 {
85 if (!cur.Next.Data.Equals(item)) continue;
86 return curIndex;
87 }
88
89 return -1;
90 }
91
92 //Remove specified data of its first occurance
93 public void Remove(object item)
94 {
95 if (header == null) return;
96
97 //Add a fake node pointing to header, so we don't need set up a local variable pointing to header. This is simple. Nice trick.
98 for (var cur = new Node { Next = header }; cur.Next != null; cur = cur.Next)
99 {
100 if (!cur.Next.Data.Equals(item)) continue;
101 if (cur.Next == header)
102 {
103 header = header.Next;
104 }
105 else
106 {
107 cur.Next = cur.Next.Next;
108 }
109 }
110 }
111
112 //此方法可以理解为先获取index-1位置的Node，然后设置此Node的下一个节点跳过index处的节点
113 public void RemoveAt(int index)
114 {
115 if (index < 0 || header == null) throw new ArgumentOutOfRangeException();
116 else if (index == 0)
117 {
118 header = header.Next;
119 }
120 else
121 {
122 Node pre = GetNode(index - 1);
123 pre.Next = pre.Next.Next;
124 }
125 }
126
127 public bool Contains(object item)
128 {
129 if (header == null) return false;
130 var current = header;
131 while (current != null && !current.Data.Equals(item))
132 {
133 current = current.Next;
134 }
135 return current != null;
136 }
137
138 public void Clear()
139 {
140 header = null;
141 }
142
143 public bool IsEmpty()
144 {
145 return header == null;
146 }
147
148 public int Count()
149 {
150 if (IsEmpty()) return 0;
151 int count = 1;
152 for (var cur = header; cur.Next != null; cur = cur.Next, count++)
153 {
154 }
155 return count;
156 }
157
158 public override string ToString()
159 {
160 if (header == null) return "Empty";
161 StringBuilder sb = new StringBuilder();
162 for (Node current = header; current != null; current = current.Next)
163 {
164 sb.Append(current.Data.ToString());
165 if (current.Next != null) sb.Append("->");
166 }
167 return sb.ToString();
168 }
169
170 #endregion
171
172 #region Private Method
173
174 private Node LastNode()
175 {
176 if (header == null) throw new InvalidOperationException();
177
178 var current = header;
179 while (current.Next != null)
180 {
181 current = current.Next;
182 }
183 return current;
184 }
185
186 private Node GetNode(int index)
187 {
188 if (header == null) throw new ArgumentOutOfRangeException();
189
190 int curIndex = 0;
191 var cur = header;
192 while (cur != null && curIndex != index)
193 {
194 cur = cur.Next;
195 curIndex++;
196 }
197
198 if (cur == null)
199 {
200 throw new ArgumentOutOfRangeException();
201 }
202 else
203 {
204 return cur;
205 }
206 }
207
208
209 #endregion
210
211 #region Fields
212
213 private Node header;
214
215 #endregion
216 }
测试代码
1 public static void Main(string[] args) 2 { 3 Can_Add_First(); 4 Can_Add_Last(); 5 Can_Insert(); 6 Other(); 7 8 Console.ReadKey(); 9 } 10 11 static void Can_Add_First() 12 { 13 var list = new SingleLinkedList(); 14 //add when list is empty 15 list.AddFirst("First"); 16 Expect(list, "First"); 17 //add when list is not empty 18 list.AddFirst("Second"); 19 list.AddFirst("Third"); 20 Expect(list, "Third->Second->First"); 21 } 22 23 static void Can_Add_Last() 24 { 25 var list = new SingleLinkedList(); 26 //add when list is empty 27 list.AddLast("First"); 28 Expect(list, "First"); 29 //add when list is not empty 30 list.AddLast("Second"); 31 list.AddLast("Third"); 32 Expect(list, "First->Second->Third"); 33 } 34 35 static void Can_Insert() 36 { 37 var list = new SingleLinkedList(); 38 //insert when list is empty 39 list.Insert(0, "First"); 40 Expect(list, "First"); 41 //insert when list is not empty 42 list.Insert(1, "Second"); 43 Expect(list, "First->Second"); 44 list.Insert(1, "Third"); 45 Expect(list, "First->Third->Second"); 46 list.Insert(0, "Forth"); 47 Expect(list, "Forth->First->Third->Second"); 48 } 49 50 static void Other() 51 { 52 var list = new SingleLinkedList(); 53 list.AddLast("First"); 54 list.AddLast("Second"); 55 list.AddLast("Third"); 56 Console.WriteLine("object Get(int) Passed: " + (list.Get(1) as string == "Second")); 57 58 Console.WriteLine("int IndexOf(object) Passsed: " + ((int)list.IndexOf("Third") == 2)); 59 Console.WriteLine("int IndexOf(object) Passsed: " + ((int)list.IndexOf("Forth") == -1)); 60 61 list.Remove("First"); 62 Expect(list, "Second->Third"); 63 list.RemoveAt(1); 64 Expect(list, "Second"); 65 66 Console.WriteLine("bool Contains(object) Passed: " + (list.Contains("Second") == true)); 67 Console.WriteLine("bool Contains(object) Passed: " + (list.Contains("First") == false)); 68 Console.WriteLine("int Count() Passed: " + (list.Count() == 1)); 69 Console.WriteLine("bool IsEmpty() Passed: " + (list.IsEmpty() == false)); 70 71 list.Clear(); 72 Console.WriteLine("int Count() Passed: " + (list.Count() == 0)); 73 Console.WriteLine("bool IsEmpty() Passed: " + (list.IsEmpty() == true)); 74 }