数组

8/5/2020 数据结构与算法数组

# 什么是数组?

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

理解几个关键词:

# 1.连续内存空间:

数组存储在一块连续的内存中,每个元素紧紧挨在一起。像下图这样:(红色表示数组占用的内存空间,灰色表示空间已被占用,绿色表示未被占用)

# 2.有限个

数组在初始化时需要有一个长度,就是告诉内存要分配一个多大的空间来存储它。

# 3.相同类型

数组必须存储一组具有相同类型的数据。

# 数组的基本操作

数据结构与算法中的数组与各编程语言中的数组不是一个概念(可能学过 java 的朋友有疑惑,数组不是定长的吗,不能插入和删除啊,对,没错,但是 java 里的数组并不等同于这里数据结构与算法中的数组,此"数组"非彼"数组",其他编程语言也一样,都是按照自己的语言特点设计的数组类型)。

数据结构和算法先于编程语言出现。编程语言中有一些数据类型,并不能跟数据结构和算法书籍中讲到的经典数据结构,完全一一对应。具体可查看这篇文章: 详解数据结构中的“数组”与编程语言中的“数组”的区别和联系 (opens new window)

数据结构的操作无非增、删、改、查几种情况,下面依次来看下:

# 1.查询

由于数组具有连续存储相同类型数据的特点,因而数组支持随机访问

什么是随机访问?这里的随机并不是概率上的随机,而是指根据下标任意访问数组中的元素,有点"钦点"的意思,你想查询数组中第几个元素就查询第几个元素。

但是注意要在数组给定的长度内访问,否则就会有数组越界的问题了。这种 根据下标随机访问的时间复杂度为O(1)

# 数组寻址公式

现在有一个长度为 7 的数组,存储在某个内存块上,内存块的首地址为 base_address ,数据中每个元素的大小为 data_type_size

那么,查询数组第 i 个元素(从 0 开始)的内存地址为:

a[i]_address = base_address + i * data_type_size
1

这个公式就是数组的寻址公式,随机访问就是根据此公式来的。

# 2.更新

更新操作比较简单,直接把新值赋给要更新的元素即可:

更新操作的时间复杂度也是O(1)。

# 3.插入

插入操作稍微复杂点,因为要保持数据的连续性,所以要涉及到数据的搬移。

先说明一点,数组的实际元素数量有可能小于数组的长度,比如下面的情况,数组长度为7,但实际元素数量为5:

尾部插入

在数组尾部插入元素7,直接将 7 赋值到数组尾部空闲位置,类似于更新操作,不用考虑数据的搬移。

中间插入

接着,在第一个元素3后面插入8,由于要考虑数组的内存连续性,需要将插入位置后面的元素统统向后移动一位。

头部插入

然后,在数组头部插入元素2,此时需要搬移整个数组的数据。

从上面几种情况可以看出,插入位置不同,数据的搬移次数也不同,向一个元素数量为 n 的数组中插入数据,插入的位置总共有 n+1 种情况,对应的数据搬移次数为 0,1,2,...,n,使用平均情况时间复杂度分析,得知数组插入操作的平均情况时间复杂度为:

T(n) = O((0+1+2+...+n)/(n+1)) = O(n)
1

数组插入操作平均情况时间复杂度为O(n)。

需要注意的一点是,假如在数组满员的情况下,再往里插入数据,需要考虑数组的扩容问题。

如果不考虑数组元素顺序的情况下,插入操作可以有一种取巧的方式,做到插入时间复杂度为O(1)。比如:

现在有一个数组,在第二个位置插入元素 2,在不考虑数组顺序的情况下,可以这样操作:

a[5] = 4;
a[1] = 2;
1
2

只需要两次赋值操作,不用数据的搬移,做到时间复杂度为O(1)。

# 4.删除

# 测试锚点

和插入操作类似,数组的删除也会涉及到数据的搬移,删除操作的平均情况时间复杂度为O(n)。

实际上,对于数组中删除操作,并不一定每次删除都得进行数据的搬移,我们可以先标记要删除的元素,等数组没有多余的存储空间时,再一次性删除被标记的元素,大大减少数据搬移的时间。

这其实就是 JVM 标记清除垃圾回收算法的核心思想。

# 容器和数组的区别

# 容器

1.支持动态扩容

不过动态扩容需要涉及数据的搬移,如果能确定需要存储数据的大小,最好在初始化容器的时候指定其大小。如:

ArrayList<Integer> array = new ArrayList(1000);
1

2.无法操作基本类型

如 int,long 需要封装为对应的包装类Integer,Long。而自动装箱(Autoboxing)、拆箱(Unboxing)有一定的性能损耗,所以如果特别关注性能,基本数据类型的存储优先用数组。

# 数组

1.需预先指定大小

因为数组需要分配连续的内存空间。

2.只能存储基本类型

使用场景

做一些业务开发,使用容器即可,损失的性能随整体的性能基本无影响。

如果做一些偏底层的开发,比如网络框架,性能的优化等,十分考虑性能,则使用数组。

说明文字