1.1.3 数组的基本操作

数组的基本操作包括向数组中插入元素、从数组中删除元素等。

1.向数组中插入元素

前面已经给出了向数组中插入元素的函数，如下。

这个函数的作用是在整型数组中的第index个位置上插入一个整型元素elem。要实现该函数，首先要理解什么是数组的第index个位置以及什么是在数组的第index个位置上插入元素。

这里规定，数组中元素的位置是从1开始的，因此数组元素的下标与数组元素的位置相差1，如图1-3所示。

这是一种约定俗成的规则，很多数据结构的书籍都是这样规定的，所以本书也沿用这一规则。当然，从0开始计算数组中元素的位置也是可以的，大家应当根据具体情况灵活掌握。

所谓在数组的第index个位置上插入元素，就是插入的这个新的元素要位于数组的第index个位置上，原第index个位置上的元素以及后续元素都要顺序向后移动一个位置。

前面已经讲到，数组中的元素之间不能存在“空隙”，因此插入新元素的位置index的取值范围应在1（包含）到elemNumber+1（包含）之间，否则数组中会出现“空隙”，从而无法判断哪些是无效的数组元素，哪些是有效的数组元素。

可以按照下面步骤来实现在数组的第index个位置上插入一个元素。

（1）将数组中第index个元素及之后的所有元素都向后移动一个位置，将数组的第index个位置空出来，如图1-4所示。

需要注意的是，在移动数组元素时要从数组的最后一个元素开始，从后向前逐个移动，直到将第index个元素向后移动一个位置为止。在图1-4中，首先将第5个元素array[4]向后移动一个位置，再将第4个元素array[3]向后移动一个位置，最后将第3个元素array[2]向后移动一个位置。只有按照这种方式移动数组元素，数据才不会被覆盖，最终将数组的第index个位置空出来。

（2）将新的元素插入数组的第index个位置，即array[index-1]=elem；因为数组的下标与数组的位置之间相差1，所以array[index-1]就是数组的第index个元素。如图1-5所示。

经过以上两步操作，可以将元素elem插入数组的第index个位置。最后还要将记录数组元素数量的变量elemNumber加1，表示数组中元素的数量增加了1。

下面给出向数组中插入元素的Java代码描述。

需要指出的是，如果插入元素的位置是elemNumber+1，也就是在数组最后插入一个元素，则不需要执行移动数组元素的操作，直接将元素插入数组的elemNumber+1位置即可。在上面这段代码中，如果函数insertElem()的参数index等于elemNumber+1，则代码中循环移动元素的操作实际上是不被执行的，因为循环变量i的初始值是elemNumber-1，不满足i≥index-1的循环条件，所以上述代码对于向数组的elemNumber+1位置插入一个元素的情形同样适用。

接下来，我们通过一个测试程序来检查这段代码的正确性。

上述这段测试程序模拟了图1-4和图1-5描述的实例。首先初始化一个容量为8的整型数组；然后通过调用MyArray类的insertElem()函数，将整数元素3、5、2、7、8依次插入数组的第1至第5个位置；接下来调用printArray()函数，打印该数组中的内容，该函数定义如下。

最后调用MyArray类的insertElem()函数在数组的第3个位置上插入元素0；再次调用printArray()函数打印该数组中的内容，运行结果如图1-6所示。

图1-6的运行结果是符合预期的，看来insertElem()函数的实现似乎没有什么问题。但是如果我们对测试程序稍加修改，就能发现一些问题。

与之前的测试程序唯一的不同是，在上面这段测试程序中初始化了一个容量为5的数组，而不是容量为8的数组。这时如果在数组的第3个位置上插入元素0，就会抛出一个数组越界异常。因为该数组中已保存了5个数据元素，没有更多的空间存储新的元素了，所以在执行到array.insertElem（0，3）；时会抛出数组越界异常，如图1-7所示。

解决这个问题有两种方法，第1种方法是当数组中的元素数量达到数组的容量上限时，就不允许再向数组中插入新元素，而是直接返回false表示插入元素失败。但是这种方法限定了数组中元素的数量，不够灵活。这里推荐第2种方法——动态扩容方法。当向数组中插入元素，而数组中的元素数量又达到容量上限时，可以调用一个数组扩容方法对数组进行扩容，这样数组的存储空间就会随着数组元素的增多而不断增大，理论上该数组就能存放任意数量的元素了。

下面给出向数组中插入元素的带扩容机制的完整的Java代码描述。

increaseCapacity()函数的实现如下。

每调用一次increaseCapacity()函数，就将数组扩容至原来的2倍，同时保留原数组中已有的元素，这样再向该数组中插入元素时就不会报出数组越界异常了。

2.从数组中删除元素

前面已经给出了从数组中删除元素的函数定义，如下。

该函数的作用是删除数组中第index个位置上的元素。这个过程与插入元素的过程正好相反，我们只需将第index个位置之后的元素（不含第index个位置上的元素）顺序向前移动一个位置，并将数组元素的数量减1，就可以完成删除操作。如图1-8所示。

如图1-8所示，删除第3个元素的方法是将第3个元素（不含）之后的所有元素顺序向前移动一个位置，同时将记录数组元素数量的变量elemNumber减1。

在执行上述删除数组元素的操作时，有几点需要大家特别注意。

（1）被删除数组元素的位置只能在1（包含）到elemNumber（包含）之间，删除其他位置的元素是非法的。

（2）在移动数组元素时要从数组的第index+1个元素开始从前向后逐个进行，直到移动到第elemNumber个元素。如图1-8所示，首先将第4个元素array[3]向前移动一个位置，然后将第5个元素array[4]向前移动一个位置，最后将第6个元素array[5]向前移动一个位置。这样移动数组元素不会覆盖有效的元素值，同时可将第index个位置上的元素覆盖。

（3）数组的元素数量只能通过变量elemNumber记录，所以在删除一个数组元素后一定要将变量elemNumber的值减1，从而保证数组下标在elemNumber-1之外的元素都是无效元素。

下面给出从数组中删除元素的Java代码描述。

至此，我们完成了数组类MyArray的定义，并实现了insertElem()、deleteElem()、increaseCapacity()等基本操作函数。以上完整的代码及测试程序可从“微信公众号＠算法匠人→匠人作品→《算法大爆炸》全书源代码资源→1-1”中获取。