数组概念

1、数组的定义

每一种编程语言中，基本都会有数组，它是一种线性表的数据结构，用一组连续的内存空间来存储一组具有相同类型的数据。

这里，线性表是数据排列成一条线一样的结构，每个线性表上的数据最多只有前和后两个方向。连续的内存空间和相同的数据类型，有了这两个限制，才能让数组可以随机访问。当然有利就有弊，这也让数组的很多操作变得低效，比如，删除和插入操作，为了保证连续性需要做大量的数据移动操作。

一维数组可以看作一个线性表，一维数组的元素有1个下标，如 a[5]。二维数组也可以看作一个线性表X=(X0，X1，X2，…，Xn-1)，只不过每一个数据元素 Xi 也是一个线性表，二维数组的元素中有 2 个下标,如 a[1][5]。

无论是一维还是二维，数组是在内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从 0 开始。

高维数组并不常用，不必深入了解。因此，后面所提及的数组不特指的话，默认的是一维数组。

2、数组如何根据下标实现随机访问的？

假如有一个长度为10的 int 类型的数组，以 Java 语言为例，如下：

int[] a = new int[10]

该数组在内存的示意图，如下：
在这里插入图片描述
从图中可以看到，计算机给数组a分配了一块连续的内存1000-1039，其中内存块的首地址为base_address=1000。

计算机会给每一个内存单元分配一个地址，并通过地址来访问内存中的数据。当计算机要访问数组中的某个元素的时候，就会通过下面公式寻找对应的地址：

a[i]_address = base_address + i*data_type_size

请注意，data_type_size 表示的是数组中每个元素的大小，这里数组是 int 类型，因此 data_type_size = 4。

3、数组的删除和插入操作

插入操作：

假如数组的长度为 n，如果我们需要将一个数据插入到数组中的第 k 个位置，为了把第 k 个位置腾出来，需要把第 k~n 这部分的元素都顺序的往后挪一位，操作复杂。

考虑最好和最坏的情况的话，如果在数组的末尾插入元素，那就不需要移动数据了，插入比较简单，如果在数组的头部插入元素就复杂了，需要把所有的数据都往后移动一位。

如果一个数组中的数据是有序的，那我们在某一个位置插入一个新的元素的时候，就必须得按照上面的方法移动 k 之后的数据，但是数组中存储的数据没有任何规律，这时候，如果想要把某个元素插入到k位置，为了避免大规模的数据搬移，有个简单的办法就是：直接把 k 位置的数据搬到数组的最后面，把新元素放到第 k 个位置。

删除操作：

与插入操作类似，如果我们要删除第 k 个位置的数据，为了保证内存的连续性，也需要移动数据，不然中间就会出现空洞。

在某些情况下，如果我们不要求数据必须是连续的，那么删除的时候可以不真删除，只是把这个元素标记为已删除，当数组空间不够用的时候，在触发一次真正的删除，这样就大大减少了删除操作导致的移动操作。

Java ArrayList

1、ArrayList的使用说明

Java 中的 ArrayList 相当于一个动态数组，支持元素有序的重复的存储，支持扩容。它可以把很多数组操作的细节封装起来，比如插入和删除操作。

数组在定义的时候，因为需要给它分配连续的内存空间，需要预先指定其大小，当存放的数据大于其大小的时候，我们需要从新分配一块更大的空间，把原来的复制过去在插入新的元素。

ArrayList 中，当空间不够用的时候，它会自动扩容为原来的1.5倍的大小。因为扩容设计到内存的申请和数据的搬移，这是比较耗时的，所以，如果事先能确定数据的大小，做好在创建 ArrayList 的时候指定其大小。

虽然 ArrayList 比数组好用，不过有些时候使用数组会更好一些，原因有：

因为 ArrayList 无法存储基本类型，int、long 等需要封装成 Integer、Long 类，而自动装箱和拆箱的操作也会有一定的性能消耗，所以如果关注性能或者想用基本类型的话就选用数组；
如果数据的大小已经知道，并且对数据的操作简单，可以直接使用数组；
当使用多维数组的时候，用数组表示起来更加直观，比如二维数组 int[][]arr ，而用容器的话则需要这样定义 ArrayList arr 。

在开发中，一般情况下直接使用 ArrayList 就可以。如果是偏底层的开发，比如网络框架开发等是需要更高的性能，选用数组实现更合适。