1. 首頁 > 生活百科 > >

.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList<T>

生活百科

[數據結構-線性表1.2] 鏈表與 LinkedList<T>【注：本篇文章源碼內容較少，分析度較淺，請酌情選擇閱讀】
關鍵詞：鏈表（數據結構）    C#中的鏈表（源碼）    可空類型與特性（底層原理 源碼）    迭代器的實現（底層原理）    接口IEqualityCompare<T>（源碼）    相等判斷（底層原理）
鏈表 ， 一種元素彼此之間具有相關性的數據結構，主要可分為三大類：單向鏈表、雙向鏈表、循環鏈表 。其由“鏈”和“表”組成，“鏈”指當前元素到其他元素之間的路徑（指針）；“表”指當前單元存儲的內容（數據） 。本文主要對 C# 中 LinkedList 的源碼進行簡要分析 。
【# 請先閱讀注意事項】
【注：
（1）   文章篇幅較長 ， 可直接轉跳至想閱讀的部分 。
（2）   以下提到的復雜度僅為算法本身，不計入算法之外的部分（如，待排序數組的空間占用）且時間復雜度為平均時間復雜度 。
（3）   除特殊標識外 ， 測試環境與代碼均為 .NET 6/C# 10 。
（4）   默認情況下，所有解釋與用例的目標數據均為升序 。
（5）   默認情況下 ， 圖片與文字的關系：圖片下方 ， 是該幅圖片的解釋 。
（6）   文末“ [ # … ] ”的部分僅作補充說明，非主題（算法）內容，該部分屬于 .NET 底層運行邏輯，有興趣可自行參閱 。
（7）   本文內容基本為本人理解所得，可能存在較多錯誤，歡迎指出并提出意見 ， 謝謝 ?！?br /> 一、鏈表概述及常見類型【注：該部分在網絡上已有很多資料，故不作為重點】
數組作為一個最初的順序儲存方式的數據結構，其可通過索引訪問的靈活性，使用為我們 的程序設計帶來了大量的便利 。但是，數組最大的缺點就是：為了保證在存儲空間上的連續性，在插入和刪除時需要移動大量的元素，造成大量的消耗時間 ， 以及高冗余度 。為了避免這樣的問題，因此引入了另一種數據結構鏈表 。
鏈表通過不連續的儲存方式、動態內存大小，以及靈活的指針使用（此處的指針是廣義上的指針 ， 不僅僅只代表 C/C++ 中的指針，還包括一些標記等），巧妙的簡化了上述的缺點 。其基本思維是，利用結構體或類的設置，額外開辟出一份內存空間去作“表”本身，其內部包含本身的值，以及指向下一個結點的指針，一個個結點通過指針相互串聯 ， 就形成了鏈表 。但優化了插入與刪除的額外時間消耗 ， 隨之而來的缺點就是：鏈表不支持索引訪問 。
(一) 單向鏈表以下僅簡單寫一下基本構成和方法 。

.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
首先定義“表” ， 即每個結點 。其包含自身數據與指向下一個表的指針 。其中一個默認構造方法，一個帶參構造方法用于兩種不同形式的初始化 。
—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
再定義一下“鏈“
  • Line 74~85：構造方法，默認方法初始化頭結點為空；鏈表長度為零；帶參方法用處初始化單個結點 。
  • Line 87~88：定義私有字段，包括鏈表長度、頭節點 。
  • Line 90~91：公共屬性，用于外部訪問私有字段 。通過公共屬性訪問私有字段，符合面向對象的設計原則，體現了對字段的封裝，增強了代碼在運行時的安全性 。
—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
接下來定義常用方法
1.   首尾添加
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
2.   插入
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
  • Line 140：關于這個循環條件 ， 循環到 idx – 1，使 cur 停在執行位置的前一個位置 。若停在操作位置，則無法設定前一個結點的 next 屬性 。
3.   刪除
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
實現效果
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
(二) 雙向鏈表
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

推薦閱讀