.NET 源码学习 [数据结构-线性表1.2] 链表与 LinkedList<T>( 二 ) _生活百科

文章插图
双向链表在单向的基础上增加了指向前的指针
—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
“链“的构造方法及相关字段和属性不变，只是在方法的实现时，需要增加对 prev 的赋值
1. 首尾添加

文章插图

Line 168、185：注意，应当先对原 head 的 prev 指针赋值，再修改 head 的指向。

—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
2. 插入

文章插图
一般地，先修改新结点的信息，再修改原结点的信息。
—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——
3. 删除

文章插图

Line 292：此处已经更新了 cur.next 的指向，所以并不是 Line 291 的语句。

实现效果

文章插图
(三) 循环链表循环，就是把尾部结点的 next 指针继续指向下，指向 head 。大同小异，本节内容在此不作演示，详细请参阅：（理论基础 —— 线性表 —— 循环链表 - 老程序员111 - 博客园 (cnblogs.com)）
总结一1. 对比一下数组、集合与链表（1）对于数组：

长度固定，初始化后长度不可变。
在内存中的存储单元是连续分配的。
可存储基本数据类型、引用数据类型。
每个数组只能存储类型相同的元素。
可通过下标与迭代器访问。

（2）对于集合：

长度（容量）可变，一般初始容量为 4，满后在现有容量基础上 *2 作为新的容量。
在内存中的存储单元是随机分配的，可能连续也可能分散。
可存储基本数据类型、引用数据类型。
对于同一个 ArrayList 可以存储不同类型的数据；对于泛型集合，每个只能存储类型相同的数据。
可通过下标与迭代器访问。

（3）对于链表：

长度可变，随结点数量变化而变化。
在内存中的存储单元是随机分配的，可能连续也可能分散。
结点可存储基本数据类型、引用数据类型。
每个链表只能存储类型相同的元素。
不可通过下标或迭代器访问，只能遍历访问。

2. 三者的优缺点（1）数组：

优点：可在 O( 1 ) 时间复杂度内完成查找。
缺点：不能扩容；对于元素的插入与删除需 O( n ) 才能完成。其中，插入的这个动作为 O( 1 )，移动元素的动作为 O( n ) 。

（2）集合：

优点：长度可变；内存易分配；可在O( 1 )内完成查找。（一般地，集合底层结构为数组或链表）
缺点：因为底层与数组、链表相同，因此对于插入与删除较慢。

（3）链表：

优点：可以任意加减元素，在添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加、删除很快， O( 1 )；
缺点：因为含有大量的指针域，占用空间较大；不支持下标与迭代器访问，因此查找元素需要遍历，非常耗时。

二、C# 中的链表 LinkedList<T>

文章插图
C# 中的LinkedList 为双向链表（双重链接链表），位于程序集 System.Collections.dll中的命名空间 System.Collections.Generic 之下。
简单解释一下其拥有的特性：【注：特性基本介绍请参阅本人的文章（[算法2-数组与字符串的查找与匹配] （.NET源码学习） - PaperHammer - 博客园 (cnblogs.com)）】