本文承接前面的3篇有關(guān)C#的數(shù)據(jù)結(jié)構(gòu)分析的文章，對于C#有關(guān)數(shù)據(jù)結(jié)構(gòu)分析還有一篇就要暫時結(jié)束了，這個系列主要從Array、List、Dictionary、LinkedList、 SortedSet等5中不同類型進行介紹和分析。廢話不多說，接下來我們來最后看一下這個系列的最后一種數(shù)據(jù)類型"鏈表"。

　　提到鏈表這個數(shù)據(jù)結(jié)構(gòu)可能大部分同學都不會感到陌生，但是在.NET中使用LinkedList  這個集合的同學可能就不會很多，因為絕大部分的場景中大部分同學會直接使用List、Dictionary數(shù)據(jù)結(jié)構(gòu)，這次我們就來借助本文對.NET的LinkedList集合進行一個全面的了解。

　　本文將從鏈表的基礎(chǔ)特性、C#中LinkedList的底層實現(xiàn)邏輯，.NET的不同版本對于Queue的不同實現(xiàn)方式的原因分析等幾個視角進行簡單的解讀。

一、鏈表的基礎(chǔ)特性

　　 數(shù)組需要一塊連續(xù)的內(nèi)存空間來存儲，對內(nèi)存的要求比較高。鏈表并不需要一塊連續(xù)的內(nèi)存空間，通過“指針”將一組零散的內(nèi)存塊串聯(lián)起來使用。鏈表的節(jié)點可以動態(tài)分配內(nèi)存，使得鏈表的大小可以根據(jù)需要動態(tài)變化，而不受固定的內(nèi)存大小的限制。特別是在需要頻繁的插入和刪除操作時，鏈表相比于數(shù)組具有更好的性能。最常見的鏈表結(jié)構(gòu)分別是：單鏈表、雙向鏈表和循環(huán)鏈表。

　　　　1、鏈表的基本單元是節(jié)點，每個節(jié)點包含兩個部分：

　　　　　　(1)、數(shù)據(jù)(Data)：存儲節(jié)點所包含的信息。

　　　　　　(2)、引用(Next)：指向下一個節(jié)點的引用，在雙向鏈表中，包含指向前一個節(jié)點的引用。

　　　　2、鏈表的基本類型，主要包含三種類型：

　　　　　　(1)、單鏈表（Singly Linked List）：每個節(jié)點只包含一個指向下一個節(jié)點的引用。

　　　　　　　　(a)、【時間復(fù)雜度】頭部插入/刪除：O(1)；尾部插入：O(n) ；中間插入/刪除：O(n) 。

　　　　　　　　(b)、【時間復(fù)雜度】按值查找：O(n) （需要遍歷整個鏈表）；按索引查找：O(n) 。

　　　　　　　　(c)、【空間復(fù)雜度】插入和刪除：O(1)；查找：O(1)。

　　　　　　(2)、雙鏈表（Doubly Linked List）：每個節(jié)點包含兩個引用，一個指向下一個節(jié)點，一個指向前一個節(jié)點。

　　　　　　　　(a)、【時間復(fù)雜度】頭部插入/刪除：O(1)；尾部插入/刪除：O(1)；中間插入/刪除：O(n) 。

　　　　　　　　(b)、【時間復(fù)雜度】按值查找：O(n) ；按索引查找：O(n) 。

　　　　　　　　(c)、【空間復(fù)雜度】O(n)。

　　　　　　(3)、循環(huán)鏈表： 尾節(jié)點的引用指向頭節(jié)點，形成一個閉環(huán)。

　　　　　　　　(a)、【時間復(fù)雜度】頭部插入/刪除：O(1)；尾部插入/刪除：O(1)；中間插入/刪除：O(n) 。

　　　　　　　　(b)、【時間復(fù)雜度】按值查找：O(n) ；按索引查找：O(n) 。

　　　　　　　　(c)、【空間復(fù)雜度】O(n)。

　　 以上簡單的介紹了鏈表的基礎(chǔ)特性、分類、對應(yīng)的時間復(fù)雜度和空間復(fù)雜度，雙鏈表雖然比較耗費內(nèi)存，但是其在插入、刪除、有序鏈表查詢方面相對于單鏈表有明顯的優(yōu)先，這一點充分的體現(xiàn)了算法上的"用空間換時間"的設(shè)計思想。

二、LinkedList數(shù)據(jù)存儲

　　 LinkedList 是 C# 中提供的一個雙向鏈表（doubly linked list）實現(xiàn)，用于存儲元素。雙向鏈表的每個節(jié)點都包含對前一個節(jié)點和后一個節(jié)點的引用，這種結(jié)構(gòu)使得在鏈表中的兩個方向上進行遍歷和操作更為方便。

　　　1、節(jié)點結(jié)構(gòu)

public sealed class LinkedListNode<T>
    {
        internal LinkedList<T>? list;
        internal LinkedListNode<T>? next;
        internal LinkedListNode<T>? prev;
        internal T item;
        ...
        public LinkedListNode(T value)
        {
            Value = value;
            Previous = null;
            Next = null;
        }
    }

　　以上的代碼展示了在C#的 LinkedList的節(jié)點的存儲結(jié)構(gòu)，表示雙向鏈表中的一個節(jié)點。 LinkedList 中的每個節(jié)點都是一個包含元素值和兩個引用的對象。list是一個對包含該節(jié)點的 LinkedList 的引用。這個引用使得節(jié)點能夠訪問鏈表的一些信息，例如頭節(jié)點、尾節(jié)點等。next是一個對下一個節(jié)點的引用。prev是一個對前一個節(jié)點的引用。item存儲節(jié)點的值。

　　其實看到這個地方，可能有部分同學會產(chǎn)生疑問，為什么這個節(jié)點的數(shù)據(jù)結(jié)構(gòu)不設(shè)計為"結(jié)構(gòu)體"，而是設(shè)計為一個類，結(jié)構(gòu)體在內(nèi)存占用方面更有優(yōu)勢。在這里為什么設(shè)計為，可能有以下幾種綜合考慮。

　　　　1、引用語義：類型的實例具有引用語義，當傳遞或賦值對象時，傳遞或賦值的是對象的引用，同一對象的修改在所有引用該對象都是可見的。

　　　　2、復(fù)雜性和生命周期：如果類型具有較復(fù)雜的生命周期或包含對其他資源（如其他對象、文件句柄等）的引用，通常會選擇類而不是結(jié)構(gòu)體。結(jié)構(gòu)體適用于輕量級、簡單的值類型，而類則更適合處理更復(fù)雜、具有引用語義的情況。

　　　　3、可空性：類可以使用 null 表示空引用，結(jié)構(gòu)體不能。

　　　　4、性能和拷貝開銷：結(jié)構(gòu)體通常會被復(fù)制，類則是通過引用傳遞。

　　對于以上的結(jié)構(gòu)設(shè)計復(fù)雜度并不高，我們從整體的設(shè)計視角考慮這個結(jié)構(gòu)設(shè)計為"結(jié)構(gòu)體"和"類"，哪一種更加有優(yōu)勢，我們在以后的系統(tǒng)開發(fā)過程中，也需要綜合去思考，沒有一種結(jié)構(gòu)是完美的，每一種結(jié)構(gòu)都有其針對性的優(yōu)勢。

　　2、鏈表頭和尾

public class LinkedList<T> : ICollection<T>, ...
{
    public LinkedListNode<T> First { get; }
    public LinkedListNode<T> Last { get; }
    ...
}

　　LinkedList 本身維護了對鏈表頭和尾的引用，分別指向第一個節(jié)點（頭節(jié)點）和最后一個節(jié)點（尾節(jié)點）。通過將鏈表的節(jié)點（LinkedListNode）作為LinkedList 類的私有成員，可以隱藏鏈表節(jié)點的實現(xiàn)細節(jié)，提供更好的封裝性。外部用戶只需關(guān)注鏈表的公共接口而不需要了解節(jié)點的具體結(jié)構(gòu)。并且可以更容易地擴展和維護鏈表的功能、可以控制對節(jié)點的訪問權(quán)限、對鏈表的操作會影響到同一個鏈表的所有引用、可以表示空鏈表等優(yōu)勢。

三、LinkedList數(shù)據(jù)讀寫

　　上文中我看分析了鏈表的存儲結(jié)構(gòu)LinkedListNode和LinkedList。接下來，我們再來看一下鏈表LinkedList元素的維護和查詢等基礎(chǔ)操作的實現(xiàn)邏輯。首先我們來看一下元素的添加操作，Add()方法用于將一個元素添加到集合中，其內(nèi)部的核心實現(xiàn)方法為AddLast()，我們接下來具體看一下這個方法的內(nèi)部實現(xiàn)?！驹创a進行了部分刪減】。

public LinkedListNode<T> AddLast(T value)
        {
            LinkedListNode<T> result = new LinkedListNode<T>(this, value);
            //區(qū)分鏈表為空和非空的場景
            if (head == null)
            {
                InternalInsertNodeToEmptyList(result);
            }
            else
            {
                InternalInsertNodeBefore(head, result);
            }
            return result;
        }

　　以上代碼展示了AddLast()的實現(xiàn)代碼，這個方法是在雙向鏈表的末尾添加一個新節(jié)點的操作，并根據(jù)鏈表是否為空采取不同的插入策略，確保插入操作的有效性，并返回了對新插入節(jié)點的引用。這里做為空和非空的場景區(qū)分是因為在雙向鏈表中，頭節(jié)點 head 的前一個節(jié)點是尾節(jié)點，而尾節(jié)點的下一個節(jié)點是頭節(jié)點。因此，在鏈表為空的情況下，頭節(jié)點即是尾節(jié)點，直接插入新節(jié)點即可。而在鏈表不為空的情況下，需要在頭節(jié)點之前插入新節(jié)點，以保持鏈表的首尾相連。接下來我們分別來看一下InternalInsertNodeToEmptyList()和InternalInsertNodeBefore()方法。

private void InternalInsertNodeToEmptyList(LinkedListNode<T> newNode)
        {
            //用于確保在調(diào)用此方法時鏈表必須為空。
            Debug.Assert(head == null && count == 0, "LinkedList must be empty when this method is called!");
            //將新節(jié)點的 next 指向自身
            newNode.next = newNode;
            //將新節(jié)點的 prev 指向自身
            newNode.prev = newNode;
            //將鏈表的頭節(jié)點指向新節(jié)點
            head = newNode;
            //增加鏈表的版本號
            version++;
            //增加鏈表中節(jié)點的數(shù)量
            count++;
        }

　　InternalInsertNodeToEmptyList()實現(xiàn)了在空鏈表中插入新節(jié)點的邏輯。在空鏈表中，新節(jié)點是唯一的節(jié)點，因此它的 next和prev都指向自身。新節(jié)點同時是頭節(jié)點和尾節(jié)點。

private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)
        {
            //新節(jié)點newNode的next引用指向目標節(jié)點node，
            //確保新節(jié)點newNode的next指向原來在鏈表中的位置。
            newNode.next = node;
            //新節(jié)點newNode的prev引用指向目標節(jié)點node的前一個節(jié)點，
            //在插入操作中保持鏈表的連接關(guān)系，確保newNode的前一個節(jié)點正確。
            newNode.prev = node.prev;
            //目標節(jié)點node前一個節(jié)點的next引用指向新節(jié)點newNode，新節(jié)點newNode插入完成
            node.prev!.next = newNode;
            //目標節(jié)點node的prev引用指向新節(jié)點newNode，
            //鏈表中目標節(jié)點node的前一個節(jié)點變成了新插入的節(jié)點newNode。
            node.prev = newNode;
            //用于追蹤鏈表的結(jié)構(gòu)變化，通過每次修改鏈表時增加
            //version的值，可以在迭代過程中檢測到對鏈表的并發(fā)修改。
            version++;
            count++;
        }

　　InternalInsertNodeBefore()用于實現(xiàn)鏈表中在指定節(jié)點前插入新節(jié)點,保證了插入操作的正確性和一致性，確保鏈表的連接關(guān)系和節(jié)點計數(shù)正確地維護。上面的代碼已經(jīng)做了邏輯說明。node.prev!.next = newNode;中的!確保在鏈表中插入新節(jié)點時，前一個節(jié)點不為 null，以防止?jié)撛诘目找卯惓?。版本號的增加是為了在并發(fā)操作中提供一種機制，使得在迭代過程中能夠檢測到鏈表的結(jié)構(gòu)變化。這對于多線程環(huán)境下的鏈表操作是一種常見的實踐，以避免潛在的并發(fā)問題。

　　上面我們介紹了LinkedList 的InternalInsertNodeToEmptyList()和InternalInsertNodeBefore()方法，用于向鏈表插入元素。接下來，我們再來具體看看鏈表的元素查詢的實現(xiàn)邏輯，LinkedList 實現(xiàn)元素的方法是Find()。

public LinkedListNode<T>? Find(T value)
        {
            LinkedListNode<T>? node = head;
            EqualityComparer<T> c = EqualityComparer<T>.Default;
            if (node != null)
            {
                if (value != null)
                {
                     // 查找非空值的節(jié)點
                    do
                    {
                        if (c.Equals(node!.item, value))
                        {
                            return node;
                        }
                        node = node.next;
                    } while (node != head);
                }
                else
                {
                    // 查找空值的節(jié)點
                    do
                    {
                        if (node!.item == null)
                        {
                            return node;
                        }
                        node = node.next;
                    } while (node != head);
                }
            }
            // 未找到節(jié)點
            return null;
        }

　　通過循環(huán)遍歷鏈表中的每個節(jié)點，根據(jù)節(jié)點的值與目標值的比較，找到匹配的節(jié)點并返回。在鏈表中可能存在包含 null 值的節(jié)點，也可能存在包含非空值的節(jié)點，而這兩種情況需要采用不同的比較方式。LinkedListNode? node = head; 初始化一個節(jié)點引用 node，開始時指向鏈表的頭節(jié)點head。使用了do-while 循環(huán)確保至少執(zhí)行一次，即使鏈表為空。為了防止?jié)撛诘目找卯惓?，使用? 操作符來斷言節(jié)點 node 不為 null。Find()方法對于鏈表中值的查詢的時間復(fù)雜度是O(n)。

　　上面介紹了鏈表元素的查詢實現(xiàn)邏輯，接下來我們看一下鏈表元素的移除操作，在InternalRemoveNode()方法中實現(xiàn)。

internal void InternalRemoveNode(LinkedListNode<T> node)
        {
            if (node.next == node)
            {
                //將鏈表頭head 設(shè)為null，表示鏈表為空。
                head = null;
            }
            else
            {
                //將目標節(jié)點node后一個節(jié)點的prev引用指向目標節(jié)點node的前一個節(jié)點。
                node.next!.prev = node.prev;
                //將目標節(jié)點node前一個節(jié)點的next引用指向目標節(jié)點node的后一個節(jié)點。
                node.prev!.next = node.next;
                if (head == node)
                {
                    //如果目標節(jié)點node是鏈表頭節(jié)點head，則將鏈表頭head設(shè)為目標節(jié)點node的下一個節(jié)點。
                    head = node.next;
                }
            }
            node.Invalidate();
            count--;
            version++;
        }

　　在雙向鏈表中刪除指定節(jié)點node，首先判斷鏈表中是否只有一個節(jié)點。如果鏈表只有一個節(jié)點，那么刪除這個節(jié)點后鏈表就為空。調(diào)用 Invalidate 方法，用于清除節(jié)點的 list、prev 和 next 引用，使節(jié)點脫離鏈表。version++增加鏈表的版本號，用于在并發(fā)迭代過程中檢測鏈表結(jié)構(gòu)的變化。

　　本節(jié)中主要介紹了鏈表的元素插入、元素的查詢、元素的移除等操作，在不同的場景中，其實現(xiàn)的方式都存在著不同，在C#內(nèi)部維護的鏈表結(jié)構(gòu)相對簡化，沒有對其內(nèi)部進行很強的優(yōu)化，因此我們在實際的項目中對于鏈表的應(yīng)用時，需要充分的分析使用的場景訴求進行調(diào)整優(yōu)化。

四、Queue中鏈表與數(shù)組的實現(xiàn)對比

　　在整個.NET Core的數(shù)據(jù)結(jié)構(gòu)體系中，數(shù)組占據(jù)了絕大部分的應(yīng)用場景，對于鏈表的應(yīng)用場景相對較少，但是鏈表也有其獨特的結(jié)構(gòu)，適用于對應(yīng)的場景中。其實在 .NET Framework版本中，Queue 的底層實現(xiàn)確實使用了鏈表，而 Stack 的實現(xiàn)通常使用了動態(tài)數(shù)組。在當前.NET Core版本中，Queue 底層實現(xiàn)已經(jīng)修改為基于Array數(shù)組來實現(xiàn)。對于Queue選擇鏈表還是數(shù)組的底層實現(xiàn)方案，各有優(yōu)劣勢。我們借助一下.NET在對Queue的實現(xiàn)方式上的不同，來對比一下鏈表與數(shù)組的選擇上的優(yōu)劣勢分析。

　　1、Queue使用鏈表的優(yōu)劣勢

　　　　1、使用鏈表的好處：

　　　　　　(1)、高效的插入和刪除操作：在隊尾和隊頭進行插入和刪除操作更為高效，符合隊列的典型操作。

　　　　　　(2)、不需要連續(xù)內(nèi)存：鏈表不要求元素在內(nèi)存中是連續(xù)存儲的，這使得隊列可以更靈活地分配和釋放內(nèi)存。

　　　　　　(3)、適用于頻繁的入隊和出隊操作：鏈表在動態(tài)增長和縮減時的性能表現(xiàn)更好，適用于隊列中頻繁進行入隊和出隊操作的場景。

　　　　2、使用鏈表的劣勢：

　　　　　　(1)、內(nèi)存開銷較大：每個節(jié)點需要額外的內(nèi)存空間存儲指向下一個節(jié)點的引用，可能會導(dǎo)致相對較大的內(nèi)存開銷。

　　　　　　(2)、隨機訪問性能差：鏈表不支持直接通過索引進行隨機訪問。

　　2、Queue使用數(shù)組的優(yōu)劣勢

　　　　1、使用數(shù)組的優(yōu)勢：

　　　　　　(1)、隨機訪問性能：數(shù)組提供了O(1)時間復(fù)雜度的隨機訪問，鏈表需要按順序遍歷到目標位置。

　　　　　　(2)、緩存友好性：數(shù)組在內(nèi)存中是連續(xù)存儲的，鏈表節(jié)點的存儲是分散的。

　　　　　　(3)、空間效率：數(shù)組不需要額外的指向下一個節(jié)點的引用，具有更小的內(nèi)存開銷。

　　　　　　(4)、適用于特定訪問模式：對于隨機訪問而非插入/刪除操作，選擇數(shù)組作為底層實現(xiàn)可能更合適。

　　　　2、使用數(shù)組的劣勢：

　　　　　　(1)、插入和刪除性能較差：數(shù)組在中間插入或刪除元素的性能較差，因為需要移動元素以保持數(shù)組的順序。

　　　　　　(2)、動態(tài)擴展的開銷：如果隊列的大小會動態(tài)變化，數(shù)組在動態(tài)擴展時可能會涉及到重新分配內(nèi)存、復(fù)制元素的開銷影響性能。

　　　　　　(3)、大隊列的管理：對于大的隊列，如果需要頻繁進行動態(tài)擴展，可能會面臨內(nèi)存管理的挑戰(zhàn)。

　　　　　　(4)、不適用于特定插入模式：如果主要操作是頻繁的插入和刪除而不是隨機訪問，選擇數(shù)組作為底層實現(xiàn)可能不是最佳選擇。

五、場景應(yīng)用

　　文章開頭介紹了鏈表的基礎(chǔ)特性，基于鏈表的基礎(chǔ)特性來展開分析C#的LinkedList結(jié)構(gòu)，重點說明了LinkedList的元素插入、查詢、移除和存儲對象。鏈表在實際的應(yīng)用中比較廣泛，尤其是在緩存的處理方面。緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)，在硬件設(shè)計、軟件開發(fā)中都有著非常廣泛的應(yīng)用，比如常見的 CPU 緩存、數(shù)據(jù)庫緩存、瀏覽器緩存等等。緩存的大小有限，當緩存被用滿時，哪些數(shù)據(jù)應(yīng)該被清理出去，哪些數(shù)據(jù)應(yīng)該被保留？這就需要緩存淘汰策略來決定。常見的策略有三種：先進先出策略 FIFO（First In，F(xiàn)irstOut）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（LeastRecently Used）。

　　這里我們以簡單實現(xiàn)方式說明一下LRU緩存的實現(xiàn)邏輯。

　　　　1、 如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了，則遍歷得到這個數(shù)據(jù)對應(yīng)的結(jié)點，并將其從原來的位置刪除，然后再插入到鏈表的頭部。

　　　　2.、如果此數(shù)據(jù)沒有在緩存鏈表中，則分為兩種情況：

　　　　　　(1)、如果此時緩存未滿，則將此結(jié)點直接插入到鏈表的頭部；

　　　　　　(2)、如果此時緩存已滿，則鏈表尾結(jié)點刪除，將新的數(shù)據(jù)結(jié)點插入鏈表的頭部。

　　對于鏈表的基礎(chǔ)應(yīng)用場景中如：單鏈表反轉(zhuǎn)；鏈表中環(huán)的檢測；有序的鏈表合并等較為常用的算法。

到此這篇關(guān)于深度解析C#中LinkedList<T>的存儲結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)C# LinkedList<T>存儲結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論