C#模擬鏈表數據結構的實例解析

寫在前面

模塊化編程是大多數初學者必經之路，然後可能你走向了結構化編程，鏈表是一種典型結構模式，它的出現克服了數組必須預先知道大小的缺陷，聽不懂?你只需要記住，鏈表結構非常牛叉就可以了，學習這種結構對我們的邏輯思維有很大提升。

什麼是鏈表結構呢？

鏈表是一種物理存儲單元上非連續、非順序的存儲結構。比如A->B->C，這種結構，我們可以理解為A連接著B，B連接C，像這種結構我們就叫做鏈表結構。對了，火車的車廂，其實就是鏈表的結構的最好說明

為什麼要有鏈表結構呢？

學過計算機的都知道數組(Array),數組常用切好用，但也存在問題。首先，數組必須需要知道空間大小（int[] age = new int[100], 必須聲明長度），其次，對於元素之間插入、刪除操作效率很低（如何在數組中間插入一個元素？）。

鏈表的出現，完美的解決了這些問題。

如何實現鏈表

首先我們需要聲明一種結構

? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 //鏈表結構: 構造節點 - 連接節點 //Template class Node { public int num; //指向下一個元素 public Node next; } //鏈表結構: 構造節點 - 連接節點 //Template class Node { public int num; //指向下一個元素 public Node next; }

我們可以把上面的這種結構看做是一個禮品盒,可以存放整形數值。

然後我們創建一個MyList先生，這位先生就使用Node去存放整形物品，而且使用了鏈表結構哦！

? 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 class MyList { public Node currentNode; public Node point; public MyList() { currentNode = new Node(); } //存放物品 public void Add(int value) { //第一次 if(point == null) { currentNode.num = value; point = currentNode; } else //2 3 4..... 次 { Node temp = new Node(); temp.num = value; point.next = temp; //更新指針 point = temp; } } } class MyList { public Node currentNode; public Node point; public MyList() { currentNode = new Node(); } //存放物品 public void Add(int value) { //第一次 if(point == null) { currentNode.num = value; point = currentNode; } else //2 3 4..... 次 { Node temp = new Node(); temp.num = value; point.next = temp; //更新指針 point = temp; } } }

然後，我們可以在客戶端測試一下：

? 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 public static void Main (string[] args) { MyList<int> mList = new MyList<int>(); //添加元素 mList.Add(1); mList.Add(11); mList.Add(111); mList.Add(1111); while(mList.currentNode != null) { Console.WriteLine (mList.currentNode.num); mList.currentNode = mList.currentNode.next; } } public static void Main (string[] args) { MyList<int> mList = new MyList<int>(); //添加元素 mList.Add(1); mList.Add(11); mList.Add(111); mList.Add(1111); while(mList.currentNode != null) { Console.WriteLine (mList.currentNode.num); mList.currentNode = mList.currentNode.next; } }

我們自己定義的一個整形集合就這樣ok了。它有兩個優點：可以存放任意多個元素！方便元素的插入和刪除。

雙向鏈表的定義和簡單操作：

雙向鏈表其實是單鏈表的改進。當我們對單鏈表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。這是由單鏈表結點的結構所限制的。因為單鏈表每個結點只有一個存儲直接後繼結點地址的鏈域，那麼能不能定義一個既有存儲直接後繼結點地址的鏈域，又有存儲直接前驅結點地址的鏈域的這樣一個雙鏈域結點結構呢？這就是雙向鏈表。在雙向鏈表中，結點除含有數據域外，還有兩個鏈域，一個存儲直接後繼結點地址，一般稱之為右鏈域；一個存儲直接前驅結點地址，一般稱之為左鏈域。

? 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 namespace DounlyLinkedlist { //定義雙向鏈表的結點 public class Node { public Object Element; public Node FLink; public Node BLink; public Node() { Element = null; FLink = null; BLink = null; } public Node(Object element) { Element = element; FLink = null; BLink = null; } } //鏈表操作的類 public class LinkedList { public Node Header; public LinkedList() { Header = new Node("Header"); Header.FLink = null; Header.BLink = null; } //查找結點 private Node Find(Object item) { Node Current = new Node(); Current = Header; while (Current.Element != item) { Current = Current.FLink; } return Current; } //插入結點 public void InsertNode(Object item,Object postionItem) { Node Current = new Node(); Node NewItem = new Node(item); Current = Find(postionItem); if (Current != null) { NewItem.FLink = Current.FLink; NewItem.BLink = Current; Current.FLink = NewItem; } } //刪除結點 public void Remove(Object item) { Node P = Find(item); if (P.FLink != null) { P.BLink.FLink = P.FLink; P.FLink.BLink = P.BLink; P.BLink = null; P.FLink = null; } } //查找雙向鏈表最後一個結點元素 private Node FindLast() { Node Current = new Node(); Current = Header; while (!(Current.FLink == null)) { Current = Current.FLink; } return Current; } //逆向打印雙向鏈表 public void PrintReverse() { Node Current = new Node(); Current = FindLast(); while (!(Current.BLink == null)) { Console.WriteLine(Current.Element); Current = Current.BLink; } } //打印雙向鏈表 public void Print() { Node Current = new Node(); Current = Header; while (!(Current.FLink == null)) { Console.WriteLine(Current.FLink.Element); Current = Current.FLink; } } } }

鏈表應用場景

應用場景：集合（動態數組）、貪吃蛇、地圖的循環生成、老虎機效果等等,鏈表可以幫助我們完成很多事情。