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

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

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

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

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

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

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

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

    1、鏈表的基本單元是節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)包含兩個(gè)部分:

      (1)、數(shù)據(jù)(Data):存儲(chǔ)節(jié)點(diǎn)所包含的信息。

      (2)、引用(Next):指向下一個(gè)節(jié)點(diǎn)的引用,在雙向鏈表中,包含指向前一個(gè)節(jié)點(diǎn)的引用。

    2、鏈表的基本類型,主要包含三種類型:

      (1)、單鏈表(Singly Linked List):每個(gè)節(jié)點(diǎn)只包含一個(gè)指向下一個(gè)節(jié)點(diǎn)的引用。

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

        (b)、【時(shí)間復(fù)雜度】按值查找:O(n) (需要遍歷整個(gè)鏈表);按索引查找:O(n) 。

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

      (2)、雙鏈表(Doubly Linked List):每個(gè)節(jié)點(diǎn)包含兩個(gè)引用,一個(gè)指向下一個(gè)節(jié)點(diǎn),一個(gè)指向前一個(gè)節(jié)點(diǎn)。

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

        (b)、【時(shí)間復(fù)雜度】按值查找:O(n) ;按索引查找:O(n) 。

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

      (3)、循環(huán)鏈表: 尾節(jié)點(diǎn)的引用指向頭節(jié)點(diǎn),形成一個(gè)閉環(huán)。

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

        (b)、【時(shí)間復(fù)雜度】按值查找:O(n) ;按索引查找:O(n) 。

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

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

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

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

   1、節(jié)點(diǎn)結(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é)點(diǎn)的存儲(chǔ)結(jié)構(gòu),表示雙向鏈表中的一個(gè)節(jié)點(diǎn)。 LinkedList 中的每個(gè)節(jié)點(diǎn)都是一個(gè)包含元素值和兩個(gè)引用的對(duì)象。list是一個(gè)對(duì)包含該節(jié)點(diǎn)的 LinkedList 的引用。這個(gè)引用使得節(jié)點(diǎn)能夠訪問鏈表的一些信息,例如頭節(jié)點(diǎn)、尾節(jié)點(diǎn)等。next是一個(gè)對(duì)下一個(gè)節(jié)點(diǎn)的引用。prev是一個(gè)對(duì)前一個(gè)節(jié)點(diǎn)的引用。item存儲(chǔ)節(jié)點(diǎn)的值。

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

    1、引用語義:類型的實(shí)例具有引用語義,當(dāng)傳遞或賦值對(duì)象時(shí),傳遞或賦值的是對(duì)象的引用,同一對(duì)象的修改在所有引用該對(duì)象都是可見的。

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

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

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

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

  2、鏈表頭和尾

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

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

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

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

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

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

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

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

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

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

  上面我們介紹了LinkedList 的InternalInsertNodeToEmptyList()和InternalInsertNodeBefore()方法,用于向鏈表插入元素。接下來,我們?cè)賮砭唧w看看鏈表的元素查詢的實(shí)現(xiàn)邏輯,LinkedList 實(shí)現(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é)點(diǎn)
                    do
                    {
                        if (c.Equals(node!.item, value))
                        {
                            return node;
                        }
                        node = node.next;
                    } while (node != head);
                }
                else
                {
                    // 查找空值的節(jié)點(diǎn)
                    do
                    {
                        if (node!.item == null)
                        {
                            return node;
                        }
                        node = node.next;
                    } while (node != head);
                }
            }
            // 未找到節(jié)點(diǎn)
            return null;
        }

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

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

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

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

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

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

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

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

    1、使用鏈表的好處:

      (1)、高效的插入和刪除操作:在隊(duì)尾和隊(duì)頭進(jìn)行插入和刪除操作更為高效,符合隊(duì)列的典型操作。

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

      (3)、適用于頻繁的入隊(duì)和出隊(duì)操作:鏈表在動(dòng)態(tài)增長(zhǎng)和縮減時(shí)的性能表現(xiàn)更好,適用于隊(duì)列中頻繁進(jìn)行入隊(duì)和出隊(duì)操作的場(chǎng)景。

    2、使用鏈表的劣勢(shì):

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

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

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

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

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

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

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

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

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

      (1)、插入和刪除性能較差:數(shù)組在中間插入或刪除元素的性能較差,因?yàn)樾枰苿?dòng)元素以保持?jǐn)?shù)組的順序。

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

      (3)、大隊(duì)列的管理:對(duì)于大的隊(duì)列,如果需要頻繁進(jìn)行動(dòng)態(tài)擴(kuò)展,可能會(huì)面臨內(nèi)存管理的挑戰(zhàn)。

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

五、場(chǎng)景應(yīng)用

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

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

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

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

      (1)、如果此時(shí)緩存未滿,則將此結(jié)點(diǎn)直接插入到鏈表的頭部;

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

  對(duì)于鏈表的基礎(chǔ)應(yīng)用場(chǎng)景中如:?jiǎn)捂湵矸崔D(zhuǎn);鏈表中環(huán)的檢測(cè);有序的鏈表合并等較為常用的算法。

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

相關(guān)文章

最新評(píng)論