1.6　插入

向数组中插入数据的效率取决于你想要插入的位置。

如果想在购物清单末尾加上"figs"，那么只需要1步。

这是由于计算机的另一个特性：在将内存分配给数组时，计算机总是会记录数组的大小。

因为计算机知道数组的起始内存地址，所以计算数组最后一个元素的内存地址就很简单了：如果数组开始于内存地址1010，大小是5，那么它的最后一个内存地址就是1014。要在那之后再添加一个元素，只需放到下一个内存地址1015即可。

一旦计算机算出了存储新值的内存地址，它只需要1步就能完成插入。

下图展示了在数组末尾插入"figs"的过程。

不过还有一个问题。因为计算机本来在内存中给数组分配了5个格子，而现在我们又加了一个元素，所以就得再给数组多分配一个格子。在很多编程语言中，这是自动完成的。但每种编程语言的处理方式不同，这里就不详细介绍了。

以上就是在数组末尾插入元素的过程，但在数组开头或者中间插入新数据就是另一回事了。在这两种情况下，必须移动数据，来给要插入的数据腾出空间。这就需要额外步骤。

假设我们要在索引2处插入"figs"。先来看下图。

为此，需要向右移动"cucumbers"、"dates"和"elderberries"来给"figs"腾出空间。这个过程需要多步，因为需要先把"elderberries"向右移动一个格子，才能移动"dates"。然后，再移动"dates"来给"cucumbers"让位。下面来详细看一下这个过程。

第1步：右移"elderberries"，如下图所示。

第2步：右移"dates"，如下图所示。

第3步：右移"cucumbers"，如下图所示。

第4步：最后，在索引2处插入"figs"，如下图所示。

注意，在这个例子中，插入需要4步，其中3步是数据右移，剩下1步是插入新值。

向数组开头插入元素需要步数最多，也就是所谓的最坏情况。这是因为要在数组开头插入元素，必须把其他所有值都右移一个格子。

对包含N个元素的数组来说，最坏的情况下需要N + 1步插入。这是因为需要移动N个元素，然后才能执行插入操作。

讲完插入，终于可以讲最后一个操作了，那就是删除。