C#集合之鏈表的用法
LinkedList<T>是一個雙向鏈表，其元素會指向它前面和后面的元素。這樣，通過移動到下一個元素可以正向遍歷鏈表，通過移動到前一個元素可以反向遍歷鏈表。
鏈表在存儲元素時，不僅要存儲元素的值，還必須存儲每個元素的下一個元素和上一個元素的信息。這就是LinkedList<T>包含LinkedListNode<T>類型的元素的原因。使用LinkedListNode<T>，可以獲得列表中的下一個和上一個元素。LinkedListNode<T>定義了屬性List，Next，Previous和Value。List屬性返回與節(jié)點相關的LinkedList<T>對象。Next和Previous屬性用于遍歷鏈表，訪問當前節(jié)點之后和之前的節(jié)點。Value屬性返回與節(jié)點相關的元素，其類型是T。
鏈表的優(yōu)點是，如果將元素插入到列表的中間位置，使用鏈表就會很快。在插入一個元素時，秩序啊喲修改上一個元素的Next引用和下一個元素的Previous引用，使它們引用所插入的元素。在List<T>（http://chabaoo.cn/article/244084.htm）中，插入一個元素，需要移動該元素后面的所以元素。
鏈表的缺點是，鏈表元素只能一個接一個的訪問，這需要較長時間來查找位于鏈表中間或尾部的元素。
LinkedList<T>類定義的成員可以訪問鏈表中的第一個和最后一個元素（First和Last）；
在指定位置插入元素：AddAfter()，AddFirst()和AddLast()；
刪除指定位置的元素：Remove()，RemoveFirst()，RemoveLast()；
搜索：Find()，F(xiàn)indLast()。
下面用一個例子演示鏈表。在鏈表中，文檔按照優(yōu)先級來排序。如果多個文檔的優(yōu)先級相同，這些元素就按照文檔的插入時間來排序：
PriorityDocumentManager類使用一個鏈表LinkedList<Document> documentList和一個列表List<LinkedListNode<Document>> priorityNodes，鏈表包含Document對象，Document對象包含文檔的標題和優(yōu)先級。列表List<LinkedListNode<Document>> priorityNodes應最多包含10個元素，每個元素分別是引用每個優(yōu)先級的最后一個文檔對象。
public class PriorityDocumentManager
{
private readonly LinkedList<Document> documentList;
// priorities 0.9
private readonly List<LinkedListNode<Document>> priorityNodes;
public PriorityDocumentManager()
{
documentList = new LinkedList<Document>();
priorityNodes = new List<LinkedListNode<Document>>(10);
for (int i = 0; i < 10; i++)
{
priorityNodes.Add(new LinkedListNode<Document>(null));
}
}
public void AddDocument(Document d)
{
//Contract.Requires<ArgumentNullException>(d != null, "argument d must not be null");
if (d == null) throw new ArgumentNullException("d");
AddDocumentToPriorityNode(d, d.Priority);
}
private void AddDocumentToPriorityNode(Document doc, int priority)
{
if (priority > 9 || priority < 0)
throw new ArgumentException("Priority must be between 0 and 9");
//檢查優(yōu)先級列表priorityNodes中是否有priority這個優(yōu)先級
if (priorityNodes[priority].Value == null)
{
//如果沒有，遞減優(yōu)先級值，遞歸AddDocumentToPriorityNode方法，檢查是否有低一級的優(yōu)先級
--priority;
if (priority >= 0)
{
AddDocumentToPriorityNode(doc, priority);
}
else //如果已經(jīng)沒有更低的優(yōu)先級時，就直接在鏈表中添加該節(jié)點，并將這個節(jié)點添加到優(yōu)先級列表
{
documentList.AddLast(doc);
priorityNodes[doc.Priority] = documentList.Last;
}
return;
}
else //優(yōu)先級列表priorityNodes中有priority這個優(yōu)先級
{
LinkedListNode<Document> prioNode = priorityNodes[priority];
//區(qū)分優(yōu)先級列表priorityNodes存在這個指定的優(yōu)先級值的節(jié)點，還是存在較低的優(yōu)先級值的節(jié)點
if (priority == doc.Priority)
// 如果存在這個指定的優(yōu)先級值的節(jié)點
{
//將這個節(jié)點添加到鏈表
documentList.AddAfter(prioNode, doc);
// 將這個節(jié)點賦予優(yōu)先級列表中的這個優(yōu)先級值的節(jié)點，因為優(yōu)先級節(jié)點總是引用指定優(yōu)先級節(jié)點的最后一個文檔
priorityNodes[doc.Priority] = prioNode.Next;
}
else //如果存在較低的優(yōu)先級值的節(jié)點
{
//在鏈表中找到這個較低優(yōu)先級的第一個節(jié)點，把要添加的節(jié)點放到它前面
LinkedListNode<Document> firstPrioNode = prioNode;
//通過循環(huán)，使用Previous找到這個優(yōu)先級的第一個節(jié)點
while (firstPrioNode.Previous != null &&
firstPrioNode.Previous.Value.Priority == prioNode.Value.Priority)
{
firstPrioNode = prioNode.Previous;
prioNode = firstPrioNode;
}
documentList.AddBefore(firstPrioNode, doc);
// 設置一個新的優(yōu)先級節(jié)點
priorityNodes[doc.Priority] = firstPrioNode.Previous;
}
}
}
public void DisplayAllNodes()
{
foreach (Document doc in documentList)
{
Console.WriteLine("priority: {0}, title {1}", doc.Priority, doc.Title);
}
}
// returns the document with the highest priority
// (that's first in the linked list)
public Document GetDocument()
{
Document doc = documentList.First.Value;
documentList.RemoveFirst();
return doc;
}
}
//存儲在鏈表中的元素是Document類型
public class Document
{
public string Title { get; private set; }
public string Content { get; private set; }
public byte Priority { get; private set; }
public Document(string title, string content, byte priority)
{
this.Title = title;
this.Content = content;
this.Priority = priority;
}
}客戶端代碼：
static void Main()
{
PriorityDocumentManager pdm = new PriorityDocumentManager();
pdm.AddDocument(new Document("one", "Sample", 8));
pdm.AddDocument(new Document("two", "Sample", 3));
pdm.AddDocument(new Document("three", "Sample", 4));
pdm.AddDocument(new Document("four", "Sample", 8));
pdm.AddDocument(new Document("five", "Sample", 1));
pdm.AddDocument(new Document("six", "Sample", 9));
pdm.AddDocument(new Document("seven", "Sample", 1));
pdm.AddDocument(new Document("eight", "Sample", 1));
pdm.DisplayAllNodes();
Console.ReadKey();
}到此這篇關于C#集合之鏈表的文章就介紹到這了。希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
Unity報錯InvalidOperationException: out of sync的解決
今天在做個東西，發(fā)現(xiàn)報錯，特此來記錄一下，本文介紹了Unity報錯InvalidOperationException: out of sync的解決，感興趣的可以了解一下2021-05-05
這篇文章主要介紹了C#中Winfrom默認輸入法的設置方法,以實例形式較為詳細的分析了C#中輸入法設置的相關技巧,需要的朋友可以參考下2015-05-05
這篇文章主要介紹了C#實現(xiàn)過濾html標簽并保留a標簽的方法,文中的自定義函數(shù)采用正則過濾實現(xiàn)了該功能,是非常實用的技巧,需要的朋友可以參考下2014-09-09
這篇文章主要介紹了詳解C#如何讀寫config配置文件，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-12-12
這篇文章主要為大家詳細介紹了C#實現(xiàn)簡單打字游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-05-05
這篇文章主要介紹了c# 循環(huán)語句的使用方法，文中代碼非常詳細，供大家參考和學習，感興趣的朋友可以了解下2020-06-06
本文是利用C#實現(xiàn)連連看的小例子，使用線程thread實現(xiàn)后臺運行時間控制，實現(xiàn)代碼簡單易懂，非常不錯，具有參考借鑒價值，需要的朋友參考下吧2017-07-07
這篇文章主要介紹了C# 使用Proxy代理請求資源的方法步驟，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-03-03
區(qū)位碼是一個4位的十進制數(shù),每個區(qū)位碼都對應著一個唯一的漢字,區(qū)位碼的前兩位叫做區(qū)碼,后兩位叫做位碼,下面我們就來看看如何使用C#實現(xiàn)漢字轉區(qū)位碼吧2024-01-01
Unity實現(xiàn)已知落點和速度自動計算發(fā)射角度
這篇文章主要為大家詳細介紹了Unity實現(xiàn)已知落點和速度自動計算發(fā)射角度，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02