大数据、Java EE 学习资料请关注 B 站:https://space.bilibili.com/204792350

数据结构与算法 - 数组

概述

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

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

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

术语

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

数据结构与算法系列-数组-2

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

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

数组优缺点

优点:

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

缺点:

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

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

数据结构与算法系列-数组-1

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

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

运行时间

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

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

插入元素

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

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

数据结构于算法-数组-3

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

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

删除元素

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

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

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

相关工具

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×