# 概述 **数组(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)](https://visualgo.net/zh) - [力扣 - LeetCode](https://leetcode-cn.com/)