C#中LinkedList<T>的存儲(chǔ)結(jié)構(gòu)詳解
本文承接前面的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<T>的存儲(chǔ)結(jié)構(gòu)的文章就介紹到這了,更多相關(guān)C# LinkedList<T>存儲(chǔ)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C# 根據(jù)表格偶數(shù)、奇數(shù)加載不同顏色
這篇文章主要介紹了C# 根據(jù)表格偶數(shù)、奇數(shù)加載不同顏色,需要的朋友可以參考下2017-09-09C# WPF 通過委托實(shí)現(xiàn)多窗口間的傳值的方法
這篇文章主要介紹了C# WPF 通過委托實(shí)現(xiàn)多窗口間的傳值的方法,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-09-09WPF簡(jiǎn)單的數(shù)據(jù)庫查詢實(shí)例
下面小編就為大家分享一篇WPF簡(jiǎn)單的數(shù)據(jù)庫查詢實(shí)例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2017-11-11C#全局熱鍵設(shè)置與窗體熱鍵設(shè)置實(shí)例
這篇文章主要介紹了C#全局熱鍵設(shè)置與窗體熱鍵設(shè)置實(shí)例,對(duì)C#全局熱鍵設(shè)置與窗體熱鍵設(shè)置的實(shí)現(xiàn)方法與具體代碼進(jìn)行了詳細(xì)的介紹,需要的朋友可以參考下2014-10-10Unity Shader實(shí)現(xiàn)2D水流效果
這篇文章主要為大家詳細(xì)介紹了Unity Shader實(shí)現(xiàn)2D水流效果,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2020-05-05C#?將數(shù)據(jù)庫SqlServer數(shù)據(jù)綁定到類中的過程詳解
本文講述的是讀取數(shù)據(jù)庫中數(shù)據(jù)的常用做法,即將數(shù)據(jù)庫中的數(shù)據(jù)綁定到創(chuàng)建的類中,再將類綁定到DataGridView的數(shù)據(jù)源中的做法,對(duì)C#將SqlServer數(shù)據(jù)綁定到類中感興趣的朋友一起看看吧2022-06-06C#實(shí)現(xiàn)程序等待延遲執(zhí)行的方法
這篇文章主要介紹了C#實(shí)現(xiàn)程序等待延遲執(zhí)行的方法,涉及C#動(dòng)態(tài)鏈接庫的使用及延遲的實(shí)現(xiàn)技巧,需要的朋友可以參考下2015-09-09