01. C and Linked Lists

Values, Addresses and Nodes#

An array stores elements consecutively. If a holds integers, a[i] means the integer i element-widths after the first one. A singly linked list instead stores separately allocated nodes, each containing a value and a pointer to the next node. Its order comes from pointers, not from adjacent addresses.

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

struct node * is the type “pointer to a node”. A pointer stores an address; it is not the node itself. p->value follows p to access the node's field, equivalently (*p).value. NULL represents the absence of a node, so it terminates the list and represents the empty list. Never evaluate p->next unless p refers to a live node.

Read the arrows from left to right: head identifies the first node, and each next field identifies the successor. The red cross means there is no next node. It is not an allocated “null node”. For this list, head->next->value is 5. The head variable and the first node are different objects: assigning a new address to head does not change any field in the old first node.

struct node *p = head;
p = p->next;             // changes the local pointer p
head->next = NULL;        // changes a field inside the first node

After the first line update, p refers to the node containing 5, while head still refers to 4. After the field update, a traversal from head reaches only 4. The nodes containing 5 and 7 still exist; if no owner retains a pointer to them, they have become leaked allocations.

Practice. If p = head, does p->value = 20 change what head->value reads? Does p = NULL do the same?

Allocate and Establish Ownership#

malloc reserves storage and returns its address, or NULL on failure. The storage is not automatically initialised. Use sizeof *n so the allocation size follows the pointed-to type:

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

struct node *newNode(int value) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) {
        fprintf(stderr, "allocation failed\n");
        exit(EXIT_FAILURE);
    }
    n->value = value;
    n->next = NULL;
    return n;
}

This teaching program exits on allocation failure. An application may instead return an error to its caller; the important point is that no code dereferences a failed allocation. The returned node is owned by the caller: the caller must eventually free it or transfer that responsibility to a list. A pointer used temporarily for traversal is borrowed; it does not independently own the node.

Prepending: Preserve the Old Head First#

struct node *prepend(struct node *head, int value) {
    struct node *n = newNode(value);
    n->next = head;
    return n;
}

The caller writes head = prepend(head, 3);. First the new node's link is set to the old head; then the returned address becomes the caller's head. Reversing that conceptual order loses the old list unless you saved its address elsewhere.

In the lower state, the new head reaches 3, and 3 reaches the unchanged old list. No existing node moves in memory. Prepending performs one allocation and a fixed number of pointer updates, so its algorithmic work is constant under the usual allocation-cost model. The list still needs one node per item: its total storage is linear in its length.

Appending: Change the Last Link#

struct node *append(struct node *head, int value) {
    struct node *n = newNode(value);
    if (head == NULL) return n;
    struct node *p = head;
    while (p->next != NULL) p = p->next;
    p->next = n;
    return head;
}

The empty case creates the first node. Otherwise the loop stops at the node whose next is null and installs the new successor. The loop maintains the fact that p is a reachable live node in this list. It visits at most all n nodes, so this append is O(n) time and O(1) auxiliary space. A wrapper retaining a tail pointer makes append constant-time, but then every deletion and empty-list transition must keep the tail correct.

Practice. Starting with an empty list, what is the total cost of building n nodes by repeatedly calling this append?

Delete Without Losing the Rest#

Deletion must separate two jobs: unlink the unwanted node, then release its storage. Here we remove the first node equal to value; absent values leave the list unchanged.

struct node *deleteFirst(struct node *head, int value) {
    struct node **link = &head;
    while (*link != NULL && (*link)->value != value) {
        link = &(*link)->next;
    }
    if (*link != NULL) {
        struct node *victim = *link;
        *link = victim->next;
        free(victim);
    }
    return head;
}

link is a pointer to the pointer that currently reaches the candidate node. Initially that pointer is the local head. Later it is a predecessor's next field. *link = victim->next therefore updates exactly the incoming link, allowing the same code to delete a first or interior node. The caller still assigns the returned head.

To delete 5 from 4,5,7, the search reaches the address of 4's next field. It saves the node 5, sets that field to the node 7, then frees 5. Any borrowed pointer still referring to 5 is now invalid. Deleting an already known node is not automatically constant-time in a singly linked list: we also need its incoming link or predecessor.

Practice. Why is free(victim); *link = victim->next; invalid?

Free a Whole List#

void freeList(struct node *head) {
    while (head != NULL) {
        struct node *next = head->next;
        free(head);
        head = next;
    }
}

The saved next remains a pointer to the next live node; we do not read a freed node. Each node is freed once: O(n) time, constant auxiliary space. The caller should stop using its old head and normally set it to NULL; assigning to the function's local head does not clear the caller's variable.

Traverse, Search and Reverse#

#include <stdbool.h>

bool contains(const struct node *head, int value) {
    for (const struct node *p = head; p != NULL; p = p->next) {
        if (p->value == value) return true;
    }
    return false;
}

struct node *reverse(struct node *head) {
    struct node *prev = NULL;
    while (head != NULL) {
        struct node *next = head->next;
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

For reverse, prev is the reversed processed prefix, and head is the unprocessed suffix. Save the original successor before redirecting a link. On 4,5,7, the states are:

At termination the suffix is empty, so prev is the entire reversed list. No node is allocated or freed. Both reversal and unsuccessful search visit n nodes and take linear time. A successful search can stop earlier. Accessing list position i takes i link traversals; unlike an array, there is no constant-time indexed lookup.

Practice. Complete an iterative sum of node values. What assumptions prevent a traversal from running forever?

Wrappers and Recursive Structure#

A wrapper separates information about the list from the nodes:

struct list {
    struct node *head;
    struct node *tail;
    size_t size;
};

The empty representation should satisfy head == NULL, tail == NULL, and size == 0. In a nonempty list, tail->next == NULL, tail is reachable from head, and size equals the number of reachable nodes. These relationships are a representation invariant: facts every public operation must preserve. Maintaining them makes fast operations possible; forgetting them makes later operations incorrect.

The dashed boxes expose a recursive definition: a list is empty, or one node followed by a smaller list. That is why recursive helpers naturally accept a node rather than the whole wrapper. The suffix shares the original nodes; it is not a copied second list.

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. Given head -> 4 -> 7 -> 9, delete the first 7. Which pointer must be saved before free, and what is the resulting chain?

Question 2. Why does void prepend(Node *head, int x) fail to change the caller’s head when it assigns head = fresh? Give two valid interface shapes.

Question 3. Reverse 2 -> 5 -> 8 in place. State prev, curr and the remaining chain immediately after processing the node 5.