本章内容

数组定义

数组（Array）是一种线性表数据结构，它用一组连续的内存空间来存储一组具有相同类型的数据。

如图所示：

线性表

线性表指的是n个具有相同特性的数据元素的有限序列，如：数组、链表、队列、栈等。

根据下标随机访问

数组定义中，连续的内存空间和相同类型的数据使得根据下标随机访问元素变得非常高效。同时，为了保证数组内存空间的连续性，在数组中添加、删除元素时，需要对数组中的其他元素进行迁移，因此，向数组中添加、删除元素的效率较低。

例如：一个长度为10的int类型的数组int[] a = new int[8]，计算机给数组a[8]分配了一块连续内存空间：10000～10031，其中，内存块的起始地址为：base_address = 10000。

如图所示：

图中，计算机会为每个内存单元分配一个地址，通过该地址来访问内存中的数据。当计算机需要随机访问数组中的某个元素时，首先会计算出该元素存储的内存地址，计算公式：

a[i]_address = base_address + i * data_type_size

其中：

• base_address：内存块的起始地址。
• i：数组下标。
• data_type_size：数组元素类型大小（int类型为4个字节）。

如：访问下标为5的元素a[5]时，a[5]的内存地址为：10000+5*4=10020。因此，根据下标随机访问数组元素的时间复杂度为O(1)。

数组操作

添加元素

向一个长度为n的数组中的第k个位置插入一个元素x，需要将数组中k～n这部分元素向后移动一位：

• 如果是在数组的末尾插入元素x，则不需要移动数组中的元素，即：最好情况的时间复杂度为O(1)。
• 如果是在数组的开头插入元素x，则需要将数组中所有的元素向后移动一位，即：最坏情况的时间复杂度为O(n)。
• 由于在数组中每个位置插入元素x的概率一样，因此，平均时间复杂度为(1+2+...n)/n=O(n)。

如果是有序数组，在数组中某个位置插入一个新元素时，需要按照以上方法进行数据迁移。

如果是无序数组，在数组中某个位置插入一个新元素时，可以先将待插入位置的元素移动到数组元素的末尾，再将待插入元素插入到指定位置，这样可以避免其他元素的移动，时间复杂度为O(1)。

删除元素

删除元素与插入元素类似，如果删除数组末尾的数据，则最好情况时间复杂度为 O(1)；如果删除开头的数据，则最坏情况时间复杂度为 O(n)；平均情况时间复杂度为 O(n)。

在某些特殊场景下，并不一定非得追求数组中数据的连续性。如果将多次删除操作集中在一起执行，则可以先记录下待删除的元素（即：将待删除的元素打上删除标识），当数组没有更多空间存储元素时，再触发真正的元素删除操作，这样就可以大大减少数组中元素的迁移次数。

数组与容器

在Java中，数组对应的容器为ArrayList，ArrayList相对于数组，最大的优势是封装了对数组操作的细节（如：数组插入、删除数据时需要迁移其他元素等）。另外，ArrayList支持动态扩容。

动态扩容

数组扩容

定义数组时，由于数组需要分配连续的内存空间，因此，需要预先指定数组大小。如：申请一个大小为10的数组，向数组中添加10个元素（即：容量已满），当向数组中添加第11个元素时，就需要重新申请一块更大的内存空间（即：扩容），并将原数组中已经存在的10个元素复制并添加到新数组中，再将第11个元素也添加新数组中，实现数组扩容。

容器扩容

定义ArrayList时，可以不预先指定容器大小（默认大小为10）。向容器中添加元素时，如果容量已满，则会自动将容量扩容为原大小的1.5倍。

注意：扩容操作涉及内存重分配和数据迁移，会存在一定的性能消耗，因此，在确定数据范围的情况下，建议在创建容器时预先指定容器的大小，避免因频繁扩容而影响性能。

数组使用场景分析

在开发过程中，大部分场景可以直接使用容器进行业务开发，但是对于某些特殊的场景，可以使用数组来降低性能消耗：

• 存储Java基本类型数据：ArrayList无法存储基本类型，如果要存储（如：int、long等）基本类型数据，需要将基本类型封装为对应的包装类（如：Integer、Long等），而对数据的包装与拆装存在一定的性能消耗，因此，可以选用数组来存储基本类型数据。
• 数据范围确定且数据操作简单：可以直接使用数组，定义数组时预先指定数组大小，并使用数组原生API对数据进行操作，减少没必要的性能消耗。

数组常见问题

为什么大多数编程语言中数组下标从0开始？

1）性能原因，数组下标表示元素的在内存块中的偏移量，用来根据数组的起始地址快速定位元素所在的位置，计算公式：

a[i]_address = base_address + i * data_type_size

其中：base_address为数组的起始地址。

如果数组下标从1开始，数组元素a[k]的内存地址的计算公式变为：

a[k]_address = base_address + (k-1)*type_size

其中：随机访问数组元素都多了一次减法运算，对于CPU来说，就是多了一次减法指令。

2）历史原因，C语言中数组下标从0开始，后面的高级语言（如：Java）为了降低学习成本，继续沿用了C语言中数组的设计习惯。

【阅读推荐】

想了解常用算法（如：快速排序、堆与堆排序、二分查找、动态规划、广度优先搜索算法（BFS）、深度优先搜索算法（DFS）等）的童鞋请移步->算法系列合集（持续更新中）。

更多内容持续更新中......

【作者简介】

一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～