C#集合本質之鏈表的用法詳解
鏈表的由來和定義
在現實生活中，我們把不同的商品放在一個購物車中。而在面向對象的世界里，有時候，也需要把不同類型的數據放到一起，組成一個集合。集合中的元素并不是彼此孤立的，在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。用圖表示就是：
鏈表就是自引用類對象的線性集合，即序列。
由于每個自引用對象是由引用鏈鏈接起來，所以叫鏈表。堆棧與隊列是約束版的鏈表，而二叉查找數是非線性數據結構。
鏈表的節(jié)點或元素雖然在邏輯上是連續(xù)的、線性的，當其內存不是連續(xù)存儲的；數組元素在內存中是連續(xù)的，所以我們才可以通過索引來訪問數組元素。
創(chuàng)建一個單向鏈表
首先創(chuàng)建一個節(jié)點，是一個自引用類：
namespace LinkedListLibrary
{
public class ListNode
{
//當前節(jié)點對象
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"){}
......
//如果第一個節(jié)點是null，那就說明集合為空
public bool IsEmpty()
{
return firstNode == null;
}
}
}以上，如果第一個節(jié)點為null，那就說明該鏈表為空。List類提供了IsEmpty方法用來判斷鏈表是否為空。List還包含另外5個重要的方法，下面展開來說。
在鏈表的的第一個節(jié)點前插入。
//在最前面插入元素、節(jié)點
public void InsertAtFront(object insertItem)
{
if (IsEmpty())//如果集合為空，加進來一個元素，相當于第一個節(jié)點和第二個節(jié)點相同，都是新加的元素
{
firstNode = lastNode = new ListNode(insertItem);
}
else //如果集合不為空，第一個節(jié)點就是新加的元素,原先的第一個節(jié)點變?yōu)橄乱粋€節(jié)點
{
firstNode = new ListNode(insertItem, firstNode);
}
}以上，當集合不為空的情況下，實際上是把新添加的節(jié)點設為第一個節(jié)點，并把新的第一個節(jié)點的引用鏈指向原先的第一個節(jié)點。
在鏈表的最后一個節(jié)點后插入。
public void InsertAtBack(object insertItem)
{
if (IsEmpty())//如果原先集合為空，第一個節(jié)點和最后一個節(jié)點就是新加的節(jié)點
{
firstNode = lastNode = new ListNode(insertItem);
}
else//如果原先的集合不為空，最后一個節(jié)點的屬性值就是新加的節(jié)點
{
lastNode = lastNode.Next = new ListNode(insertItem);
}
}以上，當集合不為空的情況下，實際上是把新添加的節(jié)點設置成最后一個節(jié)點，并把新的最后一個節(jié)點的引用鏈指向null。
移除鏈表最前面的節(jié)點。
//移除最前面的元素、節(jié)點
//即重新設置第一個節(jié)點的Next屬性
public object RemoveFromFront()
{
if (IsEmpty())
throw new EmptyListException(name);
//從第一個節(jié)點中取出節(jié)點對象
object removeItem = firstNode.Data;
if (firstNode == lastNode) //如果集合中只有一個元素
{
firstNode = lastNode = null;
}
else //正常情況下，把firstNode的Next屬性所指向的節(jié)點賦值給第一個節(jié)點
{
firstNode = firstNode.Next;
}
return removeItem;
}以上，本質是把原先排在第二位置的節(jié)點設置成第一個節(jié)點。
移除鏈表最后面的節(jié)點。
//移除最后面的元素、節(jié)點
public object RemoveFromBack()
{
if (IsEmpty())
{
throw new EmptyListException();
}
//從最后一個節(jié)點中獲取節(jié)點對象
object removeItem = lastNode.Data;
if (firstNode == lastNode)//如果當前集合只有一個節(jié)點
{
firstNode = lastNode = null;
}
else
{
//先把第一個節(jié)點作為當前節(jié)點
ListNode current = firstNode;
//改變除最后一個節(jié)點之外的節(jié)點的值
while (current.Next != lastNode)
{
current = current.Next;
}
//最后current變成倒數第二個節(jié)點
lastNode = current;
current.Next = null;//最后一個節(jié)點的Next屬性為null，即沒有指向另一個節(jié)點
}
return removeItem;
}以上，從第一個節(jié)點開始，一直循環(huán)到倒數第二個節(jié)點，current就像一個指針，每指到一個節(jié)點，就把該節(jié)點的下面一個節(jié)點設置為當前節(jié)點。最后，把倒數第二個節(jié)點設置為最后一個節(jié)點。 把Current的引用鏈設置為null，讓其能被垃圾回收機制回收。
打印鏈表。
//打印顯示
public void Display()
{
if (IsEmpty())
{
Console.WriteLine("集合" + name + "為空");
}
else
{
Console.WriteLine("集合的名稱是：" + name);
//先把第一個節(jié)點作為當前節(jié)點
ListNode current = 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用來拋出鏈表為空的異常。
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();
}
}
}
其它鏈表
以上，創(chuàng)建的是單向鏈表，其特點是第一個節(jié)點開始包含引用鏈，每個節(jié)點的引用鏈指向下一個節(jié)點，最后一個節(jié)點的引用鏈為null。單向鏈表只能從一個方向遍歷。
環(huán)形單向鏈表與單向鏈表的區(qū)別是：其最后一個節(jié)點的引用鏈指向第一個節(jié)點。環(huán)形單向鏈表也只能從一個方向遍歷，只不過遍歷到最后一個節(jié)點后，又回到第一個節(jié)點重新開始遍歷。
雙向鏈表的第一個節(jié)點只包含指向下一個節(jié)點的引用鏈，最后一個節(jié)點只包含指向上一個節(jié)點的引用鏈，其它節(jié)點同時包含指向前一個節(jié)點和后一個節(jié)點的引用鏈。雙向鏈表支持向前和向后遍歷。
環(huán)形雙向鏈表與雙向鏈表的區(qū)別是：第一個節(jié)點向后引用鏈指向最后一個節(jié)點，而最后一個節(jié)點的向前引用鏈指向第一個節(jié)點。
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對腳本之家的支持。如果你想了解更多相關內容請查看下面相關鏈接
相關文章
這篇文章介紹了C#8.0中的模式匹配，文中通過示例代碼介紹的非常詳細。對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-07-07
.Net又引入了LINQ，于是LINQ to XML也就應運而生，所以在.Net中，不僅可以用W3C XML DOM標準，還可以使用LINQ to XML來操作XML文檔。下面就來簡單介紹一下如何使用LINQ to XML2012-11-11
這篇文章主要介紹了C#設計模式之Facade外觀模式解決天河城購物問題,簡單描述了外觀模式的定義并結合具體實例分析了外觀模式解決購物問題的相關步驟與操作技巧,需要的朋友可以參考下2017-09-09
以下是對使用C#調用Java類的實現方法進行了詳細的介紹，需要的朋友可以過來參考下2013-09-09
這篇文章主要介紹了C#基于cookie實現的購物車功能,結合完整實例形式分析了C#基于cookie創(chuàng)建購物車的具體步驟與相關技巧,需要的朋友可以參考下2015-12-12
這篇文章主要介紹了C#調用Rar文件及獲取Rar返回值的方法,實例分析了C#調用rar文件實現文件的壓縮與解壓相關技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
這篇文章主要給大家介紹了關于SQL Server存儲過程在C#中調用的簡單實現方法，文中通過示例代碼介紹的非常詳細，對大家學習或者使用SQL Server存儲過程具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2020-05-05
簡單C#代碼實現modbus-rtu通訊發(fā)送數據方式
這篇文章主要介紹了簡單C#代碼實現modbus-rtu通訊發(fā)送數據方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01
Dapper類是一個開源的數據庫操作類，下面這篇文章主要給大家介紹了關于如何使用Dapper處理多個結果集與多重映射的相關資料，文中通過示例代碼介紹的非常詳細，需要的朋友可以參考借鑒，下面隨著小編來一起學習學習吧2018-09-09
這篇文章主要介紹了.NET平臺的一種方便快捷的服務注冊方案的相關資料,需要的朋友可以參考下2023-08-08