快捷導(dǎo)航

C#集合之鏈表的用法

更新時(shí)間：2022年04月12日 08:52:45 作者：Ruby_Lu

這篇文章介紹了C#集合之鏈表的用法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

LinkedList<T>是一個(gè)雙向鏈表，其元素會(huì)指向它前面和后面的元素。這樣，通過(guò)移動(dòng)到下一個(gè)元素可以正向遍歷鏈表，通過(guò)移動(dòng)到前一個(gè)元素可以反向遍歷鏈表。

鏈表在存儲(chǔ)元素時(shí)，不僅要存儲(chǔ)元素的值，還必須存儲(chǔ)每個(gè)元素的下一個(gè)元素和上一個(gè)元素的信息。這就是LinkedList<T>包含LinkedListNode<T>類型的元素的原因。使用LinkedListNode<T>，可以獲得列表中的下一個(gè)和上一個(gè)元素。LinkedListNode<T>定義了屬性List，Next，Previous和Value。List屬性返回與節(jié)點(diǎn)相關(guān)的LinkedList<T>對(duì)象。Next和Previous屬性用于遍歷鏈表，訪問(wèn)當(dāng)前節(jié)點(diǎn)之后和之前的節(jié)點(diǎn)。Value屬性返回與節(jié)點(diǎn)相關(guān)的元素，其類型是T。
鏈表的優(yōu)點(diǎn)是，如果將元素插入到列表的中間位置，使用鏈表就會(huì)很快。在插入一個(gè)元素時(shí)，秩序啊喲修改上一個(gè)元素的Next引用和下一個(gè)元素的Previous引用，使它們引用所插入的元素。在List<T>（http://www.dbjr.com.cn/article/244084.htm）中，插入一個(gè)元素，需要移動(dòng)該元素后面的所以元素。
鏈表的缺點(diǎn)是，鏈表元素只能一個(gè)接一個(gè)的訪問(wèn)，這需要較長(zhǎng)時(shí)間來(lái)查找位于鏈表中間或尾部的元素。
LinkedList<T>類定義的成員可以訪問(wèn)鏈表中的第一個(gè)和最后一個(gè)元素（First和Last）；
在指定位置插入元素：AddAfter()，AddFirst()和AddLast()；
刪除指定位置的元素：Remove()，RemoveFirst()，RemoveLast()；
搜索：Find()，F(xiàn)indLast()。
下面用一個(gè)例子演示鏈表。在鏈表中，文檔按照優(yōu)先級(jí)來(lái)排序。如果多個(gè)文檔的優(yōu)先級(jí)相同，這些元素就按照文檔的插入時(shí)間來(lái)排序：
PriorityDocumentManager類使用一個(gè)鏈表LinkedList<Document> documentList和一個(gè)列表List<LinkedListNode<Document>> priorityNodes，鏈表包含Document對(duì)象，Document對(duì)象包含文檔的標(biāo)題和優(yōu)先級(jí)。列表List<LinkedListNode<Document>> priorityNodes應(yīng)最多包含10個(gè)元素，每個(gè)元素分別是引用每個(gè)優(yōu)先級(jí)的最后一個(gè)文檔對(duì)象。

　　　　　　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)先級(jí)列表priorityNodes中是否有priority這個(gè)優(yōu)先級(jí)
              if (priorityNodes[priority].Value == null)
              {
                //如果沒(méi)有，遞減優(yōu)先級(jí)值，遞歸AddDocumentToPriorityNode方法，檢查是否有低一級(jí)的優(yōu)先級(jí)
                --priority;
                if (priority >= 0)
                {
                  AddDocumentToPriorityNode(doc, priority);
                }
                else //如果已經(jīng)沒(méi)有更低的優(yōu)先級(jí)時(shí)，就直接在鏈表中添加該節(jié)點(diǎn)，并將這個(gè)節(jié)點(diǎn)添加到優(yōu)先級(jí)列表
                {
                  documentList.AddLast(doc);
                  priorityNodes[doc.Priority] = documentList.Last;
                }
                return;
              }
              else //優(yōu)先級(jí)列表priorityNodes中有priority這個(gè)優(yōu)先級(jí)
              {
                LinkedListNode<Document> prioNode = priorityNodes[priority];
                //區(qū)分優(yōu)先級(jí)列表priorityNodes存在這個(gè)指定的優(yōu)先級(jí)值的節(jié)點(diǎn)，還是存在較低的優(yōu)先級(jí)值的節(jié)點(diǎn)
                if (priority == doc.Priority)
                // 如果存在這個(gè)指定的優(yōu)先級(jí)值的節(jié)點(diǎn)
                {
                  //將這個(gè)節(jié)點(diǎn)添加到鏈表
                  documentList.AddAfter(prioNode, doc);

                  // 將這個(gè)節(jié)點(diǎn)賦予優(yōu)先級(jí)列表中的這個(gè)優(yōu)先級(jí)值的節(jié)點(diǎn)，因?yàn)閮?yōu)先級(jí)節(jié)點(diǎn)總是引用指定優(yōu)先級(jí)節(jié)點(diǎn)的最后一個(gè)文檔
                  priorityNodes[doc.Priority] = prioNode.Next;
                }
                else //如果存在較低的優(yōu)先級(jí)值的節(jié)點(diǎn)
                {
                  //在鏈表中找到這個(gè)較低優(yōu)先級(jí)的第一個(gè)節(jié)點(diǎn)，把要添加的節(jié)點(diǎn)放到它前面
                  LinkedListNode<Document> firstPrioNode = prioNode;
                    //通過(guò)循環(huán)，使用Previous找到這個(gè)優(yōu)先級(jí)的第一個(gè)節(jié)點(diǎn)
                  while (firstPrioNode.Previous != null &&
                     firstPrioNode.Previous.Value.Priority == prioNode.Value.Priority)
                  {
                    firstPrioNode = prioNode.Previous;
                    prioNode = firstPrioNode;
                  }

                  documentList.AddBefore(firstPrioNode, doc);

                  // 設(shè)置一個(gè)新的優(yōu)先級(jí)節(jié)點(diǎn)
                  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;
            }

          }

          //存儲(chǔ)在鏈表中的元素是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();

        }

到此這篇關(guān)于C#集合之鏈表的文章就介紹到這了。希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: