概述

数组(Array) 是一种线性表数据结构，用一组连续的内存空间，来存储一组具有相同类型的数据

但是在 PHP 这类动态语言中，数组底层是通过散列表（数据结构）实现的，所以功能异常强大，PHP 的数组可以存储任何类型数据，如果与 Java 对比的话，PHP 数组集成了 Java 的数组、List、Set、Map 于一身，所以写代码的效率比 Java 高了几个量级

抛开 PHP 或 JavaScript 这种动态语言，对于传统的数组，比如 C 语言和 Java 中的数组，在使用之前都需要声明数组存储数据的类型和数组的大小

术语

数组的每一个元素都有唯一的编号对应着元素，编号从 0 开始算起，以此类推，如下方的例子：

元素 10 的编号是 0，虽然会让新手不适应，不过几乎所有的编程语言都是从 0 对数组元素编

元素所在的位置叫索引，例如上方 “元素 10 位于索引 1 处”

数组优缺点

优点：

1. 可以通过下标值随机访问数组内的任何元素
   • 两种方式：顺序和随机
   • 顺序访问意味着从第一个元素开始逐个读取元素
2. 时间复杂度是 O(1)，非常高效

缺点：

1. 删除某个元素后，将后续元素都往前移一位
2. 插入，则需要将插入位置之后的元素都往后移
3. 插入/删除的时间复杂度是 O(n)

例如，假设有一个数组，包含 5 个元素，起始地址是 00，那么元素 5 的地址是多少呢？

稍微运算下就知道是：04，所以需要随机获取元素时，数组的效率最高

下方是数组的时间复杂度：

其中 读取 最快，而 插入/删除 由需要往前/后移动，由于不清楚需要移动的元素数量，所以是 n

O(1) 是常量时间 O(n) 是线性时间

插入元素

在数组中插入新元素，最理想的情况是在最尾部，因为不用移动任何元素，所以此时的复杂度是常量时间，当然一般不考虑这种情况

假设有一个待办事项清单列表，需要新增一个待办事项，有两种情况：无序和有序

如上图，无序的话直接在数组尾部插入新增的元素，这是最好的情况。而有序的话，也就是在前/中间插入新元素，这种情况就要往后移动元素，因为移动的数量是不定的，所以这种情况是比较浪费时间

并且因为数组存储在内存空间是连续性的，所以在插入新元素的时候，如果没有足够的内存空间，可能还得将整个数组复制到内存空间的其它地方，以保证空间足以插入新元素

删除元素

删除 一个数组中的元素之后，需要将后面的元素往前移动

不同于插入，删除元素总能成功，如果没有足够的内存空间，插入可能会失败，而删除在任何情况都能操作成功

通过上面的介绍，可以得知，如果需要频繁执行 插入/删除操作，那么不适合使用数组，应该用 链表，这是另外一种数据结构

相关工具

• VisuAlgo - 数据结构和算法动态可视化 (Chinese)
• 力扣 - LeetCode

Q.E.D.