1. 首頁 > 生活百科 > >

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

生活百科

—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
接下來是方法 AddBefore() ， 其和前兩個方法一樣，均有兩個重載方法，主要是返回類型與參數不同 。
（1）   對于無返回值、待添加元素為鏈表（結點）的方法

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

文章插圖
  • Line 121：node 為目標結點，在其之后進行添加；newNode 為新結點 。
  • Line 123、124：方法 ValidateNode() 與 ValidateNewNode() 用于判斷 node 的合法性

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

文章插圖

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

文章插圖
是否為空；是否為該鏈表的成員（目的可能是防止多線程同步訪問出現的錯誤調用）
  • Line 125：方法 InternalInsertNodeBefore() 實現添加操作 。

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

文章插圖
就是普通的雙向鏈表的插入 。
（2）   對于返回類型為 LinkedList<T>，添加元素為某個值的方法
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
  • Line 132~134：判斷 node 合法性；初始化一個以 node 為首 ， node 值為 value的新鏈表；將新鏈表連接到 node 之前 。
  • Line 137：當 node 為頭結點時，添加后需要更新頭結點 。
—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
方法 AddAfter() 大同小異，不做過多分析
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
2.    包含 Contains() [ Find() 方法]
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
方法套方法，Find 可以用來查找元素，其在其他的方法（如：Remove()）中也可以使用，為了減少冗余，因此此處直接復用了方法 Find() 來實現 。
復用的思想在競賽、開發中十分常用，既能有效減少工程量，還能提高代碼可讀性 。
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
  • Line 270：Nullable 特性，其中 LinkedList 可為空；<T> 不可為空 。
  • Line 277：next 表示當前即將訪問的元素，從 head 開始 。
  • Line 278：定義了一個默認比較方式的變量 ， 用于之后調用比較方法 。EqualityCompare<T> 類型，一個抽象類，內部提供了一個 Equals() 方法，進行對象間的比較 。

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

文章插圖
【思考：為什么需要定義該類型的變量，調用該類中的比較方法 ， 而不直接用判斷運算符 “==” 或 Object.Equals() 方法？文末進行解釋】
  • Line 279：若 next 為空，即 head 為空，說明沒有元素在鏈表中，則直接返回值為空的 next（ Line: 304 ） 。
  • Line 281：若要查找的對象值為空，則不進行比較操作 ， 直接判斷是否存在空元素 。
  • Line 283：若當前結點值 item != value 則向后訪問下一個結點 ， 繼續比較，直到找到符合的結點或再次訪問到頭結點 。
  • Line 288、298：若沒有找到符合的結點，則直接轉調并返回 null 。
3.    查找 FindLast()從方法名來看 ， 其作用是找到值 value 在鏈表中出現的最后一次所對應的結點 。
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
相比方法 Find()，只是將 next 換成了 prev，其他地方大同小異 ， 主要來分析一下這個 prev 的作用 。
當 linkedListNode == prev 時，說明已經遍歷完了一遍，此時還未找到目標元素，返回 null 。
4.    刪除 Remove()
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
其基本思路說判斷合法性，然后執行操作 。其中 ValidateNode 在之前提到過，用于判斷結點合法性 。
下面看一下方法 InternalRemoveNode()
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
和添加方法中的那個 InternalInsert…() 基本一致，改變結點的指向即可 ， 記得最后要修改結點數量 。

推薦閱讀