C#集合本質之鏈表的用法詳解

第C#集合本質之鏈表的用法詳解鏈表的由來和定義

在現實生活中，我們把不同的商品放在一個購物車中。而在面向對象的世界里，有時候，也需要把不同類型的數據放到一起，組成一個集合。集合中的元素并不是彼此孤立的，在C#中，如何表達集合元素間的關系呢？

借助自引用類可以確立集合元素間的關系。比如有這樣一個自引用類：

publicclassNode

publicintData{get;set;}

publicNodeNext{get;set;}

publicNode(intdataValue)

}

Node類的最大特點是：存在一個Node類型的屬性，這個屬性指向Node的另一個實例，Next屬性也稱為引用鏈。放到集合的場景中來說就是：把多個Node實例放到一個集合中，每一個Node實例包含一個Next屬性指向下一個Node實例。而該集合中的最后一個Node實例會指向null。用圖表示就是：

鏈表就是自引用類對象的線性集合，即序列。

由于每個自引用對象是由引用鏈鏈接起來，所以叫鏈表。堆棧與隊列是約束版的鏈表，而二叉查找數是非線性數據結構。

鏈表的節(jié)點或元素雖然在邏輯上是連續(xù)的、線性的，當其內存不是連續(xù)存儲的；數組元素在內存中是連續(xù)的，所以我們才可以通過索引來訪問數組元素。

創(chuàng)建一個單向鏈表

首先創(chuàng)建一個節(jié)點，是一個自引用類：

namespaceLinkedListLibrary

publicclassListNode

//當前節(jié)點對象

publicobjectData{get;privateset;}

//Next屬性也稱為鏈，指向另一個ListNode對象實例，這樣就把2個ListNode對象實例鏈接起來了

publicListNodeNext{get;set;}

publicListNode(objectdataValue):this(dataValue,null)

publicListNode(objectdataValue,ListNodenextNode)

Data=dataValue;

Next=nextNode;

}

再模擬一個鏈表，如下：

namespaceLinkedListLibrary

publicclassList

privateListNodefirstNode;

privateListNodelastNode;

privatestringname;

publicList(stringlistName)

name=listName;

firstNode=lastNode=null;

publicList():this("list"){}

......

//如果第一個節(jié)點是null，那就說明集合為空

publicboolIsEmpty()

returnfirstNode==null;

}

以上，如果第一個節(jié)點為null，那就說明該鏈表為空。List類提供了IsEmpty方法用來判斷鏈表是否為空。List還包含另外5個重要的方法，下面展開來說。

在鏈表的的第一個節(jié)點前插入。

//在最前面插入元素、節(jié)點

publicvoidInsertAtFront(objectinsertItem)

if(IsEmpty())//如果集合為空，加進來一個元素，相當于第一個節(jié)點和第二個節(jié)點相同，都是新加的元素

firstNode=lastNode=newListNode(insertItem);

else//如果集合不為空，第一個節(jié)點就是新加的元素,原先的第一個節(jié)點變?yōu)橄乱粋€節(jié)點

firstNode=newListNode(insertItem,firstNode);

}

以上，當集合不為空的情況下，實際上是把新添加的節(jié)點設為第一個節(jié)點，并把新的第一個節(jié)點的引用鏈指向原先的第一個節(jié)點。

在鏈表的最后一個節(jié)點后插入。

publicvoidInsertAtBack(objectinsertItem)

if(IsEmpty())//如果原先集合為空，第一個節(jié)點和最后一個節(jié)點就是新加的節(jié)點

firstNode=lastNode=newListNode(insertItem);

else//如果原先的集合不為空，最后一個節(jié)點的屬性值就是新加的節(jié)點

lastNode=lastNode.Next=newListNode(insertItem);

}

以上，當集合不為空的情況下，實際上是把新添加的節(jié)點設置成最后一個節(jié)點，并把新的最后一個節(jié)點的引用鏈指向null。

移除鏈表最前面的節(jié)點。

//移除最前面的元素、節(jié)點

//即重新設置第一個節(jié)點的Next屬性

publicobjectRemoveFromFront()

if(IsEmpty())

thrownewEmptyListException(name);

//從第一個節(jié)點中取出節(jié)點對象

objectremoveItem=firstNode.Data;

if(firstNode==lastNode)//如果集合中只有一個元素

firstNode=lastNode=null;

else//正常情況下，把firstNode的Next屬性所指向的節(jié)點賦值給第一個節(jié)點

firstNode=firstNode.Next;

returnremoveItem;

}

以上，本質是把原先排在第二位置的節(jié)點設置成第一個節(jié)點。

移除鏈表最后面的節(jié)點。

//移除最后面的元素、節(jié)點

publicobjectRemoveFromBack()

if(IsEmpty())

thrownewEmptyListException();

//從最后一個節(jié)點中獲取節(jié)點對象

objectremoveItem=lastNode.Data;

if(firstNode==lastNode)//如果當前集合只有一個節(jié)點

firstNode=lastNode=null;

else

//先把第一個節(jié)點作為當前節(jié)點

ListNodecurrent=firstNode;

//改變除最后一個節(jié)點之外的節(jié)點的值

while(current.Next!=lastNode)

current=current.Next;

//最后current變成倒數第二個節(jié)點

lastNode=current;

current.Next=null;//最后一個節(jié)點的Next屬性為null，即沒有指向另一個節(jié)點

returnremoveItem;

}

以上，從第一個節(jié)點開始，一直循環(huán)到倒數第二個節(jié)點，current就像一個指針，每指到一個節(jié)點，就把該節(jié)點的下面一個節(jié)點設置為當前節(jié)點。最后，把倒數第二個節(jié)點設置為最后一個節(jié)點。把Current的引用鏈設置為null，讓其能被垃圾回收機制回收。

打印鏈表。

//打印顯示

publicvoidDisplay()

if(IsEmpty())

Console.WriteLine("集合"+name+"為空");

else

Console.WriteLine("集合的名稱是："+name);

//先把第一個節(jié)點作為當前節(jié)點

ListNodecurrent=firstNode;

while(current!=null)

//把當前節(jié)點對象打印出來

Console.Write(current.Data+"");

//把下一個節(jié)點設置為當前節(jié)點

current=current.Next;

Console.WriteLine("\n");

}

以上，從第一個節(jié)點開始，一直循環(huán)到最后一個節(jié)點，current就像一個指針，每打印一個節(jié)點，就把當前節(jié)點設置為下一個節(jié)點，一直循環(huán)下去。

EmptyListException用來拋出鏈表為空的異常。

namespaceLinkedListLibrary

publicclassEmptyListException:Exception

publicEmptyListException():base("當前集合為空"){}

publicEmptyListException(stringname):base("集合"+name+"為空"){}

publicEmptyListException(stringexception,Exceptioninner):base(exception,inner){}

}

客戶端調用：

usingLinkedListLibrary;

namespaceListTest

classProgram

staticvoidMain(string[]args)

Listlist=newList();

boolaBoolean=true;

charaChar='a';

intanInt=12;

stringaStr="hi";

list.InsertAtFront(aBoolean);

list.Display();

list.InsertAtFront(aChar);

list.Display();

list.InsertAtBack(anInt);

list.Display();

list.InsertAtBack(aStr);

list.Display();

objectremoveObject;

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(EmptyListExceptionemptyListException)

Console.Error.WriteLine("\n"+emptyListException);

Console.ReadKey();

}

以上，創(chuàng)建的是單向鏈表，其特點是第一個節(jié)點開始包含引用鏈，每個節(jié)點的引用鏈指向下一個節(jié)點，最后一個節(jié)點的引用鏈為null。單向鏈表只能從一個方向遍歷。

環(huán)形單向鏈表與單向鏈表的區(qū)別是：其最后一個節(jié)點的引用鏈指向第一個節(jié)點。環(huán)形單向鏈表也只能從