Bytebook Compiler

Foundations

Arrays as a Data Structure

Arrays from the data-structure point of view: O(1) access, the cost of insertion and deletion by shifting, and when an array is the right choice.

4 min read3 runnable examples4-question quiz

You already know how to use arrays from the C course. Here we look at them as a data structure: what each operation costs.

An array stores elements in contiguous memory. Because every element has the same size, the address of a[i] is simply base + i × size. That makes access O(1) — the computer jumps straight there.

120251312473584_5_6basea[3]
a[3] is at base + 3 × 4 bytes. No searching needed, so indexing is O(1). The _ cells are spare capacity.

Insertion at a position

To insert at index pos, every element from pos onwards must shift one place right to make room. Inserting at the front of n elements moves all n: O(n).

C
#include <stdio.h>

int insertAt(int a[], int n, int cap, int pos, int value) {
    if (n == cap || pos < 0 || pos > n) return n;      // full or invalid position
    for (int i = n; i > pos; i--)                       // shift right, starting from the end
        a[i] = a[i - 1];
    a[pos] = value;
    return n + 1;                                       // new size
}

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

int main(void) {
    int a[10] = {12, 25, 31, 47, 58};
    int n = 5;
    n = insertAt(a, n, 10, 2, 99);
    print(a, n);
    n = insertAt(a, n, 10, 0, 7);
    print(a, n);
    n = insertAt(a, n, 10, n, 100);   // at the end: no shifting, O(1)
    print(a, n);
    return 0;
}
Output
12 25 99 31 47 58 
7 12 25 99 31 47 58 
7 12 25 99 31 47 58 100
Try it Yourself

Deletion at a position

Deleting shifts the later elements left to close the gap: also O(n) in the worst case.

C
#include <stdio.h>

int deleteAt(int a[], int n, int pos) {
    if (pos < 0 || pos >= n) return n;
    for (int i = pos; i < n - 1; i++)
        a[i] = a[i + 1];
    return n - 1;
}

int main(void) {
    int a[] = {12, 25, 31, 47, 58};
    int n = 5;
    n = deleteAt(a, n, 1);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}
Output
12 31 47 58
Try it Yourself

Array operation costs

Operation Cost Why
Access a[i] O(1) address arithmetic
Update a[i] = x O(1) address arithmetic
Search (unsorted) O(n) may check every element
Search (sorted) O(log n) binary search
Insert / delete at end O(1) nothing to shift
Insert / delete at front or middle O(n) shifting

Strengths and weaknesses

Use an array when you need fast random access by index, the size is known or changes rarely, and you mostly add or remove at the end.

Avoid an array when you insert and delete in the middle a lot, or the size is completely unpredictable — that is where linked lists shine.

Merging two sorted arrays

A pattern you will reuse in merge sort: walk both arrays with two indexes, always taking the smaller front element. It runs in O(n + m).

C
#include <stdio.h>

int main(void) {
    int a[] = {3, 8, 15, 21}, b[] = {1, 9, 10, 22, 30};
    int n = 4, m = 5, c[9], i = 0, j = 0, k = 0;
    while (i < n && j < m) c[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
    while (i < n) c[k++] = a[i++];
    while (j < m) c[k++] = b[j++];
    for (int t = 0; t < k; t++) printf("%d ", c[t]);
    printf("\n");
    return 0;
}
Output
1 3 8 9 10 15 21 22 30
Try it Yourself

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    Why is accessing a[i] O(1)?

  2. 2

    What is the worst-case cost of inserting at the front of an array holding n elements?

  3. 3

    Merging two sorted arrays of sizes n and m takes...

  4. 4

    Which situation suits an array least?

Esc
↑↓ move↵ open