RavnaryA Knowledge Platform
Colour theme

Card 03/ 09

Take the quiz

ExampleDifficulty: Beginner2 min

Array Example: Inserting at the Front

Every existing element moves one cell right before the new one fits.

Inserting into an array costs one shift for every element at or after the insertion point, because the cells are contiguous and the new element needs a free one. This card covers that cost by tracing an insert at the front, then states it for every position, and for deletion.

An array holds 4 7 2 5 1 and has room for a sixth element. Writing 9 straight into index 0 would destroy the 4. Every element first moves one cell right, starting from the end, so that nothing is overwritten before it has been copied.

Before the trace: how many elements move to make room for the 9?

All five, each by exactly one cell.

In the trace, i marks the cell being filled.

Inserting 9 at index 0

Input4 7 2 5 1 in an array with room for six

  1. Start: cell 5 is free

    1. 4
    2. 7
    3. 2
    4. 5
    5. 1
    6. _i

    Five elements fill cells 0 to 4, and cell 5 is free.

  2. Copy cell 4 into cell 5

    1. 4
    2. 7
    3. 2
    4. 5
    5. 1
    6. 1i

    1 is copied right; cell 4 keeps a stale copy until something overwrites it.

  3. Copy cell 3 into cell 4

    1. 4
    2. 7
    3. 2
    4. 5
    5. 5i
    6. 1

    5 is copied right, over the stale 1.

  4. Copy cell 2 into cell 3

    1. 4
    2. 7
    3. 2
    4. 2i
    5. 5
    6. 1

    2 is copied right.

  5. Copy cell 1 into cell 2

    1. 4
    2. 7
    3. 7i
    4. 2
    5. 5
    6. 1

    7 is copied right.

  6. Copy cell 0 into cell 1

    1. 4
    2. 4i
    3. 7
    4. 2
    5. 5
    6. 1

    4 is copied right, and cell 0 is free to overwrite.

  7. Write 9 into cell 0

    1. 9i
    2. 4
    3. 7
    4. 2
    5. 5
    6. 1

    9 is written into cell 0: five shifts and one write.

ResultFive elements moved one cell each: inserting at the front of n elements makes n shifts.

The number of shifts depends on how many elements sit at or after the insertion point, not on the value inserted. A run of the same insert at each index of the five-element array, and of a delete from each index, counted them:

Shifts in an array of five elements, counted by a run
Index iShifts to insertShifts to delete
054
143
232
321
410
50No element there

With n elements, inserting at index i makes n − i shifts and deleting at i makes n − i − 1. Appending at the end is O(1), the front is O(n), and the cost falls steadily in between; at n = 1,000,000 the same run's insert at the front made 1,000,000 shifts. A Python list is this kind of array, which is why Python's documentation recommends collections.deque rather than a list for a queue that removes from the front.

← → move through sections and cards