深度解析C#中LinkedList<T>的儲存結構

2023-12-05 15:00:45

  本文承接前面的3篇有關C#的資料結構分析的文章,對於C#有關資料結構分析還有一篇就要暫時結束了,這個系列主要從Array、List、Dictionary、LinkedList、 SortedSet等5中不同類型進行介紹和分析。廢話不多說,接下來我們來最後看一下這個系列的最後一種資料型別"連結串列"。

  提到連結串列這個資料結構可能大部分同學都不會感到陌生,但是在.NET中使用LinkedList  這個集合的同學可能就不會很多,因為絕大部分的場景中大部分同學會直接使用List、Dictionary資料結構,這次我們就來藉助本文對.NET的LinkedList集合進行一個全面的瞭解。

  本文將從連結串列的基礎特性、C#中LinkedList的底層實現邏輯,.NET的不同版本對於Queue的不同實現方式的原因分析等幾個視角進行簡單的解讀。

一、連結串列的基礎特性

   陣列需要一塊連續的記憶體空間來儲存,對記憶體的要求比較高。連結串列並不需要一塊連續的記憶體空間,通過「指標」將一組零散的記憶體塊串聯起來使用。連結串列的節點可以動態分配記憶體,使得連結串列的大小可以根據需要動態變化,而不受固定的記憶體大小的限制。特別是在需要頻繁的插入和刪除操作時,連結串列相比於陣列具有更好的性能。最常見的連結串列結構分別是:單連結串列、雙向連結串列和迴圈連結串列。
    1、連結串列的基本單元是節點,每個節點包含兩個部分:
      (1)、資料(Data):儲存節點所包含的資訊。
      (2)、參照(Next):指向下一個節點的參照,在雙向連結串列中,包含指向前一個節點的參照。
    2、連結串列的基本型別,主要包含三種型別:
      (1)、單連結串列(Singly Linked List):每個節點只包含一個指向下一個節點的參照。
        (a)、【時間複雜度】頭部插入/刪除:O(1);尾部插入:O(n) ;中間插入/刪除:O(n) 。
        (b)、【時間複雜度】按值查詢:O(n) (需要遍歷整個連結串列);按索引查詢:O(n) 。
        (c)、【空間複雜度】插入和刪除:O(1);查詢:O(1)。
      (2)、雙連結串列(Doubly Linked List):每個節點包含兩個參照,一個指向下一個節點,一個指向前一個節點。
        (a)、【時間複雜度】頭部插入/刪除:O(1);尾部插入/刪除:O(1);中間插入/刪除:O(n) 。
        (b)、【時間複雜度】按值查詢:O(n) ;按索引查詢:O(n) 。
        (c)、【空間複雜度】O(n)。
      (3)、迴圈連結串列: 尾節點的參照指向頭節點,形成一個閉環。
        (a)、【時間複雜度】頭部插入/刪除:O(1);尾部插入/刪除:O(1);中間插入/刪除:O(n) 。
        (b)、【時間複雜度】按值查詢:O(n) ;按索引查詢:O(n) 。
        (c)、【空間複雜度】O(n)。

   以上簡單的介紹了連結串列的基礎特性、分類、對應的時間複雜度和空間複雜度,雙連結串列雖然比較耗費記憶體,但是其在插入、刪除、有序連結串列查詢方面相對於單鏈表有明顯的優先,這一點充分的體現了演演算法上的"用空間換時間"的設計思想。

二、LinkedList資料儲存

   LinkedList 是 C# 中提供的一個雙向連結串列(doubly linked list)實現,用於儲存元素。雙向連結串列的每個節點都包含對前一個節點和後一個節點的參照,這種結構使得在連結串列中的兩個方向上進行遍歷和操作更為方便。

   1、節點結構

 1     public sealed class LinkedListNode<T>
 2     {
 3         internal LinkedList<T>? list;
 4         internal LinkedListNode<T>? next;
 5         internal LinkedListNode<T>? prev;
 6         internal T item;
 7         ...
 8         public LinkedListNode(T value)
 9         {
10             Value = value;
11             Previous = null;
12             Next = null;
13         }
14     }

  以上的程式碼展示了在C#的 LinkedList的節點的儲存結構,表示雙向連結串列中的一個節點。 LinkedList 中的每個節點都是一個包含元素值和兩個參照的對象。list是一個對包含該節點的 LinkedList 的參照。這個參照使得節點能夠存取連結串列的一些資訊,例如頭節點、尾節點等。next是一個對下一個節點的參照。prev是一個對前一個節點的參照。item儲存節點的值。

  其實看到這個地方,可能有部分同學會產生疑問,為什麼這個節點的資料結構不設計為"結構體",而是設計為一個類,結構體在記憶體佔用方面更有優勢。在這裡為什麼設計為,可能有以下幾種綜合考慮。

    1、參照語意:型別的範例具有參照語意,當傳遞或賦值物件時,傳遞或賦值的是物件的參照,同一物件的修改在所有參照該物件都是可見的。

    2、複雜性和生命週期:如果型別具有較複雜的生命週期或包含對其他資源(如其他物件、檔案控制程式碼等)的參照,通常會選擇類而不是結構體。結構體適用於輕量級、簡單的值型別,而類則更適合處理更復雜、具有參照語意的情況。

    3、可空性:類可以使用 null 表示空參照,結構體不能。

    4、效能和拷貝開銷:結構體通常會被複制,類則是通過參照傳遞。

  對於以上的結構設計複雜度並不高,我們從整體的設計視角考慮這個結構設計為"結構體"和"類",哪一種更加有優勢,我們在以後的系統開發過程中,也需要綜合去思考,沒有一種結構是完美的,每一種結構都有其針對性的優勢。

  2、連結串列頭和尾

1 public class LinkedList<T> : ICollection<T>, ...
2 {
3     public LinkedListNode<T> First { get; }
4     public LinkedListNode<T> Last { get; }
5     ...
6 }
  LinkedList 本身維護了對連結串列頭和尾的參照,分別指向第一個節點(頭節點)和最後一個節點(尾節點)。通過將連結串列的節點(LinkedListNode)作為LinkedList 類的私有成員,可以隱藏連結串列節點的實現細節,提供更好的封裝性。外部使用者只需關注連結串列的公共介面而不需要了解節點的具體結構。並且可以更容易地擴充套件和維護連結串列的功能、可以控制對節點的存取許可權、對連結串列的操作會影響到同一個連結串列的所有參照、可以表示空連結串列等優勢。

三、LinkedList資料讀寫

  上文中我看分析了連結串列的儲存結構LinkedListNode和LinkedList。接下來,我們再來看一下連結串列LinkedList元素的維護和查詢等基礎操作的實現邏輯。首先我們來看一下元素的新增操作,Add()方法用於將一個元素新增到集合中,其內部的核心實現方法為AddLast(),我們接下來具體看一下這個方法的內部實現。【原始碼進行了部分刪減】。

 1         public LinkedListNode<T> AddLast(T value)
 2         {
 3             LinkedListNode<T> result = new LinkedListNode<T>(this, value);
 4             
 5             //區分連結串列為空和非空的場景
 6             if (head == null)
 7             {
 8                 InternalInsertNodeToEmptyList(result);
 9             }
10             else
11             {
12                 InternalInsertNodeBefore(head, result);
13             }
14             return result;
15         }

  以上程式碼展示了AddLast()的實現程式碼,這個方法是在雙向連結串列的末尾新增一個新節點的操作,並根據連結串列是否為空採取不同的插入策略,確保插入操作的有效性,並返回了對新插入節點的參照。這裡做為空和非空的場景區分是因為在雙向連結串列中,頭節點 head 的前一個節點是尾節點,而尾節點的下一個節點是頭節點。因此,在連結串列為空的情況下,頭節點即是尾節點,直接插入新節點即可。而在連結串列不為空的情況下,需要在頭節點之前插入新節點,以保持連結串列的首尾相連。接下來我們分別來看一下InternalInsertNodeToEmptyList()和InternalInsertNodeBefore()方法。

 1         private void InternalInsertNodeToEmptyList(LinkedListNode<T> newNode)
 2         {
 3             //用於確保在呼叫此方法時連結串列必須為空。
 4             Debug.Assert(head == null && count == 0, "LinkedList must be empty when this method is called!");
 5             
 6             //將新節點的 next 指向自身
 7             newNode.next = newNode;  
 8             
 9             //將新節點的 prev 指向自身
10             newNode.prev = newNode; 
11              
12             //將連結串列的頭節點指向新節點
13             head = newNode; 
14               
15             //增加連結串列的版本號       
16             version++;
17                   
18             //增加連結串列中節點的數量         
19             count++;                 
20         }

  InternalInsertNodeToEmptyList()實現了在空連結串列中插入新節點的邏輯。在空連結串列中,新節點是唯一的節點,因此它的 next和prev都指向自身。新節點同時是頭節點和尾節點。

 1         private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)
 2         {
 3             //新節點newNode的next參照指向目標節點node,
 4             //確保新節點newNode的next指向原來在連結串列中的位置。
 5             newNode.next = node;
 6             
 7             //新節點newNode的prev參照指向目標節點node的前一個節點,
 8             //在插入操作中保持連結串列的連線關係,確保newNode的前一個節點正確。
 9             newNode.prev = node.prev;
10             
11             //目標節點node前一個節點的next參照指向新節點newNode,新節點newNode插入完成
12             node.prev!.next = newNode;
13             
14             //目標節點node的prev參照指向新節點newNode,
15             //連結串列中目標節點node的前一個節點變成了新插入的節點newNode。
16             node.prev = newNode;
17             
18             //用於追蹤連結串列的結構變化,通過每次修改連結串列時增加 
19             //version的值,可以在迭代過程中檢測到對連結串列的並行修改。
20             version++;
21             count++;
22         }

  InternalInsertNodeBefore()用於實現連結串列中在指定節點前插入新節點,保證了插入操作的正確性和一致性,確保連結串列的連線關係和節點計數正確地維護。上面的代碼已經做了邏輯說明。node.prev!.next = newNode;中的!確保在連結串列中插入新節點時,前一個節點不為 null,以防止潛在的空參照異常。版本號的增加是為了在並行操作中提供一種機制,使得在迭代過程中能夠檢測到連結串列的結構變化。這對於多執行緒環境下的連結串列操作是一種常見的實踐,以避免潛在的並行問題。

  上面我們介紹了LinkedList 的InternalInsertNodeToEmptyList()和InternalInsertNodeBefore()方法,用於向連結串列插入元素。接下來,我們再來具體看看連結串列的元素查詢的實現邏輯,LinkedList 實現元素的方法是Find()。

 1         public LinkedListNode<T>? Find(T value)
 2         {
 3             LinkedListNode<T>? node = head;
 4             EqualityComparer<T> c = EqualityComparer<T>.Default;
 5             if (node != null)
 6             {
 7                 if (value != null)
 8                 {
 9                      // 查詢非空值的節點
10                     do
11                     {
12                         if (c.Equals(node!.item, value))
13                         {
14                             return node;
15                         }
16                         node = node.next;
17                     } while (node != head);
18                 }
19                 else
20                 {
21                     // 查詢空值的節點
22                     do
23                     {
24                         if (node!.item == null)
25                         {
26                             return node;
27                         }
28                         node = node.next;
29                     } while (node != head);
30                 }
31             }
32             // 未找到節點
33             return null;
34         }

  通過迴圈遍歷連結串列中的每個節點,根據節點的值與目標值的比較,找到匹配的節點並返回。在連結串列中可能存在包含 null 值的節點,也可能存在包含非空值的節點,而這兩種情況需要採用不同的比較方式。LinkedListNode? node = head; 初始化一個節點參照 node,開始時指向連結串列的頭節點head。使用了do-while 迴圈確保至少執行一次,即使連結串列為空。為了防止潛在的空參照異常,使用了! 操作符來斷言節點 node 不為 null。Find()方法對於連結串列中值的查詢的時間複雜度是O(n)。

  上面介紹了連結串列元素的查詢實現邏輯,接下來我們看一下連結串列元素的移除操作,在InternalRemoveNode()方法中實現。

 1         internal void InternalRemoveNode(LinkedListNode<T> node)
 2         {
 3             if (node.next == node)
 4             {
 5                 //將連結串列頭head 設為null,表示連結串列為空。
 6                 head = null;
 7             }
 8             else
 9             {
10                 //將目標節點node後一個節點的prev參照指向目標節點node的前一個節點。
11                 node.next!.prev = node.prev;
12                 
13                 //將目標節點node前一個節點的next參照指向目標節點node的後一個節點。
14                 node.prev!.next = node.next;
15                 
16                 if (head == node)
17                 {
18                     //如果目標節點node是連結串列頭節點head,則將連結串列頭head設為目標節點node的下一個節點。
19                     head = node.next;
20                 }
21             }
22             node.Invalidate();
23             count--;
24             version++;
25         }

  在雙向連結串列中刪除指定節點node,首先判斷連結串列中是否只有一個節點。如果連結串列只有一個節點,那麼刪除這個節點後連結串列就為空。呼叫 Invalidate 方法,用於清除節點的 list、prev 和 next 參照,使節點脫離連結串列。version++增加連結串列的版本號,用於在並行迭代過程中檢測連結串列結構的變化。

  本節中主要介紹了連結串列的元素插入、元素的查詢、元素的移除等操作,在不同的場景中,其實現的方式都存在著不同,在C#內部維護的連結串列結構相對簡化,沒有對其內部進行很強的優化,因此我們在實際的專案中對於連結串列的應用時,需要充分的分析使用的場景訴求進行調整優化。

四、Queue中連結串列與陣列的實現對比

  在整個.NET Core的資料結構體系中,陣列佔據了絕大部分的應用場景,對於連結串列的應用場景相對較少,但是連結串列也有其獨特的結構,適用於對應的場景中。其實在 .NET Framework版本中,Queue 的底層實現確實使用了連結串列,而 Stack 的實現通常使用了動態陣列。在當前.NET Core版本中,Queue 底層實現已經修改為基於Array陣列來實現。對於Queue選擇連結串列還是陣列的底層實現方案,各有優劣勢。我們藉助一下.NET在對Queue的實現方式上的不同,來對比一下連結串列與陣列的選擇上的優劣勢分析。

  1、Queue使用連結串列的優劣勢

    1、使用連結串列的好處:
      (1)、高效的插入和刪除操作:在隊尾和隊頭進行插入和刪除操作更為高效,符合佇列的典型操作。
      (2)、不需要連續記憶體:連結串列不要求元素在記憶體中是連續儲存的,這使得佇列可以更靈活地分配和釋放記憶體。
      (3)、適用於頻繁的入隊和出隊操作:連結串列在動態增長和縮減時的效能表現更好,適用於佇列中頻繁進行入隊和出隊操作的場景。
    2、使用連結串列的劣勢:
      (1)、記憶體開銷較大:每個節點需要額外的記憶體空間儲存指向下一個節點的參照,可能會導致相對較大的記憶體開銷。
      (2)、隨機存取效能差:連結串列不支援直接通過索引進行隨機存取。

  2、Queue使用陣列的優劣勢

    1、使用陣列的優勢:
      (1)、隨機存取效能:陣列提供了O(1)時間複雜度的隨機存取,連結串列需要按順序遍歷到目標位置。
      (2)、快取友好性:陣列在記憶體中是連續儲存的,連結串列節點的儲存是分散的。
      (3)、空間效率:陣列不需要額外的指向下一個節點的參照,具有更小的記憶體開銷。
      (4)、適用於特定存取模式:對於隨機存取而非插入/刪除操作,選擇陣列作為底層實現可能更合適。
    2、使用陣列的劣勢:
      (1)、插入和刪除效能較差:陣列在中間插入或刪除元素的效能較差,因為需要移動元素以保持陣列的順序。
      (2)、動態擴充套件的開銷:如果佇列的大小會動態變化,陣列在動態擴充套件時可能會涉及到重新分配記憶體、複製元素的開銷影響效能。
      (3)、大佇列的管理:對於大的佇列,如果需要頻繁進行動態擴充套件,可能會面臨記憶體管理的挑戰。
      (4)、不適用於特定插入模式:如果主要操作是頻繁的插入和刪除而不是隨機存取,選擇陣列作為底層實現可能不是最佳選擇。

五、場景應用

  文章開頭介紹了連結串列的基礎特性,基於連結串列的基礎特性來展開分析C#的LinkedList結構,重點說明了LinkedList的元素插入、查詢、移除和儲存物件。連結串列在實際的應用中比較廣泛,尤其是在快取的處理方面。快取是一種提高資料讀取效能的技術,在硬體設計、軟體開發中都有著非常廣泛的應用,比如常見的 CPU 快取、資料庫快取、瀏覽器快取等等。快取的大小有限,當快取被用滿時,哪些資料應該被清理出去,哪些資料應該被保留?這就需要快取淘汰策略來決定。常見的策略有三種:先進先出策略 FIFO(First In,FirstOut)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(LeastRecently Used)。

  這裡我們以簡單實現方式說明一下LRU快取的實現邏輯。

    1、 如果此資料之前已經被快取在連結串列中了,則遍歷得到這個資料對應的結點,並將其從原來的位置刪除,然後再插入到連結串列的頭部。
    2.、如果此資料沒有在快取連結串列中,則分為兩種情況:
      (1)、如果此時快取未滿,則將此結點直接插入到連結串列的頭部;
      (2)、如果此時快取已滿,則連結串列尾結點刪除,將新的資料結點插入連結串列的頭部。
  對於連結串列的基礎應用場景中如:單連結串列反轉;連結串列中環的檢測;有序的連結串列合併等較為常用的演演算法。
     以上內容是對C#中LinkedList的儲存結構的簡單介紹,如錯漏的地方,還望指正。