C#数据结构

一、数组(Array)

定义

元素序列，存放形同类型的变量，对象，每一项都有一个整数索引（下标）；元素位于一个连续存储的内存块中；数组空间大小是固定的。

数组分类

一维数组，多维数组（等于或大于二维）

数组的优点：

随机访问性强,查找速度快，时间复杂度是0（1）

数组的缺点：

3.1 从头部删除、从头部插入的效率低，时间复杂度是o(n),因为需要相应的向前搬移和向后搬移。

3.2 空间利用率不高

3.3 内存空间要求高，必须要有足够的连续的内存空间。

3.4 数组的空间大小是固定的，不能进行动态扩展。

总结：

1. 数组属于线性结构，在内存中是连续存放的。
2. 数组的元素类型必须相同。
3. 数组可以直接通过下标访问。
4. 数组的查找速度非常快，新增和删除速度慢。
5. 数组在初始化时要指定数组长度。

二、动态数组(ArrayList)

定义

动态数组（ArrayList）代表了可被单独索引的对象的有序集合。它基本上可以替代一个数组。但是，与数组不同的是，您可以使用索引在指定的位置添加和移除项目，动态数组会自动重新调整它的大小。它也允许在列表中进行动态内存分配、增加、搜索、排序各项。

为了解决数组创建时必须指定长度以及只能存放相同类型的缺点而推出的数据结构。ArrayList是System.Collections命名空间下的一部分，所以若要使用则必须引入System.Collections。正如上文所说，ArrayList解决了数组的一些缺点。

动态数组的优点

1. 不必在声明ArrayList时指定它的长度，这是由于ArrayList对象的长度是按照其中存储的数据来动态增长与缩减的。
2. ArrayList可以存储不同类型的元素。这是由于ArrayList会把它的元素都当做Object来处理。因而，加入不同类型的元素是允许的。

动态数组的缺点

1. ArrayList不是类型安全的。因为把不同的类型都当做Object来做处理，很有可能会在使用ArrayList时发生类型不匹配的情况。
2. 如上文所诉，数组存储值类型时并未发生装箱，但是ArrayList由于把所有类型都当做了Object，所以不可避免的当插入值类型时会发生装箱操作，在索引取值时会发生拆箱操作。这能忍吗？

穿插一下装箱与拆箱的概念：
简单的来讲:
装箱：就是将值类型的数据打包到引用类型的实例中
比如将int类型的值123赋给object对象o

int i=123;
object o=(object)i;

拆箱：就是从引用数据中提取值类型
比如将object对象o的值赋给int类型的变量i

object o=123;
int i=(int)o;

注：为何说频繁的没有必要的装箱和拆箱不能忍呢？且听小匹夫慢慢道来：所谓装箱 (boxing)：就是值类型实例到对象的转换。那么拆箱：就是将引用类型转换为值类型

从原理上可以看出，装箱时，生成的是全新的引用对象，这会有时间损耗，也就是造成效率降低。（ArrayList非必要不使用 ）

总结：

1. ArrayList的底层其实就是一个数组。
2. ArrayList在声明时不必指定长度，会根据存储的数据动态的增加或减少长度。
3. ArrayList会把所有的元素都当做Object处理，因此可以存储不同数据类型的元素。
4. 插入和删除一个元素时，会移动它之后所有元素的位置，效率低，频繁进行插入或者删除元素推荐使用LinkedList。
5. ArrayList是非类型安全的，在插入和删除元素时会进行拆箱和装箱问题，影响性能，效率低。

三、List泛型List

​ 为了解决ArrayList不安全类型与装箱拆箱的缺点，所以出现了泛型的概念，作为一种新的数组类型引入。也是工作中经常用到的数组类型。和ArrayList很相似，长度都可以灵活的改变，最大的不同在于在声明List集合时，我们同时需要为其声明List集合内数据的对象类型，这点又和Array很相似，其实List内部使用了Array来实现。

优点

1. 即确保了类型安全。
2. 也取消了装箱和拆箱的操作。
3. 它融合了Array可以快速访问的优点以及ArrayList长度可以灵活变化的优点。

四、双向链表（LinkedList）

1.链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，一般用于插入与删除较为频繁的场景。

和上述的数组最大的不同之处就是在于链表在内存存储的排序上可能是不连续的。这是由于链表是通过上一个元素指向下一个元素来排列的，所以可能不能通过下标来访问。如图

既然链表最大的特点就是存储在内存的空间不一定连续，那么链表相对于数组最大优势和劣势就显而易见了。

1. 向链表中插入或删除节点无需调整结构的容量。因为本身不是连续存储而是靠各对象的指针所决定，所以添加元素和删除元素都要比数组要有优势。
2. 链表适合在需要有序的排序的情境下增加新的元素，这里还拿数组做对比，例如要在数组中间某个位置增加新的元素，则可能需要移动移动很多元素，而对于链表而言可能只是若干元素的指向发生变化而已。
3. 有优点就有缺点，由于其在内存空间中不一定是连续排列，所以访问时候无法利用下标，而是必须从头结点开始，逐次遍历下一个节点直到寻找到目标。所以当需要快速访问对象时，数组无疑更有优势。

综上，链表适合元素数量不固定，需要经常增减节点的情况。

2.链表的分类

常见的有单链表、双链表和循环链表

单链表 ：每个节点只有一个指针域，指向下一个节点。单链表的插入和删除操作比较简单，但是查询慢。

双链表 ：每个节点有两个指针域，分别指向前一个节点和后一个节点。双链表可以方便地实现双向遍历，但是占用空间比较大。

循环链表 ：尾节点的指针域指向链表的头节点。循环链表比单链表和双链表的查询效率更高，但是在插入和删除操作时需要注意维护链表的结构。

单链表的数据结构

            public class ListNode
                {
                    public int val;
                    public ListNode next;
                    public ListNode(int x)
                    {
                        val =x;
                    }

                }

链表的优点

1. 任意位置插入元素和删除元素的速度快，时间复杂度是o(1)
2. 内存利用率高，不会浪费内存
3. 链表的空间大小不固定，可以动态拓展。

链表的缺点

1. 随机访问效率低

数组和链表的区别

双向链表具有如下特点：

1. 链表的节点在内存中的空间是不连续的，每块空间称作一个节点，每个节点都存有一个前驱和后置指针，分别指向前一个节点和后一个节点，因此向链表中添加和删除元素的效果高，只需要更改相应节点的指针指向即可。
2. 链表的查找效率低。查找元素时不能通过下标进行访问，只能从头开始通过地址按顺序查找。

五、堆栈（Stack）

1、什么是堆？（Heap）

堆是无序的，是一片不连续的内存域，由用户自己来控制和释放，如果用户自己不释放的话，当内存达到一定的特定值时，通过垃圾回收器（GC）来回收。

是程序运行期间动态分配的内存空间，你可以根据程序的运行情况确定要分配的堆内存的大小。

2、什么是栈？（Stack）

栈是有顺序的，是一片连续的内存域，保持着先进后出的原则，由系统自动分配和维护。

是编译期间就分配好的内存空间，因此代码中必须就栈的大小有明确的定义。

表尾允许进行插入删除操作，称为栈顶（*Top*），另一端是固定的，称为栈底（*Bottom*）。

PS：

线性表（Linear List）是具有相同特性的数据元素的一个有限序列。

堆栈（Stack） 是一种特殊的线性表，是一种操作只允许在尾端进行插入或删除等操作的线性表。

顺序栈（Sequence Stack）是用一片连续的存储空间来存储栈中的数据元素。

链栈（Linked Stack）是用链式存储结构来存储的栈，链栈通常用单链表来表示。

定义

由堆和栈的概念，可以清晰的知道，堆栈是一种数据项按序排列的数据结构，只能在一端称为栈顶（top）对数据项进行插入和删除。

最后一个放入堆栈中的物体总是被最先拿出来，这个特性通常称为后进先出（LIFO）队列。

堆栈中定义了一些操作，两个最重要的是PUSH和POP。PUSH操作在堆栈的顶部加入一个元素，POP操作相反，在堆栈顶部移去一个元素， 并将堆栈的大小减一。

PS：通常所说的堆栈，实际上更偏向于指栈。

堆栈具有如下特点：

1. 堆栈是先进后出的原则，最先插入的元素最后被访问，最后插入的元素最先被访问。
2. Push入栈，Pop出栈并返回栈顶元素，Peek只返回栈顶元素。

堆、栈之间的区别是

堆实际上指的就是（满足堆性质的）优先队列的一种数据结构，第一个元素有最高的优先权

栈实际上就是满足先进后出的性质的数学或数据结构。

1、堆栈空间分配

栈（操作系统）：由操作系统自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。

堆（操作系统）：一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收，分配方式倒是类似于链表。

2、堆栈缓存方式

栈使用的是一级缓存， 他们通常都是被调用时处于存储空间中，调用完毕立即释放。

堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些。

3、堆栈数据结构区别

堆（数据结构）：堆可以被看成是一棵树，如：堆排序。

栈（数据结构）：一种先进后出的数据结构。

特性： 最后一个放入堆栈中的物体总是被最先拿出来， 这个特性通常称为后进先出(LIFO)队列。

六、Queue（ 队列）

队列是一种特殊的线性表，它只允许在表的前端（Front）进行删除操作，而在表的后端（Rear）进行插入操作。

进行插入操作的表尾称为队尾（Rear），把进行其他操作的头部称为队头（Front）。

队列中没有元素时，称为空队列，队列具有先进先出（FIFO）的特点。

PS：

队列（Queue）是插入操作限定在表的尾部而其他操作限定在表的头部进行的线性表。

顺序队列（Sequence Queue）用一片连续的存储空间来存储队列中的数据元素，类似于顺序表，用一维数组来存放队列中的数据元素。

循环顺序队列（Circular sequence Queue）解决顺序队列的假溢出的方法是将顺序队列看成是首位相接的循环结构。

链队列（Linked Queue）队列的另外一种存储方式是链式存储，通常用单链表表示。

队列具有以下特点：

1. 链表是先进先出的原则，最先进入的元素最先被访问，最后进入的元素最后被访问。
2. Enqueue入队列，Dequeue出队列并返回列首元素，Peek只返回列首元素。

七、字典（Dictionary）

字典具有以下特点：

1. 创建字典时需要指定key和value的数据类型。
2. 字典中的key值是唯一的，value的值可以不唯一。
3. 可以通过key快速查找对应的value，速度快，但是消耗内存。

总结：几种常见数据结构的使用情景