.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++ 中的指针，还包括一些标记等），巧妙的简化了上述的缺点。其基本思维是，利用结构体或类的设置，额外开辟出一份内存空间去作“表”本身，其内部包含本身的值，以及指向下一个结点的指针，一个个结点通过指针相互串联，就形成了链表。但优化了插入与删除的额外时间消耗，随之而来的缺点就是：链表不支持索引访问。
(一) 单向链表以下仅简单写一下基本构成和方法。