Linked lists

Learning outcomes

Trace insertion, deletion and reversal in a singly linked list, compare list variants, and account for search cost.

8.1 Links rather than consecutive positions

A linked list connects nodes through stored addresses. Nodes need not be adjacent in memory. A head pointer identifies the first node; a null head represents an empty singly linked list. The last node's next link is null.

Lists can grow node by node, but each node carries pointer and allocation overhead. Arrays usually offer better locality and constant-time indexed access. “Dynamic” does not mean that insertion can never fail: allocation can fail.

8.2 Insert at the beginning or after a node

To prepend value x, allocate a new node, set its value, point its next field to the old head, and then make head point to it. This works unchanged for an empty list.

new.next = head
head = new

To insert after a known node p, first set new.next = p.next, then set p.next = new. Reversing those assignments can lose the remainder of the list. Relinking is Θ(1); finding p may be Θ(n).

Appending is Θ(n) if only head is retained and traversal is needed to find the last node. With a valid tail pointer, append is Θ(1), but every operation that empties or changes the last node must maintain tail.

8.3 Remove the first matching value

Search while retaining the current node and its predecessor. If no match exists, return failure without changing the list. If the matching node is head, advance head. Otherwise, set previous.next = current.next. Save any required value, free the removed node and do not use its pointer again.

Deletion by key is O(n) because of the search. Deletion after a known predecessor is Θ(1). In a singly linked list, an arbitrary pointer to a node does not generally provide its predecessor.

8.4 Reverse the links

previous = NULL
current = head
while current != NULL:
    following = current.next
    current.next = previous
    previous = current
    current = following
head = previous

Saving following before reversing the link preserves access to the unprocessed suffix. At every step, previous heads the reversed prefix and current heads the unreversed suffix. Time is Θ(n), auxiliary space Θ(1). Empty and singleton lists need no special branch.

8.5 Variants

For a doubly linked insertion between p and q, connect the new node to both neighbours, then update p.next and q.prev. If either neighbour is absent, update the corresponding endpoint. A circular list with a tail pointer can reach its first node as tail->next when nonempty; deleting its sole node must also reset tail.

A polynomial may be represented as a list of (coefficient, exponent) terms ordered by exponent. Merging two such lists supports addition by combining equal exponents. Eliminate zero-coefficient terms if that is part of the representation invariant.

Practice

1. Prepend 5 to the list in Figure 8.1. Show which links change.
2. Trace reversal of 10 → 20 → 30, recording previous, current and following.
3. State the invariant for an empty and a singleton circular list using tail.
4. Why does a doubly linked list need more writes during insertion than a singly linked list?
5. Design a polynomial-addition procedure for two exponent-sorted term lists.

/* C11. singly linked list, owned by head. */
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int value; struct Node *next; } Node;
static bool prepend(Node **head, int value)
{
    Node *node = malloc(sizeof *node);
    if (node == NULL) return false; /* Leave the existing list unchanged. */
    node->value = value; node->next = *head; *head = node;
    return true;
}
/* Remove the first matching value; pointer-to-pointer also handles the head. */
static bool remove_first(Node **head, int value)
{
    Node **link = head;
    while (*link != NULL && (*link)->value != value) link = &(*link)->next;
    if (*link == NULL) return false;
    Node *victim = *link;
    *link = victim->next;
    free(victim);
    return true;
}
static const Node *find(const Node *head, int value)
{
    while (head != NULL && head->value != value) head = head->next;
    return head;
}
static void clear(Node **head)
{
    while (*head != NULL) {
        Node *next = (*head)->next;
        free(*head); *head = next;
    }
}
int main(void)
{
    Node *head = NULL;
    assert(!remove_first(&head, 10)); assert(find(head, 10) == NULL);
    for (int i = 4; i >= 1; --i) {
        if (!prepend(&head, i * 10)) { clear(&head); return EXIT_FAILURE; }
    }
    assert(find(head, 30) != NULL);
    assert(remove_first(&head, 10)); /* head */
    assert(remove_first(&head, 30)); /* middle */
    assert(!remove_first(&head, 99));
    printf("List:");
    for (const Node *p = head; p != NULL; p = p->next) printf(" %d", p->value);
    putchar('\n');
    assert(remove_first(&head, 40)); /* tail */
    assert(remove_first(&head, 20)); /* sole node */
    assert(head == NULL);
    assert(prepend(&head, 5)); assert(prepend(&head, 5));
    assert(remove_first(&head, 5) && head != NULL && head->value == 5);
    clear(&head); clear(&head); assert(head == NULL);
    puts("linked-list tests passed");
    return EXIT_SUCCESS;
}