概念介紹： 單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。 鏈表中的數據是以結點來表示的，每個結點的構成：元素(數據元素的映象) + 指針(指示後繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據 由圖可知： 鏈表在進行添加/刪除時，只需要 ...
概念介紹：
單鏈表是一種鏈式存取的數據結構，用一組地址任意的存儲單元存放線性表中的數據元素。
鏈表中的數據是以結點來表示的，每個結點的構成：元素(數據元素的映象) + 指針(指示後繼元素存儲位置)，元素就是存儲數據的存儲單元，指針就是連接每個結點的地址數據
由圖可知：
- 鏈表在進行添加/刪除時，只需要修改 當前節點和相鄰節點 的next，更新效率高
- 遍曆數據，需要根據節點按順序訪問，導致查詢速度慢，時間複雜度為O(n)
- 每個節點中都保存了下一個節點的指針【Next，最後一個節點的next為null】，所以長度是動態變化的，且不是連續記憶體空間
相關代碼：
MyLinkedListNode:自定義鏈表節點類
1 /// <summary> 2 /// 自定義鏈表節點類： 單鏈表 3 /// </summary> 4 public class MyLinkedListNode<T> 5 { 6 /// <summary> 7 /// 當前節點 8 /// </summary> 9 public T Node { get; set; } 10 11 /// <summary> 12 /// 下一個節點 13 /// </summary> 14 public MyLinkedListNode<T> Next { get; set; } 15 16 /// <summary> 17 /// 構造函數： 無參構造函數 18 /// </summary> 19 /// <param name="Node"></param> 20 public MyLinkedListNode() 21 { 22 this.Node = default; 23 this.Next = null; 24 } 25 26 /// <summary> 27 /// 構造函數： 指定當前節點，常用於 新增根節點和最後一個節點 28 /// </summary> 29 /// <param name="node"></param> 30 public MyLinkedListNode(T node) 31 { 32 this.Node = node; 33 this.Next = null; 34 } 35 36 /// <summary> 37 /// 構造函數： 指定當前節點和下一節點，常用於 新增內部節點/確定下一節點 的情況 38 /// </summary> 39 /// <param name="next"></param> 40 /// <param name="Next"></param> 41 public MyLinkedListNode(T node, MyLinkedListNode<T> next) 42 { 43 this.Node = node; 44 this.Next = next; 45 } 46 }View Code
MyLinkedList:自定義鏈表
1 /// <summary> 2 /// 自定義鏈表 3 /// 功能： 4 /// 1.添加： 添加到集合最後面 5 /// 2.添加： 添加到集合最前面 6 /// 3.添加： 添加索引後面 7 /// 4.添加： 添加索引前面 8 /// 5.刪除： 刪除T 9 /// 6.刪除： 刪除指定索引 10 /// 7.刪除： 刪除第一個 11 /// 8.刪除： 刪除最後一個 12 /// 9.刪除： 刪除所有 13 /// </summary> 14 public class MyLinkedList<T> 15 { 16 /// <summary> 17 /// 存儲鏈表集合-根節點： 18 /// 框架自帶了雙向鏈表 System.Collections.Generic.LinkedList，鏈表集合保存在 MyLinkedListNode 中 19 /// 考慮到存在clear方法，鏈表預設值為null更方便 20 /// </summary> 21 private MyLinkedListNode<T> _rootNode = null; // { get; set; } 22 23 /// <summary> 24 /// 索引索引器，從0開始，根據索引返回指定索引節點信息 25 /// </summary> 26 /// <param name="index"></param> 27 /// <returns></returns> 28 public T this[int index] 29 { 30 get 31 { 32 var node = GetNodeAt(index).Node; 33 Console.WriteLine($"this[int {index}] = {node}\r\n"); 34 return node; 35 } 36 } 37 38 #region 查詢方法 39 40 /// <summary> 41 /// 根據索引返回指定索引節點信息 42 /// </summary> 43 /// <param name="index">索引，從0開始</param> 44 /// <returns></returns> 45 private MyLinkedListNode<T> GetNodeAt(int index) => GetNodeTupleAt(index)?.Item1; 46 47 /// <summary> 48 /// 根據索引返回指定索引：節點元組 49 /// </summary> 50 /// <param name="index">索引，從0開始</param> 51 /// <returns>item1:當前節點;item2:上一節點;item3:下一節點;</returns> 52 private Tuple<MyLinkedListNode<T>, MyLinkedListNode<T>, MyLinkedListNode<T>> GetNodeTupleAt(int index) 53 { 54 if (index < 0) return null; 55 if (_rootNode == null) throw new Exception("自定義鏈表為空！"); 56 57 var num = 0; 58 // 當前節點 59 MyLinkedListNode<T> currentNode = _rootNode; 60 // 上一節點 61 MyLinkedListNode<T> prevNode = _rootNode; 62 // while迴圈會在 currentNode == 倒數第二個節點時就會停止迴圈，所以while後面需要再做一次判斷 63 while (currentNode.Next != null) 64 { 65 // 如果當前索引 和 查找索引相同，則返回擔負起節點 66 if (num == index) return GetValidNodeTuple(index, currentNode, prevNode); 67 // 重置：上一節點 68 prevNode = currentNode; 69 // 重置：當前節點 70 currentNode = currentNode.Next; 71 num++; 72 } 73 if (num < index) throw new Exception("索引超過鏈表長度！"); 74 return num == index ? GetValidNodeTuple(index, currentNode, prevNode) : null; 75 } 76 77 /// <summary> 78 /// 獲取有效的節點元組 79 /// </summary> 80 /// <param name="index">索引</param> 81 /// <param name="currentNode">當前節點</param> 82 /// <param name="prevNode">上一節點【如果索引 == 0 ？ null ：上一節點 】</param> 83 /// <returns>item1:當前節點;item2:上一節點;item3:下一節點;</returns> 84 private Tuple<MyLinkedListNode<T>, MyLinkedListNode<T>, MyLinkedListNode<T>> GetValidNodeTuple(int index, MyLinkedListNode<T> currentNode, MyLinkedListNode<T> prevNode) 85 { 86 return new Tuple<MyLinkedListNode<T>, MyLinkedListNode<T>, MyLinkedListNode<T>>(currentNode, index == 0 ? null : prevNode, currentNode.Next); 87 } 88 89 #endregion 90 91 #region 添加方法 92 93 /// <summary> 94 /// 1.添加： 添加到集合最後面 95 /// </summary> 96 /// <param name="item"></param> 97 public void Append(T item) 98 { 99 MyLinkedListNode<T> node = new MyLinkedListNode<T>(item); 100 // 如果鏈表集合為空，則講當前 元素當作跟節點 101 if (_rootNode == null) 102 { 103 _rootNode = node; 104 return; 105 } 106 107 // 迴圈得到最末節點 108 MyLinkedListNode<T> currentNode = _rootNode; 109 while (currentNode.Next != null) currentNode = currentNode.Next; 110 111 // 添加到集合最後面 112 currentNode.Next = node; 113 } 114 115 /// <summary> 116 /// 2.添加： 添加到集合最前面 117 /// </summary> 118 /// <param name="item"></param> 119 public void AddFirst(T item) 120 { 121 MyLinkedListNode<T> node = new MyLinkedListNode<T>(item); 122 // 如果鏈表集合為空，則講當前 元素當作跟節點 123 if (_rootNode == null) 124 { 125 _rootNode = node; 126 return; 127 } 128 129 _rootNode = new MyLinkedListNode<T>(item, _rootNode); 130 131 // 顯示鏈表中的所有數據 132 Console.Write($"AddFirst({item})\t"); 133 Show(); 134 } 135 136 /// <summary> 137 /// 3.添加： 在索引後面添加 138 /// 3.1.獲取到當前索引的節點 139 /// 3.2.根據item創建新節點,把 當前節點的 下一節點指給 新節點的下一節點 140 /// 3.3.把新節點當作當前節點的下一節點 141 /// </summary> 142 /// <param name="index"></param> 143 /// <param name="item"></param> 144 public void AddAtAfter(int index, T item) 145 { 146 MyLinkedListNode<T> node = new MyLinkedListNode<T>(item); 147 // 如果鏈表集合為空，則講當前 元素當作跟節點 148 if (_rootNode == null) 149 { 150 _rootNode = node; 151 return; 152 } 153 // 3.1.獲取到當前索引的節點 154 var currentNode = GetNodeAt(index); 155 // 如果鏈表集合為空，則講當前 元素當作跟節點 156 if (currentNode == null) 157 { 158 _rootNode = node; 159 return; 160 } 161 162 // 3.2.根據item創建新節點 163 var newNode = new MyLinkedListNode<T>(item, currentNode.Next); 164 165 // 3.3.把新節點當作當前節點的下一節點 166 currentNode.Next = newNode; 167 168 // 顯示鏈表中的所有數據 169 Console.Write($"AddAtAfter(int {index},T {item})\t"); 170 Show(); 171 } 172 173 /// <summary> 174 /// 4.添加： 在索引前面添加 175 /// 4.1.獲取到 當前索引 和 上一索引 的節點 176 /// 4.2.根據item創建新節點，把當前節點當作新節點的下一節點 177 /// 4.3.把新節點當作上一節點的下一節點 178 /// </summary> 179 /// <param name="index"></param> 180 /// <param name="item"></param> 181 public void AddAtBefore(int index, T item) 182 { 183 var nodeTuple = GetNodeTupleAt(index); 184 if (nodeTuple == null) throw new Exception("索引超過鏈表長度！"); 185 186 // 4.1.獲取到 當前索引 和 上一索引 的節點 187 var currentNode = nodeTuple.Item1; 188 var prevtNode = nodeTuple.Item2; 189 190 // 4.2.根據item創建新節點，把當前節點當作新節點的下一節點 191 var newNode = new MyLinkedListNode<T>(item, currentNode); 192 193 // 4.3.把新節點當作上一節點的下一節點:如果索引是0，則新節點作為鏈接根節點 194 if (index == 0) _rootNode = newNode; 195 else prevtNode.Next = newNode; 196 197 // 顯示鏈表中的所有數據 198 Console.Write($"AddAtBefore(int {index},T {item})\t"); 199 Show(); 200 } 201 202 #endregion 203 204 #region 刪除方法 205 206 207 /// <summary> 208 /// 5.刪除： 刪除T 209 /// 5.1.得到 當前節點/上一節點/下一節點 210 /// 5.2.把 上一節點的下一節點 更新為 下一節點 211 /// </summary> 212 /// <param name="item"></param> 213 public void Remove(T item) 214 { 215 if (_rootNode == null) return; 216 // 當前節點 217 var currentNode = _rootNode; 218 // 上一節點 219 MyLinkedListNode<T> prevNode = null; 220 while (currentNode.Next != null) 221 { 222 if (currentNode.Node.Equals(item)) 223 { 224 // 根據 當前節點 的 上一節點和下一節點 刪除 當前節點 225 Remove(prevNode, currentNode.Next); 226 227 // 顯示鏈表中的所有數據 228 Console.Write($"Remove({item})\t"); 229 Show(); 230 return; 231 } 232 // 重置 上一節點 和 當前節點 233 prevNode = currentNode; 234 currentNode = currentNode.Next; 235 } 236 // 如果需要刪除的是最後一個節點，則while迴圈在 currentNode == 倒數第二個節點時就會停止迴圈 237 Remove(prevNode, null); 238 239 // 顯示鏈表中的所有數據 240 Console.Write($"Remove({item})\t"); 241 Show(); 242 } 243 244 /// <summary> 245 /// 根據 當前節點 的 上一節點和下一節點 刪除 當前節點：把上一節點的next 指向 下一節點 246 /// </summary> 247 /// <param name="prevNode"></param> 248 /// <param name="nextNode"></param> 249 private void Remove(MyLinkedListNode<T> prevNode, MyLinkedListNode<T> nextNode) 250 { 251 if (prevNode == null) _rootNode = nextNode; 252 else prevNode.Next = nextNode; 253 } 254 255 /// <summary> 256 /// 6.刪除： 刪除指定索引 257 /// 6.1.得到 當前/上一/下一節點 258 /// 6.2.把當前節點的下一節點 更新為 下一節點 259 /// </summary> 260 /// <param name="index"></param> 261 public void RemoveAt(int index) 262 { 263 var nodeTuple = GetNodeTupleAt(index); 264 265 // 上一節點 266 var prevNode = nodeTuple.Item2; 267 // 判斷上一節點是不是null ? 當前節點為根節點，需要把下一節點更新為更節點 268 if (prevNode == null) _rootNode = nodeTuple.Item3; 269 else prevNode.Next = nodeTuple.Item3; 270 271 272 // 顯示鏈表中的所有數據 273 Console.Write($"RemoveAt({index})\t"); 274 Show(); 275 } 276 277 /// <summary> 278 /// 7.刪除： 刪除第一個 279 /// </summary> 280 public void RemoveFirst() 281 { 282 if (_rootNode == null) return; 283 _rootNode = _rootNode.Next; 284 285 // 顯示鏈表中的所有數據 286 Console.Write($"RemoveFirst()\t"); 287 Show(); 288 } 289 290 /// <summary> 291 /// 8.刪除： 刪除最後一個 292 /// </summary> 293 public void RemoveLast() 294 { 295 if (_rootNode == null) return; 296 // 如果鏈表只存在根節點，則把根節點刪除 297 if (_rootNode.Next == null) 298 { 299 _rootNode = null; 300 return; 301 } 302 // while迴圈獲得最後一個節點 303 var currentNode = _rootNode; 304 // 上一節點/倒數第二個節點 305 MyLinkedListNode<T> prevNode = null; 306 while (currentNode.Next != null) 307 { 308 prevNode = currentNode; 309 currentNode = currentNode.Next; 310 } 311 prevNode.Next = null; 312 313 // 顯示鏈表中的所有數據 314 Console.Write($"RemoveLast()\t"); 315 Show(); 316 } 317 318 /// <summary> 319 /// 9.刪除： 刪除所有 320 /// </summary> 321 public void Clear() 322 { 323 _rootNode = null; 324 325 // 顯示鏈表中的所有數據 326 Console.Write($"Clear()\t"); 327 Show(); 328 } 329 330 #endregion 331 332 /// <summary> 333 /// 顯示鏈表中的所有數據 334 /// </summary> 335 public void Show() 336 { 337 if (_rootNode == null) 338 { 339 Console.WriteLine($"鏈表中的數據為空！\r\n"); 340 return; 341 } 342 StringBuilder builder = new StringBuilder(); 343 344 MyLinkedListNode<T> currentNode = _rootNode; 345 while (currentNode.Next != null) 346 { 347 builder.Append($"{currentNode.Node}\t"); 348 currentNode = currentNode.Next; 349 } 350 // 最後一個節點next為null，不會進入while 351 builder.Append($"{currentNode.Node}\t"); 352 353 Console.WriteLine($"鏈表中的數據為：\r\n{builder.ToString()}\r\n"); 354 } 355 }View Code
測試代碼：
1 /// <summary> 2 /// 測試單鏈表 3 /// </summary> 4 public static void RunLinkedList() 5 { 6 Console.WriteLine("======= 鏈表測試 Start ======="); 7 8 MyLinkedList<string> myLinkedList = new MyLinkedList<string>(); 9 myLinkedList.Append("張三"); 10 myLinkedList.Append("李四"); 11 myLinkedList.Append("王五"); 12 myLinkedList.Append("六麻子"); 13 myLinkedList.Append("田七"); 14 myLinkedList.Show(); // 張三 李四 王五 六麻子 田七 15 16 // 異常測試 17 var a = myLinkedList[1]; // 張三 18 a = myLinkedList[3]; // 六麻子 19 //a = myLinkedList[11]; 20 21 // 測試添加功能 22 myLinkedList.AddFirst("郭大爺"); // 郭大爺 張三 李四 王五 六麻子 田七 23 myLinkedList.AddAtAfter(0, "海大爺"); // 郭大爺 海大爺 張三 李四 王五 六麻子 田七 24 myLinkedList.AddAtBefore(0,
