如果想對集合(系列)有本質的了解，鏈表是一個必須了解的概念。本篇主要包括：
● 鏈表的由來和定義
● 創建一個單向鏈表
● 其它鏈表
鏈表的由來和定義
在現實生活中，我們把不同的商品放在一個購物車中。而在面向對象的世界裡，有時候，也需要把不同類型的數據放到一起，組成一個集合。集合中的元素並不是彼此孤立的，在C#中，如何表達集合元素間的關系呢？
借助"自引用類"可以確立集合元素間的關系。比如有這樣一個自引用類：
public class Node{public int Data{get;set;}public Node Next{get;set;}public Node(int dataValue){}}
Node類的最大特點是：存在一個Node類型的屬性，這個屬性指向Node的另一個實例，Next屬性也稱為"引用鏈"。放到集合的場景中來說就是：把多個Node實例放到一個集合中，每一個Node實例包含一個Next屬性指向下一個Node實例。而該集合中的最後一個Node實例會指向null。用圖表示就是：
鏈表就是自引用類對象的線性集合，即序列。
由於每個自引用對象是由引用鏈鏈接起來，所以叫鏈表。堆棧與隊列是約束版的鏈表，而二叉查找數是非線性數據結構。
鏈表的節點或元素雖然在邏輯上是連續的、線性的，當其內存不是連續存儲的；數組元素在內存中是連續的，所以我們才可以通過索引來訪問數組元素。
創建一個單向鏈表
首先創建一個節點，是一個自引用類：
namespace LinkedListLibrary{public class ListNode{//當前節點對象public object Data { get; private set; }//Next屬性也稱為鏈，指向另一個ListNode對象實例，這樣就把2個ListNode對象實例鏈接起來了public ListNode Next { get; set; }public ListNode(object dataValue): this(dataValue, null){}public ListNode(object dataValue, ListNode nextNode){Data = dataValue;Next = nextNode;}}}
再模擬一個鏈表，如下：
namespace LinkedListLibrary{public class List{private ListNode firstNode;private ListNode lastNode;private string name;public List(string listName){name = listName;firstNode = lastNode = null;}public List() : this("list"){}......//如果第一個節點是null，那就說明集合為空public bool IsEmpty(){return firstNode == null;}}}
以上，如果第一個節點為null，那就說明該鏈表為空。List類提供了IsEmpty方法用來判斷鏈表是否為空。List還包含另外5個重要的方法，下面展開來說。
在鏈表的的第一個節點前插入。
//在最前面插入元素、節點public void InsertAtFront(object insertItem){if (IsEmpty())//如果集合為空，加進來一個元素，相當於第一個節點和第二個節點相同，都是新加的元素{firstNode = lastNode = new ListNode(insertItem);}else //如果集合不為空，第一個節點就是新加的元素,原先的第一個節點變為下一個節點{firstNode = new ListNode(insertItem, firstNode);}}
以上，當集合不為空的情況下，實際上是把新添加的節點設為第一個節點，並把新的第一個節點的引用鏈指向原先的第一個節點。
在鏈表的最後一個節點後插入。
public void InsertAtBack(object insertItem){if (IsEmpty())//如果原先集合為空，第一個節點和最後一個節點就是新加的節點{firstNode = lastNode = new ListNode(insertItem);}else//如果原先的集合不為空，最後一個節點的屬性值就是新加的節點{lastNode = lastNode.Next = new ListNode(insertItem);}}
以上，當集合不為空的情況下，實際上是把新添加的節點設置成最後一個節點，並把新的最後一個節點的引用鏈指向null。
移除鏈表最前面的節點。
//移除最前面的元素、節點//即重新設置第一個節點的Next屬性public object RemoveFromFront(){if (IsEmpty())throw new EmptyListException(name);//從第一個節點中取出節點對象object removeItem = firstNode.Data;if (firstNode == lastNode) //如果集合中只有一個元素{firstNode = lastNode = null;}else //正常情況下，把firstNode的Next屬性所指向的節點賦值給第一個節點{firstNode = firstNode.Next;}return removeItem;}
以上，本質是把原先排在第二位置的節點設置成第一個節點。
移除鏈表最後面的節點。
//移除最後面的元素、節點public object RemoveFromBack(){if (IsEmpty()){throw new EmptyListException();}//從最後一個節點中獲取節點對象object removeItem = lastNode.Data;if (firstNode == lastNode)//如果當前集合只有一個節點{firstNode = lastNode = null;}else{//先把第一個節點作為當前節點ListNode current = firstNode;//改變除最後一個節點之外的節點的值while (current.Next != lastNode){current = current.Next;}//最後current變成倒數第二個節點lastNode = current;current.Next = null;//最後一個節點的Next屬性為null，即沒有指向另一個節點}return removeItem;}
以上，從第一個節點開始，一直循環到倒數第二個節點，current就像一個指針，每指到一個節點，就把該節點的下面一個節點設置為當前節點。最後，把倒數第二個節點設置為最後一個節點。 把Current的引用鏈設置為null，讓其能被垃圾回收機制回收。
打印鏈表。
//打印顯示public void Display(){if (IsEmpty()){Console.WriteLine("集合" + name + "為空");}else{Console.WriteLine("集合的名稱是：" + name);//先把第一個節點作為當前節點ListNode current = firstNode;while (current != null){//把當前節點對象打印出來Console.Write(current.Data + " ");//把下一個節點設置為當前節點current = current.Next;}Console.WriteLine("\n");}}
以上，從第一個節點開始，一直循環到最後一個節點，current就像一個指針，每打印一個節點，就把當前節點設置為下一個節點，一直循環下去。
EmptyListException用來拋出鏈表為空的異常。
namespace LinkedListLibrary{public class EmptyListException : Exception{public EmptyListException() : base("當前集合為空"){}public EmptyListException(string name) : base("集合" + name + "為空"){}public EmptyListException(string exception, Exception inner) : base(exception, inner){}}}
客戶端調用：
using LinkedListLibrary;namespace ListTest{class Program{static void Main(string[] args){List list = new List();bool aBoolean = true;char aChar = 'a';int anInt = 12;string aStr = "hi";list.InsertAtFront(aBoolean);list.Display();list.InsertAtFront(aChar);list.Display();list.InsertAtBack(anInt);list.Display();list.InsertAtBack(aStr);list.Display();object removeObject;try{removeObject = list.RemoveFromFront();Console.WriteLine(removeObject + "被刪除了...");list.Display();removeObject = list.RemoveFromFront();Console.WriteLine(removeObject + "被刪除了...");list.Display();removeObject = list.RemoveFromBack();Console.WriteLine(removeObject + "被刪除了...");list.Display();removeObject = list.RemoveFromBack();Console.WriteLine(removeObject + "被刪除了...");list.Display();}catch (EmptyListException emptyListException){Console.Error.WriteLine("\n" + emptyListException);}Console.ReadKey();}}}
其它鏈表
以上，創建的是單向鏈表，其特點是第一個節點開始包含引用鏈，每個節點的引用鏈指向下一個節點，最後一個節點的引用鏈為null。單向鏈表只能從一個方向遍歷。
環形單向鏈表與單向鏈表的區別是：其最後一個節點的引用鏈指向第一個節點。環形單向鏈表也只能從一個方向遍歷，只不過遍歷到最後一個節點後，又回到第一個節點重新開始遍歷。
雙向鏈表的第一個節點只包含指向下一個節點的引用鏈，最後一個節點只包含指向上一個節點的引用鏈，其它節點同時包含指向前一個節點和後一個節點的引用鏈。雙向鏈表支持向前和向後遍歷。
環形雙向鏈表與雙向鏈表的區別是：第一個節點向後引用鏈指向最後一個節點，而最後一個節點的向前引用鏈指向第一個節點。
參考資料：
Visual C# 2008大學教程--（第三版）
鏈表
鏈表概述
鏈表是一種常見的重要的數據結構。它是動態地進行存儲分配的一種結構。它可以根據需要開辟內存單元。鏈表有一個“頭指針”變量，以head表示，它存放一個地址。該地址指向一個元素。鏈表中每一個元素稱為“結點”，每個結點都應包括兩個部分：一為用戶需要用的實際數據，二為下一個結點的地址。因此，head指向第一個元素：第一個元素又指向第二個元素；……，直到最後一個元素，該元素不再指向其它元素，它稱為“表尾”，它的地址部分放一個“NULL”（表示“空地址”），鏈表到此結束。
單向鏈表
單向鏈表的每個結點中除信息域以外還有一個指針域，用來指出其後續結點，單向鏈表的最後一個結點的指針域為空(NULL)。單向鏈表由頭指針唯一確定，因此單向鏈表可以用頭指針的名字來命名，例如頭指針名為head的單向鏈表稱為表head，頭指針指向單向鏈表的第一個結點。
簡單實現為：
#define NULL 0
typedef int DATATYPE
typedef struct node
{DATATYPE info；
node *next;
}LINKLIST;
雙向鏈表
每個結點中只包括一個指向下個結點的指針域，這種鏈表稱為單向鏈表。如果要在單向鏈表一個指針所指的當前位置插入一個新結點，就必須從鏈表頭指針開始逐個遍歷直到當前指針所指結點的前一結點，修改這個結點的指針。雙向鏈表的每個結點中包括兩個指針域，分別指向該結點的前一個結點和後一個結點。在雙向鏈表中由任何一個結點都很容易找到其前面的結點和後面的結點，而不需要在上述的插入(及刪除)操作中由頭結點開始尋找。
簡單實現為：
typedef struct node
{ DATATYPE info；
node *priv, *next;
}DINKLIST；
循環鏈表
單向鏈表的最後一個結點的指針域為空（NULL）。如果將這個指針裡利用起來，以指向單向鏈表的第一個結點，就組成一個單向循環鏈表。
這裡有一篇好文章：myweb.yzu.edu.cn/...ao.htm
參考資料：myweb.yzu.edu.cn/...ao.htm
創建鏈表
/*creat a list*/
#include "stdlib.h"
#include "stdio.h"
#include "conio.h"
struct list
{
int data;
struct list *next;
};
typedef struct list node;
typedef node *link;
void main()
{
link ptr,head;
int num,i;
ptr=(link)malloc(sizeof(node));
ptr=head;
printf("please input 5 numbers==>\n");
for(i=0;i<=4;i++)
{
scanf("%d",&num);
ptr->data=num;
ptr->next=(link)malloc(sizeof(node));
if(i==4) ptr->next=NULL;
else ptr=ptr->next;
}
ptr=head;
while(ptr!=NULL)
{
printf("The value is ==>%d\n",ptr->data);
ptr=ptr->next;
}
getch();
}
