Arrays

An array stores elements of the same type in one contiguous block of memory. That one fact explains almost every strength and weakness of arrays. If the first element starts at address base, and each element occupies size bytes, then element i starts at:

base + i * size

The machine does not need to walk through earlier elements to reach arr[i]; it computes the address directly. This is why indexed access is O(1). The price is that the block is physically ordered: inserting or deleting in the middle means moving elements to keep the sequence compact.

Conceptually, an array is both a storage layout and a data structure interface. The storage layout says “values live next to each other.” The interface usually supports indexed access, traversal, search, insertion, deletion, and sometimes resizing. Only indexed access is automatically fast. Searching for a value and changing the middle of the sequence still require scanning or shifting.

Setup

In C, declaring an array fixes its element type and physical capacity:

int marks[5];                         /* declared, values uninitialized */
int scores[5] = {80, 75, 90, 60, 88}; /* declared and initialized */

For array implementations, always distinguish:

• capacity: how many slots physically exist
• size: how many slots currently contain meaningful values

Traversal should visit 0 through size - 1, not the whole capacity. Insertion is valid only when size < capacity. Deletion reduces size; it does not need to erase the old value beyond the active range.

Traversal

Traversing an array is a sequential scan over contiguous memory:

#include <stdio.h>

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

int linear_search(const int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

Traversal is O(n) because every active element is visited once. Accessing a known index is O(1), but finding a value without additional structure is still O(n).

Addresses

For a 1D array A, the address of A[i] is:

address(A[i]) = base(A) + i * sizeof(element)

For an array indexed from lower to upper instead of from zero:

address(A[i]) = base(A) + (i - lower) * sizeof(element)

C uses zero-based indexing and does not check bounds at runtime. arr[n] is not the last element; it is one past the last valid element. Reading or writing it is undefined behavior.

int safe_get(const int arr[], int n, int index, int *out) {
    if (index < 0 || index >= n) return 0;
    *out = arr[index];
    return 1;
}

Bounds checks are O(1). They do not change the asymptotic cost of indexed access, but they often decide whether the program is correct.

Updates

Appending at the end is O(1) if unused capacity remains. Inserting at the front or middle is O(n) because elements must shift right:

int array_insert(int arr[], int *n, int capacity, int at, int value) {
    if (*n == capacity || at < 0 || at > *n) return 0;
    for (int i = *n; i > at; i--) {
        arr[i] = arr[i - 1];
    }
    arr[at] = value;
    (*n)++;
    return 1;
}

int array_delete(int arr[], int *n, int at) {
    if (at < 0 || at >= *n) return 0;
    for (int i = at; i < *n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    (*n)--;
    return 1;
}

The shift direction matters. During insertion, shift from the end toward the insertion index so values are not overwritten before being copied. During deletion, shift from the deleted index toward the end.

Ordered Arrays

If an array is kept sorted, searching can improve from linear search to binary search: O(log n). Insertion, however, still costs O(n) because even after finding the correct position, values must shift.

int lower_bound(const int arr[], int n, int value) {
    int lo = 0, hi = n;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < value) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int sorted_insert(int arr[], int *n, int capacity, int value) {
    if (*n == capacity) return 0;
    int at = lower_bound(arr, *n, value);
    return array_insert(arr, n, capacity, at, value);
}

Sorted arrays are excellent for repeated search and range queries, but expensive for frequent insertion and deletion.

Dynamic Arrays

A static array cannot grow after declaration. A dynamic array grows by allocating a larger block, copying the old elements, and freeing the old block. This is the idea behind vectors and array lists.

#include <stdlib.h>

typedef struct {
    int *data;
    int size;
    int capacity;
} IntArray;

void ia_init(IntArray *a) {
    a->capacity = 4;
    a->size = 0;
    a->data = malloc(a->capacity * sizeof(int));
}

void ia_push(IntArray *a, int value) {
    if (a->size == a->capacity) {
        a->capacity *= 2;
        a->data = realloc(a->data, a->capacity * sizeof(int));
    }
    a->data[a->size++] = value;
}

void ia_free(IntArray *a) {
    free(a->data);
    a->data = NULL;
    a->size = 0;
    a->capacity = 0;
}

An occasional resize costs O(n), but doubling capacity makes push amortized O(1) over a long sequence of insertions. Growing by a constant amount, such as 10 slots each time, would copy too often and produce O(n^2) total work across n appends.

Resizing

realloc may extend the same block in place, or it may allocate a new block, copy values, free the old block, and return a new pointer. Use a temporary pointer so failed allocation does not lose the old array:

int ia_reserve(IntArray *a, int new_capacity) {
    if (new_capacity <= a->capacity) return 1;
    int *new_data = realloc(a->data, new_capacity * sizeof(int));
    if (new_data == NULL) return 0;
    a->data = new_data;
    a->capacity = new_capacity;
    return 1;
}

A dynamic array owns its backing buffer. Whoever calls ia_init must eventually call ia_free. Forgetting this leaks memory; freeing twice corrupts memory.

2D Arrays

A 2D array represents a rectangular table. In C, A[ROWS][COLS] is stored in row-major order: all of row 0, then all of row 1, and so on. Element A[i][j] is stored at offset:

i * COLS + j

#define MAX_ROWS 10
#define MAX_COLS 10

void fill_matrix(int A[MAX_ROWS][MAX_COLS], int rows, int cols) {
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            A[i][j] = i * cols + j;
        }
    }
}

Accessing A[i][j] is O(1), but inserting or deleting rows and columns requires shifting many cells.

void insert_row(int A[MAX_ROWS][MAX_COLS], int *rows, int cols,
                int at, const int new_row[]) {
    for (int i = *rows; i > at; i--) {
        for (int j = 0; j < cols; j++) {
            A[i][j] = A[i - 1][j];
        }
    }
    for (int j = 0; j < cols; j++) A[at][j] = new_row[j];
    (*rows)++;
}

void delete_row(int A[MAX_ROWS][MAX_COLS], int *rows, int cols, int at) {
    for (int i = at; i < *rows - 1; i++) {
        for (int j = 0; j < cols; j++) {
            A[i][j] = A[i + 1][j];
        }
    }
    (*rows)--;
}

void insert_col(int A[MAX_ROWS][MAX_COLS], int rows, int *cols,
                int at, const int new_col[]) {
    for (int i = 0; i < rows; i++) {
        for (int j = *cols; j > at; j--) {
            A[i][j] = A[i][j - 1];
        }
        A[i][at] = new_col[i];
    }
    (*cols)++;
}

void delete_col(int A[MAX_ROWS][MAX_COLS], int rows, int *cols, int at) {
    for (int i = 0; i < rows; i++) {
        for (int j = at; j < *cols - 1; j++) {
            A[i][j] = A[i][j + 1];
        }
    }
    (*cols)--;
}

Column operations are often less cache-friendly than row operations because they jump across rows instead of moving through consecutive memory.

Matrix Layout

C stores 2D arrays in row-major order. Some languages use column-major order. The logical matrix may be the same, but traversal performance changes.

/* Cache-friendly in C */
for (int i = 0; i < rows; i++)
    for (int j = 0; j < cols; j++)
        sum += A[i][j];

/* Less cache-friendly in C */
for (int j = 0; j < cols; j++)
    for (int i = 0; i < rows; i++)
        sum += A[i][j];

Both loops are O(rows * cols), but the first usually runs faster because it reads consecutive memory.

Matrix Forms

C can represent a matrix as an array of row pointers:

int **matrix = malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
    matrix[i] = malloc(cols * sizeof(int));
}

This is more flexible than int A[ROWS][COLS], but rows may live in different memory blocks. A flattened matrix keeps a single contiguous block:

int get_flat(const int data[], int cols, int i, int j) {
    return data[i * cols + j];
}

When most values are zero, dense matrices waste memory. A sparse matrix can store only non-zero entries:

typedef struct {
    int row;
    int col;
    int value;
} Entry;

This saves memory but makes lookup slower unless the entries are sorted or indexed.

Pitfalls

• Mixing up size and capacity
• Reading arr[n] instead of arr[n - 1]
• Shifting in the wrong direction during insertion
• Forgetting to check capacity before insertion
• Losing the old pointer when realloc fails
• Assuming int ** has the same memory layout as int A[ROWS][COLS]

Costs

Exercises

1. Implement insertion and deletion in a 1D array with explicit size and capacity.
2. Trace the array [10, 20, 30, 40, 50] after inserting 99 at index 2, showing every shift.
3. Implement row insertion and column deletion for a matrix.
4. Explain why A[i][j] is O(1) but inserting a column is not.