Building data structures in C: linked list, stack & queue

An array is a data structure that stores its elements back to back in RAM. Arrays have one big drawback: their size is fixed and awkward to grow, and inserting or deleting an element in the middle is extremely expensive (every element behind it has to shift). To get around that, programmers reach for dynamically linked structures instead. In this lesson we will combine struct with dynamically allocated pointers to build three classic data structures by hand: the singly linked list, the stack, and the queue.

1. Performance at the hardware level: CPU cache locality & spatial locality

Before we get into the code, we need to understand what the hardware is doing: why, at exactly the same algorithmic complexity, does walking an array sequentially run tens of times faster than walking a linked list? The answer is CPU cache locality.

What a cache line is, and why memory is fetched ahead of time:

The CPU never reads individual bytes straight out of RAM, because RAM is far too slow (hundreds of times slower than the CPU's own compute speed). Instead, on every read the CPU pulls in a contiguous block called a cache line (typically 64 bytes) from RAM into the fast L1/L2/L3 caches.

The principle of spatial locality:

When you access element arr[0] of an array:

• The system loads arr[0], arr[1], arr[2], arr[3]… (up to 64 contiguous bytes) into the CPU cache in a single read.
• When the loop reaches arr[1], the CPU does not touch RAM at all — it takes the value straight from L1 cache. That is a cache hit (extremely fast, under 1 ns).

With a linked list, the opposite happens:

• Nodes are allocated dynamically through malloc() at different moments, so they end up scattered at random across the heap.
• When you follow node1->next, the next node's address usually lives in a completely different region of RAM. The CPU is forced to discard the cached line and issue a fresh RAM read. That is a cache miss. Hitting cache misses over and over makes walking a linked list very slow on modern CPUs (the phenomenon known as the memory wall).

Array (contiguous memory):
[ Node 0 ][ Node 1 ][ Node 2 ][ Node 3 ] <--- whole block loaded into CPU cache in 1 cycle

Linked list (scattered memory):
[ Node 0 ] ----(pointer to a random address)---> [ Node 1 ] (cache miss!)
  Address: 0x1000                                 Address: 0x5000
              

2. Costing an algorithm: complexity and Big O notation

When you design a piece of software or solve a problem, there are usually several algorithms to choose from. To judge which one runs faster or uses fewer machine resources, computer science uses the mathematical notation called Big O.

Big O measures the growth rate of the number of basic operations (time complexity) or of the extra RAM consumed (space complexity) as the input size ($N$) tends to infinity ($N \to \infty$).

How the common Big O classes grow:

Growth rate (running time / number of operations)
 ^
 |                                                    / O(2^N) (exponential - worst of all)
 |                                                   /
 |                                                  /   / O(N^2) (quadratic - bad once N is large)
 |                                                 /   /
 |                                                /   /     / O(N log N) (good - quick/merge sort)
 |                                               /   /     /
 |                                              /   /     /   / O(N) (linear - scanning an array)
 |                                             /   /     /   /
 |                                            /   /     /   /     / O(log N) (logarithmic - binary search)
 |                                           /   /     /   /     /
 |                                          /   /     /   /     /_______ O(1) (constant - instant operations)
 +-----------------------------------------------------------------------> Input size (N)
              

2.1. The underlying maths and the simplification rules

Formally, we say $f(N) = O(g(N))$ if there exist positive constants $c$ and $N_0$ such that:

\(f(N) \le c \times g(N) \quad \text{for all} \quad N \ge N_0\)

In practical analysis we always apply two core simplifications:

• Drop the constant factors: an algorithm costing $3N$ steps and one costing $100N$ steps are both $O(N)$, because a constant multiplier does not change the shape of the growth curve once $N$ becomes very large.
• Keep only the dominant term: for a cost function $f(N) = 3N^2 + 50N + 1000$, at $N = 1{,}000{,}000$ the term $3N^2$ ($3 \times 10^{12}$) utterly dwarfs $50N$ ($5 \times 10^7$) and the constant $1000$. So we discard the lower-order terms and write it simply as $O(N^2)$.

2.2. Two rules for reading real source code

1. The sum rule: if the algorithm consists of blocks that run one after another: \(O(f(N)) + O(g(N)) = O(\max(f(N), g(N)))\)
   Example: block 1 scans the array once ($O(N)$), block 2 has two nested loops ($O(N^2)$). The total is $O(N + N^2) = O(N^2)$.

2. The product rule: if the algorithm has nested loops or repeated function calls: \(O(f(N)) \times O(g(N)) = O(f(N) \times g(N))\)
   Example: the outer loop runs $N$ times and the inner loop runs $N$ times. The total is $O(N \times N) = O(N^2)$.

2.3. The time complexity classes in detail

1. $O(1)$ — constant time

The running time never changes, entirely independent of $N$. Note: a function containing a loop with a fixed iteration count (say exactly 1000 rounds) still counts as $O(1)$.

// Direct access to a cell by array index is O(1)
int getElement(int arr[], int index) {
    return arr[index];
}

// A loop of a fixed 100 iterations, independent of N, is still O(1)
void printHeader() {
    for (int i = 0; i < 100; i++) {
        printf("-");
    }
}

Both functions are O(1), even though the second one runs 100 iterations. The key point: Big O measures how fast the cost grows with N, not the absolute number of operations. A fixed 100 rounds is still 100 rounds whether N is 10 or 10 million — it does not grow with N, so it stays constant.

2. $O(\log N)$ — logarithmic time

Extremely efficient. After each operation, the space still to be searched or processed is halved. The base-2 logarithm ($\log_2 N$) is exactly the number of times you can divide $N$ by 2 before the result drops to 1 or below.

// Binary search over a sorted array
int binarySearch(int arr[], int size, int target) {
    int left = 0, right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // Avoids integer overflow
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1; // Discard the left half
        else right = mid - 1;                // Discard the right half
    }
    return -1;
}

Every iteration throws away half of the remaining elements — that is the signature of O(log N). For an array of a million elements, binary search needs about 20 steps at most. The line left + (right - left) / 2 is written that way rather than (left + right) / 2 to avoid integer overflow when both indices are large — a bug that survived for years inside the Java standard library.

3. $O(N)$ — linear time

The running time grows in direct proportion to $N$. The classic cases are algorithms that scan an array with a single loop, or walk a linked list.

// Walk the whole array, searching sequentially
int linearSearch(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) return i; // Worst case visits all N elements
    }
    return -1;
}

The difference from the binary version above: this function does not require the array to be sorted, and the price it pays is having to walk it sequentially. For an array of a million elements, the worst case is a million comparisons rather than 20. That gap is precisely the difference between O(N) and O(log N).

4. $O(N \log N)$ — linearithmic time

This is the mathematical lower bound for comparison-based sorting algorithms (merge sort, quicksort, heapsort). The algorithm splits the data in half $\log N$ times, and at each level of the split it performs a linear $O(N)$ merge or scan.

5. $O(N^2)$ — quadratic time

The running time grows with the square of the input size. It shows up readily in elementary sorting algorithms (bubble sort, selection sort) and in processing an $N \times N$ matrix.

// Print every pair of elements in the array
void printAllPairs(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) { // Shrinks as i grows
            printf("(%d, %d)\n", arr[i], arr[j]); // Still O(N^2)
        }
    }
}

Notice the inner loop starts at i + 1 rather than 0, so the total number of iterations is roughly N²/2, not N². But Big O drops constants, so it is still O(N²) — and that means something real: double N and the running time goes up fourfold.

6. The dangerous classes: $O(2^N)$ and $O(N!)$

• $O(2^N)$ — exponential time: a truly terrifying growth rate, doubling the number of operations every time $N$ goes up by 1. The classic examples are naive recursive Fibonacci and generating every binary string of length $N$.

  // Naive recursive Fibonacci (no memoisation) costs O(2^N)
  int fibonacci(int n) {
      if (n <= 1) return n;
      return fibonacci(n - 1) + fibonacci(n - 2); // Each parent spawns 2 branches
  }

• $O(N!)$ — factorial time: the worst complexity class in computing. At just $N = 20$, even a supercomputer would run for decades. The classic example is brute-force enumeration of permutations (for instance solving the travelling salesperson problem by exhaustive search).

2.4. The three cases an algorithm is judged on (best, average, worst)

• Best case ($\Omega$ — omega): the fewest steps, on the most favourable input (for example finding the element right at arr[0], costing $O(1)$). Rarely of practical value.
• Worst case ($O$ — Big O): the upper bound, guaranteeing that the running time cannot exceed this figure however bad the input is. This is the most important measure in software development.
• Average case ($\Theta$ — theta): the one that reflects how the application really performs in practice, on randomly distributed data.

2.5. Space complexity & call stack depth

Space complexity measures the extra RAM (beyond the original input data) an algorithm consumes over its lifetime.

• Heap space: what you allocate deliberately with calls such as malloc() or calloc().
• Stack space (call stack depth): this is the part that causes stack overflow. When a function recurses, the machine has to allocate a stack frame on the call stack to hold the return address and that call's local variables. That block is only released when the call finishes.

Compare the memory cost of the recursive approach against an ordinary loop:

// OPTION 1: RECURSION (sum from 1 to N)
// Recurses N deep, so the call stack holds N stack frames at once
// => Time: O(N) | Space: O(N) (easy to blow the stack for large N)
int sumRecursive(int n) {
    if (n <= 1) return n;
    return n + sumRecursive(n - 1);
}

// OPTION 2: ITERATION (sum from 1 to N)
// Uses one fixed sum variable, in a single stack frame
// => Time: O(N) | Space: O(1) (safe, and minimal RAM)
int sumIterative(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

3. The singly linked list

A linked list is built out of many separate data cells called nodes.

Each node has two parts:

• Data: the actual value being stored (an integer, a struct, and so on).
• Next: a pointer to the next node in the list. The final node points at NULL to mark the end.

A picture of it:

Head -> [ Data | Next ] ---> [ Data | Next ] ---> [ Data | Next ] ---> NULL
              

Let's run a program that builds and prints a singly linked list:

#include <stdio.h>
#include <stdlib.h>

// Define one node of the list
typedef struct Node {
    int data;
    struct Node *next; // Pointer to the next node
} Node;

// Allocate and initialise a new node
Node* createNode(int value) {
    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// Insert a new node at the head of the list
void insertAtHead(Node **head, int value) {
    Node *newNode = createNode(value);
    newNode->next = *head;
    *head = newNode;
}

// Print every node in the list
void printList(Node *head) {
    Node *temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    Node *head = NULL; // The list starts out empty

    insertAtHead(&head, 30);
    insertAtHead(&head, 20);
    insertAtHead(&head, 10);

    printf("Linked list: ");
    printList(head); // Output: 10 -> 20 -> 30 -> NULL

    // Free every node before leaving the program
    Node *temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

📥 Download the sample source: linked_list.c

4. The stack (LIFO)

A stack works on the last in, first out principle. Like a pile of plates, the plate put down last is the first one taken off.

A stack has two basic operations:

• Push: put an element on the top of the stack.
• Pop: take the element off the top and return its value.

#include <stdio.h>
#include <stdlib.h>

typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode;

// Push an element onto the stack
void push(StackNode **top, int value) {
    StackNode *newNode = (StackNode*) malloc(sizeof(StackNode));
    newNode->data = value;
    newNode->next = *top;
    *top = newNode;
    printf("Pushed: %d\n", value);
}

// Pop an element off the stack
int pop(StackNode **top) {
    if (*top == NULL) {
        printf("Stack is empty!\n");
        return -1;
    }
    StackNode *temp = *top;
    int poppedValue = temp->data;
    *top = (*top)->next;
    free(temp);
    return poppedValue;
}

int main() {
    StackNode *top = NULL;

    push(&top, 100);
    push(&top, 200);
    push(&top, 300);

    printf("Popped: %d\n", pop(&top)); // 300 (last in, first out)
    printf("Popped: %d\n", pop(&top)); // 200

    // Free whatever is left on the stack
    while(top != NULL) {
        pop(&top);
    }

    return 0;
}

Worth noticing: both push and pop only ever touch the head of the list, so both are O(1) no matter how many elements the stack holds. That is why stacks are used wherever predictable speed matters — including the call stack the CPU itself uses for function calls, as we saw in Lesson 5.

5. The queue (FIFO)

A queue works on the first in, first out principle. Like a queue at a ticket office, whoever arrives first is served and leaves first.

A queue has two basic operations:

• Enqueue: add an element at the rear of the queue.
• Dequeue: take the element at the front out of the queue.

#include <stdio.h>
#include <stdlib.h>

typedef struct QNode {
    int data;
    struct QNode *next;
} QNode;

typedef struct {
    QNode *front;
    QNode *rear;
} Queue;

// Create an empty queue
Queue* createQueue() {
    Queue *q = (Queue*) malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

// Add an element at the rear of the queue
void enqueue(Queue *q, int value) {
    QNode *temp = (QNode*) malloc(sizeof(QNode));
    temp->data = value;
    temp->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = temp;
        printf("Enqueued: %d\n", value);
        return;
    }

    q->rear->next = temp;
    q->rear = temp;
    printf("Enqueued: %d\n", value);
}

// Remove the element at the front of the queue
int dequeue(Queue *q) {
    if (q->front == NULL) {
        printf("Queue is empty!\n");
        return -1;
    }

    QNode *temp = q->front;
    int val = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    return val;
}

int main() {
    Queue *q = createQueue();

    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);

    printf("Dequeued: %d\n", dequeue(q)); // 10 (first in, first out)
    printf("Dequeued: %d\n", dequeue(q)); // 20

    // Free whatever is left in the queue
    while(q->front != NULL) {
        dequeue(q);
    }
    free(q);

    return 0;
}