概述
数组(Array) 是一种线性表数据结构,用一组连续的内存空间,来存储一组具有相同类型的数据
但是在 PHP 这类动态语言中,数组底层是通过散列表(数据结构)实现的,所以功能异常强大,PHP 的数组可以存储任何类型数据,如果与 Java 对比的话,PHP 数组集成了 Java 的数组、List、Set、Map 于一身,所以写代码的效率比 Java 高了几个量级
抛开 PHP 或 JavaScript 这种动态语言,对于传统的数组,比如 C 语言和 Java 中的数组,在使用之前都需要声明数组存储数据的类型和数组的大小
术语
数组的每一个元素都有唯一的编号对应着元素,编号从 0
开始算起,以此类推,如下方的例子:
元素 10 的编号是 0,虽然会让新手不适应,不过几乎所有的编程语言都是从 0 对数组元素编
元素所在的位置叫索引,例如上方 “元素 10 位于索引 1 处”
数组优缺点
优点:
- 可以通过下标值随机访问数组内的任何元素
- 两种方式:顺序和随机
- 顺序访问意味着从第一个元素开始逐个读取元素
- 时间复杂度是
O(1)
,非常高效
缺点:
- 删除某个元素后,将后续元素都往前移一位
- 插入,则需要将插入位置之后的元素都往后移
- 插入/删除的时间复杂度是
O(n)
例如,假设有一个数组,包含 5 个元素,起始地址是 00,那么元素 5 的地址是多少呢?
稍微运算下就知道是:04,所以需要随机获取元素时,数组的效率最高
下方是数组的时间复杂度:
其中 读取 最快,而 插入/删除 由需要往前/后移动,由于不清楚需要移动的元素数量,所以是 n
O(1)
是常量时间O(n)
是线性时间
插入元素
在数组中插入新元素,最理想的情况是在最尾部,因为不用移动任何元素,所以此时的复杂度是常量时间,当然一般不考虑这种情况
假设有一个待办事项清单列表,需要新增一个待办事项,有两种情况:无序和有序
如上图,无序的话直接在数组尾部插入新增的元素,这是最好的情况。而有序的话,也就是在前/中间插入新元素,这种情况就要往后移动元素,因为移动的数量是不定的,所以这种情况是比较浪费时间
并且因为数组存储在内存空间是连续性的,所以在插入新元素的时候,如果没有足够的内存空间,可能还得将整个数组复制到内存空间的其它地方,以保证空间足以插入新元素
删除元素
删除 一个数组中的元素之后,需要将后面的元素往前移动
不同于插入,删除元素总能成功,如果没有足够的内存空间,插入可能会失败,而删除在任何情况都能操作成功
通过上面的介绍,可以得知,如果需要频繁执行 插入/删除操作,那么不适合使用数组,应该用 链表,这是另外一种数据结构
相关工具
Q.E.D.
Comments | 0 条评论