Inserting and deleting in an array

An array has no gaps to put a new number in. To insert, every cell after the spot moves one place along. Watch four of them make room for 15.

⋯7int main(void)8{9    int data[8] = { 10, 20, 30, 40, 50 };10    size_t len = 5;11    size_t shifts = 0;12    for (size_t k = len; k > AT; k--) {13        data[k] = data[k - 1];14        shifts++;15    }16    data[AT] = 15;17    len++;18    for (size_t k = 0; k < len; k++)19        printf("%d ", data[k]);20    printf("\n%zu shifts\n", shifts);21    return 0;22}

Length and capacity

An array in C is a fixed run of cells. To use it as a list that grows and shrinks, keep two numbers beside it: the length, how many cells are in use, and the capacity, how many there are. The cells from the length up to the capacity are spare: they exist, and may even hold old values, but they are not part of the list.

Inserting in the middle means making a gap, and the only way to make a gap is to move every cell after it one place along. That is why the cost depends on where.

The code and its cost

Making room

int data[8] = { 10, 20, 30, 40, 50 };
size_t len = 5;
size_t shifts = 0;
for (size_t k = len; k > AT; k--) {
    data[k] = data[k - 1];
    shifts++;
}
data[AT] = 15;
len++;

AT is the index to insert at, fixed when the program is compiled (#define AT 1, or gcc -DAT=3). The loop runs k from len down to AT + 1 and copies cell k − 1 into cell k: cells 4, 3, 2 and 1 each move one place right, starting from the end. Then cell AT is free to overwrite. Inserting at i into len items takes len − i shifts: 5 at the front, 0 at the end.

The direction matters. Copying from the front would write cell 1’s value into cell 2 before cell 2’s own value had been moved, and so on down the line: one value copied over everything (the worked example shows it).

A struct that keeps them together

struct int_array {
    int *data;
    size_t len, cap;
};

The functions take a pointer to the struct, so they can change len. Each refuses when it cannot work, and returns false.

bool insert_at(struct int_array *a, size_t i, int v)
{
    if (a->len == a->cap || i > a->len)
        return false;
    for (size_t k = a->len; k > i; k--)
        a->data[k] = a->data[k - 1];
    a->data[i] = v;
    a->len++;
    return true;
}

bool delete_at(struct int_array *a, size_t i)
{
    if (i >= a->len)
        return false;
    for (size_t k = i; k + 1 < a->len; k++)
        a->data[k] = a->data[k + 1];
    a->len--;
    return true;
}

insert_at is the loop above. delete_at closes the gap the other way: cells i + 1 to len − 1 each move one place left, starting from the front, len − i − 1 moves. Then len drops by one. Nothing is given back: the block keeps all its cells, and the last one still holds its old value, now outside the length.

The program int-array.c also has append, which writes cell len if len < cap; reverse, which swaps the two ends and walks inwards; max, which compares each item with the best so far (it needs len ≥ 1, since it starts from cell 0); and print. Its main makes a block of 8 and calls them in turn.

⋯19bool insert_at(struct int_array *a, size_t i, int v)20{21    if (a->len == a->cap || i > a->len)22        return false;23    for (size_t k = a->len; k > i; k--)24        a->data[k] = a->data[k - 1];25    a->data[i] = v;26    a->len++;27    return true;28}29 30bool delete_at(struct int_array *a, size_t i)31{32    if (i >= a->len)33        return false;34    for (size_t k = i; k + 1 < a->len; k++)35        a->data[k] = a->data[k + 1];36    a->len--;37    return true;38}⋯67int main(void)68{69    struct int_array a = { NULL, 0, 8 };70    a.data = malloc(a.cap * sizeof *a.data);71    if (a.data == NULL)72        return 1;73    for (int v = 1; v <= 5; v++)74        append(&a, v * 10);75    insert_at(&a, 1, 15);76    delete_at(&a, 3);77    reverse(&a);78    print(&a);79    int m = max(&a);80    printf("max %d\n", m);81    free(a.data);82    return 0;83}

After each call the items in use are 10 20 30 40 50; then 10 15 20 30 40 50, after 4 shifts; then 10 15 20 40 50, after 2; then 50 40 20 15 10, after 2 swaps. The program prints 50 40 20 15 10 and max 50.

What each operation costs

Inserting or deleting near the front costs the most; at the end it costs nothing beyond the one write. On average, over every position, about half the items move.

Worked example

Delete at 3. In 10 15 20 30 40 50, deleting the 30 at index 3 moves 40 and 50 one place left: 6 − 3 − 1 = 2 moves, leaving 10 15 20 40 50.

When order does not matter. If the list need not stay in order, delete by moving the last item into the hole and dropping len by one: 1 move, wherever the hole is. Deleting the 30 that way gives 10 15 20 50 40.

At a million. In 10⁶ items, inserting at the front moves all 10⁶. At a random place, the average is about half, 5 × 10⁵ moves.

Shifting from the front, as a mistake.

for (size_t k = i + 1; k <= len; k++)
    data[k] = data[k - 1];

With i = 1 on 10 20 30 40 50, the first pass copies 20 into cell 2, overwriting the 30 before it has moved. The next pass copies that 20 into cell 3, and so on: the cells become 10 20 20 20 20 20. Writing 15 at index 1 then gives 10 15 20 20 20 20. The traced program front-first.c prints exactly those two lines.

Two checks. How many shifts does inserting at index 0 into 7 items take? (7.) How many moves does deleting the last item take? (0.)

Where it’s used

Editors and spreadsheets. A text editor’s table of lines and a spreadsheet’s rows are ordered lists; inserting a row in the middle moves those after it, which is why large files use cleverer structures.

Sorted arrays. An array kept in order for binary search pays this shift on every insertion: finding the place is quick, making room is not.

Fixed buffers. Embedded programs that cannot allocate keep a fixed array with a length beside it, exactly as here.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.