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

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

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

基本概念

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

.NET 对数组的处理

在 .NET 中，数组本身是引用类型，继承自 Base Class Library 的 System.Array 基类。因此，无论数组元素是值类型还是引用类型，数组对象本身都存储在托管堆上。

需要注意的是，如果数组元素是引用类型（如 string[]），数组内存中存储的是指向对象的引用（指针）；如果是值类型（如 int[]），元素的值直接存储在数组的连续内存块中。

有关值类型与引用类型

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};
// 1. 创建新数组（长度+1）
int[] arr2 = new int[6];
int insertIndex = 2;
int insertValue = 4;

// 2. 复制插入点之前的数据
for (int i = 0; i < insertIndex; i++)
{
    arr2[i] = arr[i];
}

// 3. 插入新元素
arr2[insertIndex] = insertValue;

// 4. 复制插入点之后的数据（整体后移）
for (int i = insertIndex + 1; i < arr2.Length; i++)
{
    // 注意这里原数组索引需要 -1
    arr2[i] = arr[i - 1]; 
} 
// 结果: 1, 1, 4, 5, 1, 4

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

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

总结

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

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

但也因为这个特性

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