2-3　新数据插入数组

数组结构虽然好用，但是如果要将新数据插入数组或是删除数组元素，则需要较多的时间，本节讲解如何将新数据插入数组。

2-3-1　假设当下有足够的连续内存空间

数组结构虽然好用，但是如果要将新数据插入数组则需要较多的时间，下列是假设有一个内存内含数组x，此数组有5、3、9，3个数据。

假设现在想要在索引1位置插入一个数据2，数组处理步骤如下：

　步骤1

先确定数组有足够的空间容纳新元素。此时内存空间概念图如下：

　步骤2

由于新数据要放在x[1]索引位置，所以要先将原x[1]及以后的元素往后移动，下列是移动过程与结果。

下列是另一个元素3的移动过程。

　步骤3

将数据2插入索引1位置。

上述在插入数据时，可能要移动所有数组元素，所以时间复杂度是O（n）。

2-3-2　假设当下没有足够的连续内存空间

读者可以想象，有几个朋友相邀去看电影，当坐下来后，有一位新朋友想插入一起坐下看电影，可是当下区间座位有限，这时只好在电影院寻找其他的座位。

假设有一个数组，此数组内含3个数据，此数组内存空间的位置如下：

假设现在想要在索引1位置插入一个数据2，但数组连续空间不足，这时需要向计算机要新的可以容纳数组的连续空间，然后将所有数组内容移至新的内存空间，下列是移动与插入结果。

在没有足够内存空间时插入数据，可能要移动所有数组元素，所以时间复杂度是O（n）。