算法零基础一本通(Python版)
上QQ阅读APP看书,第一时间看更新

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)