欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C#中LinkedList<T>的存儲結(jié)構(gòu)詳解

 更新時間:2023年12月06日 08:53:43   作者:彭-澤  
這篇文章主要介紹了深度解析C#中LinkedList<T>的存儲結(jié)構(gòu),本文將從鏈表的基礎(chǔ)特性、C#中LinkedList的底層實現(xiàn)邏輯,.NET的不同版本對于Queue的不同實現(xiàn)方式的原因分析等幾個視角進行簡單的解讀,需要的朋友可以參考下

本文承接前面的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&lt;T&gt;的存儲結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)C# LinkedList&lt;T&gt;存儲結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評論