经验总结

  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）   本文内容基本为本人理解所得，可能存在较多错误，欢迎指出并提出意见，谢谢 。】
一、链表概述及常见类型【注：该部分在网络上已有很多资料，故不作为重点】
数组作为一个最初的顺序储存方式的数据结构，其可通过索引访问的灵活性，使用为我们 的程序设计带来了大量的便利 。但是，数组最大的缺点就是：为了保证在存储空间上的连续性，在插入和删除时需要移动大量的元素，造成大量的消耗时间，以及高冗余度 。为了避免这样的问题，因此引入了另一种数据结构链表 。
链表通过不连续的储存方式、动态内存大小，以及灵活的指针使用（此处的指针是广义上的指针，不仅仅只代表 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：公共属性，用于外部访问私有字段 。通过公共属性访问私有字段，符合面向对象的设计原则，体现了对字段的封装，增强了代码在运行时的安全性 。
—— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— —— ——

经验总结扩展阅读


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

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