1. 首頁 > 生活百科 > >

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

生活百科


文章插圖
雙向鏈表在單向的基礎上增加了指向前的指針
—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
“鏈“的構造方法及相關字段和屬性不變 ， 只是在方法的實現時，需要增加對 prev 的賦值
1.    首尾添加

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

文章插圖
  • Line 168、185：注意，應當先對原 head 的 prev 指針賦值，再修改 head 的指向 。
—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
2.    插入
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList<T>

文章插圖
一般地，先修改新結點的信息 ， 再修改原結點的信息 。
—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
3.    刪除
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList<T>

文章插圖
  • Line 292：此處已經更新了 cur.next 的指向，所以并不是 Line 291 的語句 。
實現效果
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList<T>

文章插圖
(三) 循環鏈表循環，就是把尾部結點的 next 指針繼續指向下，指向 head 。大同小異 ， 本節內容在此不作演示，詳細請參閱：（理論基礎 —— 線性表 —— 循環鏈表 - 老程序員111 - 博客園 (cnblogs.com)）
總結一1.   對比一下數組、集合與鏈表（1）   對于數組：
  1. 長度固定 ， 初始化后長度不可變 。
  2. 在內存中的存儲單元是連續分配的 。
  3. 可存儲基本數據類型、引用數據類型 。
  4. 每個數組只能存儲類型相同的元素 。
  5. 可通過下標與迭代器訪問 。
（2）   對于集合：
  1. 長度（容量）可變，一般初始容量為 4，滿后在現有容量基礎上 *2 作為新的容量 。
  2. 在內存中的存儲單元是隨機分配的，可能連續也可能分散 。
  3. 可存儲基本數據類型、引用數據類型 。
  4. 對于同一個 ArrayList 可以存儲不同類型的數據；對于泛型集合，每個只能存儲類型相同的數據 。
  5. 可通過下標與迭代器訪問 。
（3）   對于鏈表：
  1. 長度可變，隨結點數量變化而變化 。
  2. 在內存中的存儲單元是隨機分配的，可能連續也可能分散 。
  3. 結點可存儲基本數據類型、引用數據類型 。
  4. 每個鏈表只能存儲類型相同的元素 。
  5. 不可通過下標或迭代器訪問 ， 只能遍歷訪問 。
2.   三者的優缺點（1）   數組：
  1. 優點：可在 O( 1 ) 時間復雜度內完成查找 。
  2. 缺點：不能擴容；對于元素的插入與刪除需 O( n ) 才能完成 。其中，插入的這個動作為 O( 1 )，移動元素的動作為 O( n ) 。
（2）   集合：
  1. 優點：長度可變；內存易分配；可在O( 1 )內完成查找 。（一般地，集合底層結構為數組或鏈表）
  2. 缺點：因為底層與數組、鏈表相同 ， 因此對于插入與刪除較慢 。
（3）   鏈表：
  1. 優點：可以任意加減元素，在添加或者刪除元素時只需要改變前后兩個元素結點的指針域指向地址即可，所以添加、刪除很快 ，  O( 1 )；
  2. 缺點：因為含有大量的指針域 ， 占用空間較大；不支持下標與迭代器訪問，因此查找元素需要遍歷，非常耗時 。
二、C# 中的鏈表 LinkedList<T>
.NET 源碼學習 [數據結構-線性表1.2] 鏈表與 LinkedList&lt;T&gt;

文章插圖
C# 中的LinkedList 為雙向鏈表（雙重鏈接鏈表），位于程序集 System.Collections.dll中的命名空間 System.Collections.Generic 之下 。
簡單解釋一下其擁有的特性：【注：特性基本介紹請參閱本人的文章（[算法2-數組與字符串的查找與匹配] （.NET源碼學習） - PaperHammer - 博客園 (cnblogs.com)）】
  • Line 9：NullableContext() 表示可空的上下文 。括號中的值對應的功能如下圖：

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

文章插圖
這里解釋一下“上下文”：
上下文并不是一個具體的東西，就和閱讀小說一樣，需要結合前后進行理解 。

推薦閱讀