经验总结

  1. 首页 > 生活 > >

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

生活百科


接下来定义常用方法
1.   首尾添加

.NET 源码学习 [数据结构-线性表1.2] 链表与 LinkedList<T>

文章插图
2.   插入
.NET 源码学习 [数据结构-线性表1.2] 链表与 LinkedList<T>

文章插图
  • Line 140：关于这个循环条件，循环到 idx – 1 ，使 cur 停在执行位置的前一个位置 。若停在操作位置，则无法设定前一个结点的 next 属性 。
3.   删除
.NET 源码学习 [数据结构-线性表1.2] 链表与 LinkedList<T>

文章插图
实现效果
.NET 源码学习 [数据结构-线性表1.2] 链表与 LinkedList<T>

文章插图
(二) 双向链表
.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 ) 。

    经验总结扩展阅读


上一篇：驾校学车的搞笑文案 朋友圈晒驾驶证文案

下一篇：月老牵线喜结良缘上上签 破镜重圆的3大星座