.NET 数据结构：线性表 - 数组

数组是线性的数据结构，其特点是会将相同类型的元素存储在连续的内存空间中。

由于其内存空间的连续，通过下标访问元素的时间复杂度为O(1)。

基本概念

存在一个数组：1, 1, 4, 5, 1, 4

.NET 对数组的处理

在.NET中，数组是引用类型的，从Base Class Library的基类System.Array派生，但数组元素可以是值类型的。

但如果数组的元素是引用类型的，那么数组存储的将会是对象的引用。

有关值类型与引用类型

Microsoft Learn - 值类型

Microsoft Learn - 引用类型

.NET 的6个重要概念

因此，.NET会将数组放在托管堆上，而不是栈。

操作

实例化

一维数组：

1 2	int[] arr = new int[5]; // 5个元素的数组 int[] arr2 = new int[] { 1, 2, 3 }; // 显式初始化，数组长度由编译器推断

多维数组：

int[,] arr = new int[2, 3];  // 2行3列的二维数组
int[,] arr2 = new int[,] { { 1, 2 }, { 3, 4 } };  // 显式初始化，数组长度由编译器推断

int[,,] arr3 = new int[2, 3, 4];  // 2行3列4层的三维数组
int[,,] arr4 = new int[,,] { 
            { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } }, 
            { { 13, 14, 15, 16 }, { 17, 18, 19, 20 }, { 21, 22, 23, 24 } } 
            };  // 显式初始化，数组长度由编译器推断

访问

数组在内存中是连续存储的，其优势在于可以高效地访问任意元素，时间复杂度为O(1)。

1 2	int[] arr = new int[] { 1, 2, 3 }; Console.WriteLine(arr[0]); // 输出 1

插入 & 删除 & 添加

以插入操作为例：

在内存中连续存储的特性导致数组难以快速插入元素。因此，如果需要插入元素，需要先把插入位置后面的元素全部后移，然后再插入。

然而，如果要让原数组的元素得以保留，那么就需要新建一个更长的数组，然后把原数组的元素复制到新数组中，再插入元素。

这也是基于数组实现列表的基本原理之一。

int[] arr = {1, 1, 5, 1, 4};
int[] arr2 = new int[6];
int insertIndex = 2;
int insertValue = 4;
for (int i = 0; i < insertIndex; i++)
{
    arr2[i] = arr[i];
}
arr2[insertIndex] = insertValue;
for (int i = insertIndex+1; i < arr2.Length; i++)
{
    arr2[i] = arr[i-1];
}  // 1, 1, 4, 5, 1, 4

不难发现，由于在数组中，元素紧密排列，从而导致在最坏情况下，插入元素的时间复杂度为O(n)。

进而可以得知，删除或添加元素的时间复杂度也为O(n)。

总结

得益于数组在内存中的连续存储

数组对内存拥有更高效率的利用：元素在数组中的紧密排列意味着数组几乎不会浪费内存。
极高的访问速度：通过索引访问元素的时间复杂度为O(1)。

但也因为这个特性

新增&插入&删除的效率低：涉及到元素增删的操作会不可避免地导致元素的移动，时间复杂度为O(n)。
固定的长度：如果出现数组长度不够用的情况，需要扩容。