Insertion

The efficiency of inserting a new piece of data into an array depends on where within the array you’re inserting it.

Let’s say we want to add "figs" to the end of our shopping list. Such an insertion takes just one step.

This is true due to another fact about computers: when allocating an array, the computer always keeps track of the array’s size.

When we couple this with the fact that the computer also knows at which memory address the array begins, computing the memory address of the last item of the array is a cinch: if the array begins at memory address 1010 and is of size 5, that means its final memory address is 1014. So to insert an item beyond that would mean adding it to the next memory address, which is 1015.

Once the computer calculates which memory address to insert the new value into, it can do so in one step.

This is what inserting "figs" at the end of the array looks like:

But there’s one hitch. Because the computer initially allocated only five cells in memory for the array, and now we’re adding a sixth element, the computer may have to allocate additional cells toward this array. In many programming languages, this is done under the hood automatically, but each language handles this differently, so I won’t get into the details of it.

We’ve dealt with insertions at the end of an array, but inserting a new piece of data at the beginning or in the middle of an array is a different story. In these cases, we need to shift pieces of data to make room for what we’re inserting, leading to additional steps.

For example, let’s say we want to add "figs" to index 2 within the array. Take a look at the following diagram:

To do this, we need to move "cucumbers", "dates", and "elderberries" to the right to make room for "figs". This takes multiple steps, since we need to first move "elderberries" one cell to the right to make room to move "dates". We then need to move "dates" to make room for "cucumbers". Let’s walk through this process.

Step 1: We move "elderberries" to the right:

Step 2: We now move "dates" to the right:

Step 3: We now move "cucumbers" to the right:

Step 4: Finally, we can insert "figs" into index 2:

Notice that in the preceding example, insertion took four steps. Three of the steps involved shifting data to the right, while one step involved the actual insertion of the new value.

The worst-case scenario for insertion into an array—that is, the scenario in which insertion takes the most steps—is when we insert data at the beginning of the array. This is because when inserting at the beginning of the array, we have to move all the other values one cell to the right.

We can say that insertion in a worst-case scenario can take N + 1 steps for an array containing N elements. This is because we need to shift all N elements over, and then finally execute the actual insertion step.

Now that we’ve covered insertion, we’re up to the array’s final operation: deletion.