【注:本篇文章原始碼內容較少,分析度較淺,請酌情選擇閱讀】
關鍵詞:連結串列(資料結構) 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,即讀取其中的值。對於值型別而言,其值就儲存在棧中,因此解析後直接得到對應的值;對於參照型別而言,其值儲存在堆/堆疊中,因此解析後會得到一個堆中的位置,這個位置就是儲存實際值的位置。
類 Object:
類 RuntimeHelpers:
方法 Equals() 最初被定義在類 RuntimeHelpers 中,再由類 Object 與類 ValueType 進行擴充套件,而 C# 中其他所有型別(包括值型別、參照型別、自定義型別)均派生自這兩個類,並重寫了這個方法,因此對於任意一個變數均可使用這個方法;且均有各自的比較據。
【關於方法 Equals() 的更多說明與應用,請參閱C# 有關List<T>的Contains與Equals方法 - PaperHammer - 部落格園 (cnblogs.com)】
在 C# 中,對於值型別的比較不管是用 「==」 還是 Equals 都是對於其內容的比較,也就是說對於其值的比較,相等則返回 true 不相等則返回 false;
但是對於除 string 型別以外的參照型別 「==」 比較的是物件在棧上的參照是否相同,而 Equals 則比較的是物件在堆上的內容是否相同。
該方法主要用於字串間的比較,比較的是字串的大小,根據字元對應的 ASCII 碼進行比較。
對於 Compare(s1, s2):s1 == s2 返回 0;s1 > s2 返回 1;s1 < s2 返回 -1。
該類是一個抽象類,位於程式集 CoreLib.dll 中的 名稱空間 System.Collections.Generic
包含 8 個方法,一個屬性。
—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
此處主要關注方法 IEqualityComparer.Equals(object x, object y)
其實該方法的比較依舊主要過運運算元 「==」 完成。
對於比較,其實並不複雜,只需要區分開值型別與參照型別的比較規則就可以。雖然有許多工具都可以用來比較,但其比較的本質依舊是不變的。