数组

/ 计算机基础 / 273浏览

数组

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

第一个是线性表(Linear List)。顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。 除了数组,链表、队列、栈等也是线性表结构。 它相对立的概念是非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。

第二个是连续的内存空间和相同类型的数据 ,正是因为这两个限制,它才有了一个堪称“杀手锏”的特性:“随机访问”。可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。但有利就有弊,这两个限制也让数组的很多操作变得非常低效,比如要想在数组中删除、插入一个数据,为了保证连续性,就需要做大量的数据搬移工作。

数组是适合查找操作,但是查找的时间复杂度并不为O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是O(logn)。所以,数组支持随机访问,根据下标随机访问的时间复杂度为O(1)。

低效的“插入”和“删除”

前面概念部分我们提到,数组为了保持内存数据的连续性,会导致插入、删除这两个操作比较低效。

插入操作

假设数组a[10]中存储了如下5个元素:a,b,c,d,e。 我们现在需要将元素x插入到第3个位置。我们只需要将c放入到a[5],将a[2]赋值为x即可。最后,数组中的元素如下: a,b,x,d,e,c。

利用这种处理技巧,在特定场景下,在第k个位置插入一个元素的时间复杂度就会降为O(1)。

删除操作

跟插入数据类似,如果我们要删除第k个位置的数据,为了内存的连续性,也需要搬移数据,不然中间就会出现空洞,内存就不连续了。 和插入类似,如果删除数组末尾的数据,则最好情况时间复杂度为O(1);如果删除开头的数据,则最坏情况时间复杂度为O(n);平均情况时间复杂度也为O(n)。

容器与数组

针对数组类型, 很多语言都提供了容器类,比如Java中的ArrayList ,在项目开发中,什么时候适合用数组,什么时候适合用容器呢?

其中,ArrayList最大的优势就是,可以将很多数组操作的细节封装起来 。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外,它还有一个优势,就是支持动态扩容

数组本身在定义的时候需要预先指定大小,因为需要分配连续的内存空间。如果我们申请了大小为10的数组,当第11个数据需要存储到数组中时,我们就需要重新分配一块更大的空间,将原来的数据复制过去,然后再将新的数据插入。

如果使用ArrayList,我们就完全不需要关心底层的扩容逻辑,ArrayList已经帮我们实现好了。每次存储空间不够的时候,它都会将空间自动扩容为1.5倍大小。

不过,这里需要注意一点,因为扩容操作涉及内存申请和数据搬移,是比较耗时的。所以,如果事先能确定需要存储的数据大小,最好在创建ArrayList的时候事先指定数据大小。

比如我们要从数据库中取出9999条数据放入ArrayList。我们看下面这几行代码,你会发现,相比之下,事先指定数据大小可以省掉很多次内存申请和数据搬移操作。

ArrayList<User> users = new ArrayList(9999); 
for (int i = 0; i < 9999; ++i) {
	users.add(xxx);
}

⭐ 下面几点说明数组与容器的适用场景: