数组

数组是一切数据结构的起点，或者说，在计算机世界里，唯一被硬件支持的数据结构就是数组，因为内存的模型就是一个巨大的可以被随机读写的数组，如何合理的划分，组织，就成为了数据结构研究的内容。

数组的定义

数组是一种线性数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。元素在数组中的位置被称为索引或数组下标，一般在C/C++等编程语言中，第一个元素的索引为0，第二个元素的索引为1，以此类推。划分给数组的大小往往是固定的，被称为数组的容量，而实际存放的元素个数，被称为数组的长度。

// 存储在栈上
int arr1[5] = { 1, 2, 3, 4, 5 };
// 存储在堆上
int* arr2 = new int[5] { 1, 2, 3, 4, 5 };

数组的操作

访问数组，如果我们知道了数组的起始地址，已经存放的元素大小，那么就可以快速计算出任意元素的地址，从而快速访问任意元素。这种访问方式被称为随机访问，因为我们可以随机访问任意元素。计算公式为：

元素地址 = 基地址 + 下标 × 元素大小

由于地址可以直接计算得到，所以随机访问的时间复杂度是 O(1)。但插入和删除操作则不同：为了保持元素在内存中的连续性，插入需要把插入点之后的元素整体后移，删除则需要把删除点之后的元素整体前移，这两种操作在最坏情况下的时间复杂度都是 O(n)。

试一试，在下面的可视化组件中体验数组的随机访问、插入与删除操作，注意观察插入和删除时元素的搬移过程。