定义

数组(Array)是一种线性表结构，它用一组连续的内存空间来存储一组具有相同类型的数据。
在这个定义中有几个关键词：

线性表

所谓线性表就是数据会排成像一条线一样的结构。也就是说线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
线性表包括:顺序表和链表
顺序表里面元素的地址是连续的，比如数组或者用数组实现的队列、栈等
链表里面节点的地址不是连续的，是通过指针连起来的.如下图所示：

线性表具体解释可以参考线性表

而与线性表队里的概念就是费线性表，比如二叉树、堆、图等等。之所以叫非线性表是因为，在非线性表中数据之间并不是一对一的前后关系，如下所示：

连续内存空间&相同类型

正是基于这种定义的限制，因此可以只需要计算出数组中某一元素相对于首地址(base_address)的偏移量，就可以很方便的计算出这个元素的地址。
以一个长度为4的int类型的数组 int[] arr = new int[4]; 为例。在初始化这个数组时，计算机会给数组arr分配一块连续的内存空间 1000~1015，其中首地址为base_address = 1000, 如下图所示：

计算机会给每个内存单元分配一个物理地址，然后计算机通过这些物理地址来访问内存中的数据。当计算机需要访问数组中的某个元素是，就可以通过下面的寻址公式，计算出该元素的内存地址：

arr[i]_address = base_address + i * data_type_size

其中i 代表需要访问的元素下标，base_address代表首地址，data_type_size_代表每个元素占用的内存大小，比如数组中存储的是java的int类型，所以data_type_size_也就是4个字节。

数组的基本操作

• 插入操作
• 删除操作
• 查找操作

插入操作

插入操作有两种情况。

在数组的末尾插入元素

如果是在末尾插入操作，不需要移动任何元素的位置，直接在数组最后位置添加上一个新的元素即可。因此在数组末尾插入数据的时间复杂度为 O(1)

在数组头部插入元素。

如果是在开头位置插入元素，那为了保持内存数据的连续性，所有的数据都需要依次往后移动一位，所以最坏时间复杂度为 O(n)

删除操作

和插入元素类似，如果要删除数组中第K位置的数据，为了保持内存的连续性，需要将K + 1到最后一个元素的位置都向前移动一位。同样也分两种情况

删除数组末尾元素

最好时间复杂度为 O(1)

删除数组头部元素

最坏时间复杂度为 O(n)

随机访问

当我们已经知道某元素在数组中的下标时，我们就可以直接通过下标来访问此元素，比如假设我们已经知道数字 23 在数组 [10, 15, 23, 45] 的下标是 2, 所以我们可以直接通过 arr[2]来指向23。因此数组随机访问的时间复杂度是O(1)

查找操作

假设我们需要在数组 [10, 15, 23, 45] 中查找是否有 23时，因为我们不知道元素23所处的下标是多少，因此需要从头到尾依次遍历数组中的每一个元素，并判断是否等于23。代码可以如下：

for (let index = 0; index < array.length; index++) {
    if(element === array[index]) {
      return index;
    }
  }

因此数组中查找某元素的时间复杂度为 O(n)

数组时间复杂度总结