Arrays: insert, delete and 2D arrays

Introduction

An array is the simplest data structure: items side by side in memory, so a[i] is found in one step. Its weakness is that it has a fixed capacity. A program usually keeps two numbers: the capacity (how many items fit) and the count n (how many are in use).

Arrays are the base of many other structures in this course: stacks, queues, heaps and hash tables can all be built on one. Knowing exactly what an array makes cheap and what it makes expensive explains why those structures look the way they do.

How it works

2D arrays

#include <stdio.h>

int main(void) {
    int m[2][3] = {{1, 2, 3}, {4, 5, 6}};
    int t[3][2];
    for (int r = 0; r < 2; r++)
        for (int c = 0; c < 3; c++)
            t[c][r] = m[r][c];
    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < 2; c++) printf("%d ", t[r][c]);
        printf("\n");
    }
    printf("m[1][2] is item %d in memory\n", 1 * 3 + 2);
    return 0;
}

int m[2][3] is 2 rows of 3 ints. In memory the rows are stored one after another (row-major order), so m[r][c] is item number r * 3 + c. Here we build the transpose t, where row and column swap: t[c][r] = m[r][c].

Syntax

#define CAPACITY 6
int a[CAPACITY] = {5, 8, 13, 21};   // room for 6, four in use
int n = 4;                          // the count, kept beside the array

for (int i = n; i > pos; i--) a[i] = a[i - 1];       // open a gap at pos
for (int i = pos; i < n - 1; i++) a[i] = a[i + 1];   // close the gap at pos

Example

#include <stdio.h>
#define CAPACITY 6

void print(int a[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
}

int insert_at(int a[], int n, int pos, int value) {
    if (n == CAPACITY) return n;   // full: nothing changes
    for (int i = n; i > pos; i--) a[i] = a[i - 1];
    a[pos] = value;
    return n + 1;
}

int delete_at(int a[], int n, int pos) {
    for (int i = pos; i < n - 1; i++) a[i] = a[i + 1];
    return n - 1;
}

int main(void) {
    int a[CAPACITY] = {5, 8, 13, 21};
    int n = 4;
    n = insert_at(a, n, 1, 6);
    print(a, n);
    n = delete_at(a, n, 3);
    print(a, n);
    return 0;
}

• Insert at pos: move items pos .. n-1 one place right, starting from the end, then write the new value. Starting from the front would overwrite values before they are copied.
• Delete at pos: move items pos+1 .. n-1 one place left. The last cell keeps an old copy, but it no longer counts, because n went down.

Both are O(n) in the worst case. Reading or changing a[i] is O(1). insert_at refuses when the array is full; without that check, it would write past the end.

Line by line

1. CAPACITY is the array's room, and n is how many cells are in use.
2. insert_at first refuses when the array is full, and returns n unchanged.
3. Its loop starts at the end, so each value is copied before it is overwritten. Then a[pos] receives the new value.
4. delete_at copies each later item one place left. The old last cell stays, but n - 1 means it no longer counts.
5. main inserts 6 at position 1 and prints, then deletes position 3 and prints again.

Expected result

5 6 8 13 21 
5 6 8 21 

In the real world

A text editor that stored a document in one plain array would have to move every later character on each keypress near the start. That is why editors use cleverer arrangements, and why dynamic arrays such as C++'s vector add at the end but warn that inserting in the middle is slow.

Common mistakes

• Shifting right from the front: for (i = pos; i < n; i++) a[i+1] = a[i]; copies a[pos] into every cell.
• Forgetting to update n after an insert or delete.
• Inserting when n == capacity: there is no room, and C will not stop you. StepVioz will.

Best practices

• Keep the capacity and the count in clearly named variables, or together in a struct.
• Check that a position is between 0 and the count before using it.
• Test inserting at the very start, at the very end and into a full array.

Summary

An array gives O(1) access by index, but inserting or deleting in the middle shifts items and costs O(n). A separate count says how much of the capacity is in use, and a 2D array is stored one row after another.

Mark lesson complete