Dynamic Data Structures

Dynamic structures allocate nodes as data arrives. They trade the cache locality and constant-time indexing of arrays for flexible growth and efficient relinking. Every implementation needs an explicit invariant and ownership policy.

Singly linked list

struct Node {
    int value;
    struct Node *next;
};

int push_front(struct Node **head, int value) {
    struct Node *node = malloc(sizeof *node);
    if (!node) return 0;
    node->value = value;
    node->next = *head;
    *head = node;
    return 1;
}

Insertion at the head is O(1). Searching and indexing are O(n). The pointer-to-pointer lets the function replace the caller’s head.

Release the complete list without using a freed node:

void list_destroy(struct Node **head) {
    struct Node *current = *head;
    while (current) {
        struct Node *next = current->next;
        free(current);
        current = next;
    }
    *head = NULL;
}

A doubly linked list adds previous links for O(1) removal when a node is already known, at the cost of memory and more invariants.

Stack

A stack follows last-in, first-out order. A linked stack can push and pop at the head in O(1). An array-backed stack is often faster because of locality and fewer allocations; grow it geometrically with checked realloc.

Queue

A linked queue maintains front and rear pointers so enqueue and dequeue are O(1).

struct Queue {
    struct Node *front;
    struct Node *rear;
};

Invariant: both pointers are null for an empty queue; otherwise rear->next is null. Dequeuing the last node must set both pointers to null. A circular array is another strong queue representation when capacity can grow in blocks.

API design and testing

Hide node details behind a module when callers should not manipulate links. Define whether the container owns stored payloads, whether duplicates are allowed, and how allocation failure is reported.

Test empty, one-node, many-node, insertion/removal boundaries, allocation failures, and full destruction. Use sanitizers to catch leaks and invalid links. Big-O describes growth; real performance also depends on allocation cost and cache behavior.