[資料結構-線性表1.2] 連結串列與 LinkedList<T>(.NET 原始碼學習)

2022-11-08 21:02:28

[資料結構-線性表1.2] 連結串列與 LinkedList<T>

【注:本篇文章原始碼內容較少,分析度較淺,請酌情選擇閱讀】

關鍵詞:連結串列(資料結構)    C#中的連結串列(原始碼)    可空型別與特性(底層原理 原始碼)    迭代器的實現(底層原理)    介面IEqualityCompare<T>(原始碼)    相等判斷(底層原理)

連結串列,一種元素彼此之間具有相關性的資料結構,主要可分為三大類:單向連結串列、雙向連結串列、迴圈連結串列。其由「鏈」和「表」組成,「鏈」指當前元素到其他元素之間的路徑(指標);「表」指當前單元儲存的內容(資料)。本文主要對 C# 中 LinkedList 的原始碼進行簡要分析

【# 請先閱讀注意事項】

【注:

(1)   文章篇幅較長,可直接轉跳至想閱讀的部分。

(2)   以下提到的複雜度僅為演演算法本身,不計入演演算法之外的部分(如,待排序陣列的空間佔用)且時間複雜度為平均時間複雜度。

(3)   除特殊標識外,測試環境與程式碼均為 .NET 6/C# 10。

(4)   預設情況下,所有解釋與用例的目標資料均為升序。

(5)   預設情況下,圖片與文字的關係:圖片下方,是該幅圖片的解釋。

(6)   文末「 [ # … ] 」的部分僅作補充說明,非主題(演演算法)內容,該部分屬於 .NET 底層執行邏輯,有興趣可自行參閱。

(7)   本文內容基本為本人理解所得,可能存在較多錯誤,歡迎指出並提出意見,謝謝。】

一、連結串列概述及常見型別

【注:該部分在網路上已有很多資料,故不作為重點】

陣列作為一個最初的順序儲存方式的資料結構,其可通過索引存取的靈活性,使用為我們 的程式設計帶來了大量的便利。但是,陣列最大的缺點就是:為了保證在儲存空間上的連續性,在插入和刪除時需要移動大量的元素,造成大量的消耗時間,以及高冗餘度。為了避免這樣的問題,因此引入了另一種資料結構連結串列

連結串列通過不連續的儲存方式、動態記憶體大小,以及靈活的指標使用(此處的指標是廣義上的指標,不僅僅只代表 C/C++ 中的指標,還包括一些標記等),巧妙的簡化了上述的缺點。其基本思維是,利用結構體或類的設定,額外開闢出一份記憶體空間去作「表」本身,其內部包含本身的值,以及指向下一個結點的指標,一個個結點通過指標相互串聯,就形成了連結串列。但優化了插入與刪除的額外時間消耗,隨之而來的缺點就是:連結串列不支援索引存取

(一) 單向連結串列

以下僅簡單寫一下基本構成和方法。

—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——

(二) 參照型別

—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——

雖然在之前的文章中提到過,這裡還是再解釋一下即使視窗裡的資訊。此處顯示了兩個地址:一個是 &x 後的地址;另一個時 *&x 後的地址。

對於 C# 而言總會將變數本身儲存在棧中,變數內部的值儲存在相應的位置(值型別在棧中,參照型別在堆/堆疊中)。對於獲取到的第一個地址,是變數在棧中儲存的位置,也就是說:C# 中的 &x 獲取的是變數在棧中的位置

而 *&x 的含義是:解析地址 &x,即讀取其中的值。對於值型別而言,其值就儲存在棧中,因此解析後直接得到對應的值;對於參照型別而言,其值儲存在堆/堆疊中,因此解析後會得到一個堆中的位置,這個位置就是儲存實際值的位置。

二、方法 Equals()

類 Object:

類 RuntimeHelpers:

 

方法 Equals() 最初被定義在類 RuntimeHelpers 中,再由類 Object 與類 ValueType 進行擴充套件,而 C# 中其他所有型別(包括值型別、參照型別、自定義型別)均派生自這兩個類,並重寫了這個方法,因此對於任意一個變數均可使用這個方法且均有各自的比較據

【關於方法 Equals() 的更多說明與應用,請參閱C# 有關List<T>的Contains與Equals方法 - PaperHammer - 部落格園 (cnblogs.com)

小結一

在 C# 中,對於值型別的比較不管是用 「==」 還是 Equals 都是對於其內容的比較,也就是說對於其值的比較,相等則返回 true 不相等則返回 false;

但是對於除 string 型別以外的參照型別  「==」 比較的是物件在棧上的參照是否相同,而 Equals 則比較的是物件在堆上的內容是否相同

三、方法 Comapre()

該方法主要用於字串間的比較,比較的是字串的大小,根據字元對應的 ASCII 碼進行比較

對於 Compare(s1, s2):s1 == s2 返回 0;s1 > s2 返回 1;s1 < s2 返回 -1。

四、泛型型別 EqualityCompare<T>

該類是一個抽象類,位於程式集 CoreLib.dll 中的 名稱空間 System.Collections.Generic

包含 8 個方法,一個屬性。

—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——

此處主要關注方法 IEqualityComparer.Equals(object x, object y)

其實該方法的比較依舊主要過運運算元 「==」 完成。

  • Line 82:當兩個物件不相等且均不為空時,在確保二者為相同型別的情況下,將其轉換為各具體型別,按照具體型別的比較規則進行比較。

總結

對於比較,其實並不複雜,只需要區分開值型別與參照型別的比較規則就可以。雖然有許多工具都可以用來比較,但其比較的本質依舊是不變的。