Linked Lists

A linked list stores each element in a separately allocated node. A node contains data plus one or more pointers that connect it to neighboring nodes. Unlike arrays, list nodes do not need to sit next to each other in memory. This makes insertion and deletion cheap when you already have the right pointer, but it makes indexed access expensive because the only way to reach the ith node is to follow links from the head.

The main idea is link-based sequencing. The order of values is not determined by physical memory addresses; it is determined by pointers. This gives linked lists their flexibility, but it also means every operation must preserve pointer invariants exactly. One wrong assignment can lose the rest of the structure.

Singly Linked List

Each node points to the next node:

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

The learner-friendly way to make linked list code modular is not to hide the whole structure behind many files. Start with one function per responsibility: one function creates a node, one inserts, one traverses, one searches, one deletes, and one frees the list. This keeps the program readable while still avoiding repeated pointer logic.

Node Creation

Node creation should be isolated in one function. Any function that needs a new node can call it instead of repeating malloc, assignment, and next initialization.

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

Node *createNode(int data) {
    Node *newNode = malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }

    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

This function returns a pointer to a new node. If memory allocation fails, it returns NULL. Checking this result is important because inserting a NULL node would corrupt the list.

List State

The simplest linked list representation stores only a pointer to the first node:

Node *head = NULL;

head == NULL means the list is empty. If head points to a node, that node is the first element. The last node has next == NULL. Every operation must preserve this chain.

Other representations may also store tail and size, but the head-only form makes the ownership path visible first. Adding a tail pointer then becomes a deliberate optimization with another invariant to maintain.

Head Return

There are two common ways to let a function change the first node:

• Pass the address of head.
• Return the updated head.

Returning the updated head keeps the changed ownership visible at the call site:

head = insertBegin(head, 30);
head = deleteNode(head, 30);

This style avoids double pointers while still handling operations that change the first node. The rule is simple: if a function might change the first node, assign its return value back to head.

List Traversal

Traversal visits every node from head to NULL.

void display(Node *head) {
    Node *current = head;

    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }

    printf("NULL\n");
}

The traversal pointer current moves through the list. The original head is not changed. This is important: traversal should inspect the list, not destroy it.

Traversal is O(n) because every node must be visited once. There is no direct indexing like arr[i].

Use while (current != NULL), not while (current->next != NULL). The second version skips the last node and crashes when the list is empty because it tries to read current->next before proving that current exists.

List Search

Searching is also a traversal, but it stops early if the target is found.

Node *search(Node *head, int key) {
    Node *current = head;

    while (current != NULL) {
        if (current->data == key) {
            return current;
        }
        current = current->next;
    }

    return NULL;
}

The function returns a pointer to the matching node. If no node contains the target, it returns NULL. This makes the function useful for later operations such as inserting after a specific value.

Insertion

Head insertion is the simplest insertion. The new node becomes the first node.

Node *insertBegin(Node *head, int data) {
    Node *newNode = createNode(data);
    if (newNode == NULL) {
        return head;
    }

    newNode->next = head;
    return newNode;
}

The caller must store the returned pointer:

head = insertBegin(head, 30);

This matters because inserting at the front changes the first node. If the caller ignores the return value, the new head is lost.

Tail Insert

Tail insertion adds a node at the end. With only a head pointer, the function must traverse to the last node.

Node *insertEnd(Node *head, int data) {
    Node *newNode = createNode(data);
    if (newNode == NULL) {
        return head;
    }

    if (head == NULL) {
        return newNode;
    }

    Node *current = head;
    while (current->next != NULL) {
        current = current->next;
    }

    current->next = newNode;
    return head;
}

Tail insertion is O(n) in this version because finding the last node takes time. If a program inserts at the tail frequently, adding a separate tail pointer can reduce this operation to O(1).

Insert After

Insertion after a target value has two steps: find the target node, then reconnect pointers.

int insertAfter(Node *head, int key, int data) {
    Node *targetNode = search(head, key);
    if (targetNode == NULL) {
        return 0;
    }

    Node *newNode = createNode(data);
    if (newNode == NULL) {
        return 0;
    }

    newNode->next = targetNode->next;
    targetNode->next = newNode;

    return 1;
}

The order of pointer assignments is important. First point the new node at the old successor. Then point the target node at the new node. Reversing those two lines loses the rest of the list.

List Deletion

Head deletion removes the first node and returns the new head.

Node *deleteBegin(Node *head) {
    if (head == NULL) {
        return NULL;
    }

    Node *oldHead = head;
    head = head->next;
    free(oldHead);

    return head;
}

The function saves the old head before moving head. If you move head first without saving the old node, you lose the pointer needed for free.

Delete by Value

Deleting by value requires tracking both current and previous.

Node *deleteNode(Node *head, int key) {
    if (head == NULL) {
        return NULL;
    }

    if (head->data == key) {
        printf("Deleted %d\n", key);
        return deleteBegin(head);
    }

    Node *previous = head;
    Node *current = head->next;

    while (current != NULL && current->data != key) {
        previous = current;
        current = current->next;
    }

    if (current == NULL) {
        printf("%d not found\n", key);
        return head;
    }

    previous->next = current->next;
    free(current);
    printf("Deleted %d\n", key);

    return head;
}

Deletion has two jobs: unlink the node and free its memory. Doing only the first leaks memory. Doing only the second leaves a dangling pointer inside the list.

Cleanup

Every node allocated by createNode must eventually be freed.

void free_list(Node *head) {
    Node *current = head;

    while (current != NULL) {
        Node *next = current->next;
        free(current);
        current = next;
    }
}

Saving next before freeing current is essential. After free(current), reading current->next is undefined behavior.

Putting It Together

The functions are modular, but still easy to follow because the program uses one Node *head.

int main(void) {
    Node *head = NULL;

    head = insertEnd(head, 10);
    head = insertEnd(head, 20);
    head = insertBegin(head, 5);
    insertAfter(head, 10, 15);

    display(head);  /* 5 -> 10 -> 15 -> 20 -> NULL */

    if (search(head, 15) != NULL) {
        printf("15 found\n");
    }

    head = deleteNode(head, 20);
    head = deleteBegin(head);

    display(head);  /* 10 -> 15 -> NULL */

    free_list(head);
    return 0;
}

This modular form gives each operation its own function while keeping every change to the head pointer visible.

Doubly Linked List

A doubly linked list stores both next and prev pointers. This costs more memory per node, but it allows O(1) deletion when you already have a pointer to the node itself.

typedef struct DNode {
    int value;
    struct DNode *prev;
    struct DNode *next;
} DNode;

DNode *dlist_remove(DNode *head, DNode *node) {
    if (node->prev) {
        node->prev->next = node->next;
    } else {
        head = node->next;
    }

    if (node->next) {
        node->next->prev = node->prev;
    }
    free(node);

    return head;
}

The invariant is two-directional: if a->next == b, then b->prev must be a. A deletion or insertion that updates only one direction leaves the list structurally inconsistent.

Doubly Insertion

The short wiring example below assumes that allocation succeeds and that cur is a valid node. If malloc returns NULL, it dereferences a null pointer. Use it only to study the four link changes; the checked version immediately afterward validates its inputs, reports failure, and leaves the list unchanged when allocation fails.

DNode *dnode_new(int value) {
    DNode *node = malloc(sizeof(DNode));
    node->value = value;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

DNode *dlist_insert_front(DNode *head, int value) {
    DNode *node = dnode_new(value);
    node->next = head;
    if (head != NULL) {
        head->prev = node;
    }
    return node;
}

DNode *dlist_insert_after(DNode *cur, int value) {
    DNode *node = dnode_new(value);
    node->prev = cur;
    node->next = cur->next;
    if (cur->next != NULL) {
        cur->next->prev = node;
    }
    cur->next = node;

    return node;
}

Here is the same operation with an explicit failure contract:

static DNode *dnode_new_checked(int value) {
    DNode *node = malloc(sizeof *node);
    if (node == NULL) {
        return NULL;
    }

    node->value = value;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

int dlist_insert_front_checked(DNode **head, int value) {
    if (head == NULL) {
        return 0;
    }

    DNode *node = dnode_new_checked(value);
    if (node == NULL) {
        return 0;
    }

    node->next = *head;
    if (*head != NULL) {
        (*head)->prev = node;
    }
    *head = node;
    return 1;
}

int dlist_insert_after_checked(DNode *cur, int value,
                               DNode **inserted) {
    if (inserted != NULL) {
        *inserted = NULL;
    }
    if (cur == NULL) {
        return 0;
    }

    DNode *node = dnode_new_checked(value);
    if (node == NULL) {
        return 0;
    }

    node->prev = cur;
    node->next = cur->next;
    if (cur->next != NULL) {
        cur->next->prev = node;
    }
    cur->next = node;

    if (inserted != NULL) {
        *inserted = node;
    }
    return 1;
}

Both insertion functions return 1 only after every required link has been committed. A return value of 0 means no node was inserted. Passing &head lets front insertion publish the new head only after allocation succeeds; the optional inserted output gives the caller the new interior node without hiding failure in a null data value.

When drawing a doubly linked insertion, draw four arrows: node->prev, node->next, previous node’s next, and next node’s prev.

Circular Linked List

In a circular linked list, the last node points back to the first. There is no NULL terminator, so traversal must stop when it returns to the starting node.

Node *circular_insert_tail(Node *tail, int data) {
    Node *node = createNode(data);
    if (node == NULL) {
        return tail;
    }

    if (tail == NULL) {
        node->next = node;
        return node;
    } else {
        node->next = tail->next;
        tail->next = node;
        return node;
    }
}

void circular_print(const Node *tail) {
    if (tail == NULL) {
        return;
    }
    const Node *cur = tail->next;
    do {
        printf("%d ", cur->data);
        cur = cur->next;
    } while (cur != tail->next);
    printf("\n");
}

A tail pointer is especially useful here: tail gives the last node, while tail->next gives the head. That makes insertion at the back efficient.

Circular lists are useful for cyclic processing: round-robin scheduling, multiplayer turns, rotating buffers, and repeated polling. Their danger is infinite traversal. A traversal must know where it started or maintain a count.

Reversal

Reversal is a standard pointer exercise: keep prev, cur, and next.

Change the node values below, then step through the exact moment each link changes direction. Moving backward exposes why the unreversed suffix would be lost if next were not saved first.

Node *list_reverse(Node *head) {
    Node *prev = NULL;
    Node *cur = head;
    while (cur != NULL) {
        Node *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

Saving next before overwriting cur->next is the whole trick. If you overwrite first, the rest of the list becomes unreachable.

Sentinel Nodes

A sentinel or dummy node is a permanent node that does not store real data. It simplifies edge cases by ensuring there is always a predecessor before the first real node. Sentinels are especially helpful in doubly linked lists and hash-table chains because they reduce special cases.

Invariants

A function-based list implementation should be written around invariants, not around individual pointer tricks. After every operation, these statements should be true:

• If the list is empty, then head == NULL.
• If the list is non-empty, then head points to the first node.
• The final node always has next == NULL.
• Starting from head and following next eventually reaches NULL.
• No insert function loses the old list.
• No delete function leaves a removed node reachable from the list.
• No delete function frees a node before saving the next pointer it needs.

These invariants explain why insert and delete functions return the updated head. A function that changes the first node must give the caller the new first node. Otherwise the program keeps using an old pointer and the list becomes incorrect.

List Tests

Linked list tests should target boundary cases first because most bugs occur at the front, the back, or the transition between empty and non-empty states.

Useful tests include:

• Start with head = NULL and display the empty list.
• Insert one value at the head.
• Insert one value at the tail on an empty list.
• Insert several values at the tail and verify traversal order.
• Insert a value after an existing value.
• Try to insert after a value that does not exist.
• Remove the first value from a one-node list and confirm the list becomes empty.
• Remove the head from a multi-node list.
• Remove the tail from a multi-node list.
• Try to remove a value that does not exist.
• Free an empty list and a non-empty list.

In C, a memory checker such as Valgrind or AddressSanitizer is especially valuable for this topic. Logical output tests can show whether values appear in the right order, but memory tools catch leaks, double frees, and use-after-free errors that may not show up immediately in normal output.

Memory Cost

Linked lists are flexible but cache-unfriendly. Each node is separately allocated, so traversing a list may jump to unrelated memory addresses. An array scan over one million integers and a linked-list scan over one million integers are both O(n), but the array often runs much faster because consecutive values are loaded together by the CPU cache.

This is why linked lists should not be chosen simply because they have O(1) insertion. That bound assumes you already have the insertion position. If you first search for the position, the full operation is usually O(n).

Pointer Hazards

• Losing the rest of the list by overwriting next too early
• Freeing a node before saving the pointer needed to continue traversal
• Displaying with while (current->next != NULL) and skipping the last node
• Using global current and newNode variables instead of local variables inside functions
• Forgetting to check whether malloc returned NULL
• Forgetting to update tail after deleting the last node
• Treating O(1) insertion as if finding the position were free
• Updating only one direction in a doubly linked list
• Traversing a circular list with while (cur != NULL)

List Costs

List Practice

1. Implement singly linked list traversal, insertion at head, insertion after a node, and deletion after a node.
2. Draw A -> B -> C -> D -> NULL, then trace insertion of X after B line by line.
3. Implement a doubly linked list deletion and verify both next and prev links after every deletion.
4. Reverse a list of five nodes by hand before running your code.

List Metadata

A head-only list keeps the representation small, but some workloads repeatedly need the tail or element count. A wrapper can store both as maintained metadata:

typedef struct {
    Node *head;
    Node *tail;
    size_t size;
} List;

void list_init(List *list) {
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

The stronger representation invariant is:

size == 0 if and only if head == NULL and tail == NULL
size > 0 implies head != NULL and tail != NULL
tail->next == NULL
following next from head reaches exactly size nodes
the final reachable node is tail

Maintaining tail changes append from O(n) to O(1):

int list_push_back(List *list, int data) {
    Node *node = createNode(data);
    if (node == NULL) {
        return 0;
    }

    if (list->tail == NULL) {
        list->head = node;
    } else {
        list->tail->next = node;
    }
    list->tail = node;
    list->size++;
    return 1;
}

int list_pop_front(List *list, int *out) {
    if (list->head == NULL || out == NULL) {
        return 0;
    }

    Node *old_head = list->head;
    *out = old_head->data;
    list->head = old_head->next;
    free(old_head);
    list->size--;

    if (list->head == NULL) {
        list->tail = NULL;
    }
    return 1;
}

The singleton-to-empty transition must clear both pointers. A stale tail may not affect forward display immediately, but the next append can write through freed memory.

Extra metadata is useful only if every operation preserves it. A debug validator can traverse from head, count nodes, record the final node, and compare both results with size and tail.

Ownership Contract

For integer nodes, ownership is straightforward: the list allocates nodes and releases them during deletion or cleanup. For pointer payloads, two independent objects exist:

list node -> payload object

The interface must decide whether the list owns only the node or also owns the payload. If it owns payloads, deletion and cleanup need a destructor callback: a function supplied by the caller that releases one payload. If it stores borrowed payloads, those objects must outlive every list reference to them.

Returning a Node * from search also creates an alias into the representation. An alias is simply another pointer to the same node. That pointer becomes invalid when its node is deleted. Reversal preserves node addresses but changes successor relationships; clients must not assume a saved next link still describes list order after mutation.

Bidirectional Traversal

A doubly linked list commonly stores both ends:

typedef struct {
    DNode *head;
    DNode *tail;
    size_t size;
} DList;

Backward traversal begins at tail and follows prev:

void dlist_print_reverse(const DList *list) {
    const DNode *current = list->tail;
    while (current != NULL) {
        printf("%d ", current->value);
        current = current->prev;
    }
    printf("\n");
}

For every adjacent pair a then b, both directions must agree:

a->next == b
b->prev == a

The boundary conditions are head->prev == NULL and tail->next == NULL. Testing only forward output cannot detect every broken backward link.

With a stored size, indexed lookup can begin at the closer end. This can halve the maximum number of followed links, but the asymptotic cost remains O(n).

Circular Deletion

In a tail-based circular singly linked list, tail->next is the head. Removing the head is constant time:

Node *circular_remove_head(Node *tail, int *out) {
    if (tail == NULL || out == NULL) {
        return tail;
    }

    Node *head = tail->next;
    *out = head->data;

    if (head == tail) {
        free(head);
        return NULL;
    }

    tail->next = head->next;
    free(head);
    return tail;
}

The one-node case is special because the same node is both head and tail. For a larger list, deletion changes only the tail’s link to the new head.

A valid non-empty circular list has no null successor. Starting from tail->next and following exactly size links returns to the same node. Waiting for NULL is therefore never a valid circular traversal condition.

Operation Contracts

Pointer rewiring may be constant time while the complete requested operation is not:

insert after a supplied node pointer: O(1)
find a value, then insert after it:    O(n)
delete a supplied doubly linked node: O(1)
find a value, then delete it:          O(n)

State both the required input and the complete cost. Saying only “linked-list insertion is O(1)” hides the cost of locating an insertion point.

Operations that allocate should leave the old list unchanged when allocation fails. Operations that return removed data should use a status value or output parameter rather than reserving an ordinary data value as an error sentinel.

List Reference

The earlier functions make one pointer change at a time. This complete C17 list uses a wrapper so head, tail, and size form one maintained state. It supports both-end insertion, indexed insertion and deletion, lookup, reversal, cleanup, and a structural validator. Nodes are owned exclusively by the list; a successful deletion copies the integer out before releasing its node, and failed allocation leaves the list unchanged.

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

typedef struct ListNode {
    int value;
    struct ListNode *next;
} ListNode;

typedef struct {
    ListNode *head;
    ListNode *tail;
    size_t size;
} ManagedList;

static void managed_list_init(ManagedList *list) {
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
}

static bool managed_list_valid(const ManagedList *list) {
    if (list == NULL) {
        return false;
    }
    if (list->size == 0) {
        return list->head == NULL && list->tail == NULL;
    }
    if (list->head == NULL || list->tail == NULL ||
        list->tail->next != NULL) {
        return false;
    }

    size_t count = 0;
    const ListNode *last = NULL;
    for (const ListNode *node = list->head;
         node != NULL;
         node = node->next) {
        if (count == list->size) {
            return false;
        }
        last = node;
        count++;
    }
    return count == list->size && last == list->tail;
}

static ListNode *managed_node_create(int value) {
    ListNode *node = malloc(sizeof *node);
    if (node == NULL) {
        return NULL;
    }
    node->value = value;
    node->next = NULL;
    return node;
}

static bool managed_push_front(ManagedList *list, int value) {
    assert(managed_list_valid(list));
    ListNode *node = managed_node_create(value);
    if (node == NULL) {
        return false;
    }

    node->next = list->head;
    list->head = node;
    if (list->tail == NULL) {
        list->tail = node;
    }
    list->size++;
    assert(managed_list_valid(list));
    return true;
}

static bool managed_push_back(ManagedList *list, int value) {
    assert(managed_list_valid(list));
    ListNode *node = managed_node_create(value);
    if (node == NULL) {
        return false;
    }

    if (list->tail == NULL) {
        list->head = node;
    } else {
        list->tail->next = node;
    }
    list->tail = node;
    list->size++;
    assert(managed_list_valid(list));
    return true;
}

static ListNode *managed_node_at(ManagedList *list, size_t index) {
    if (index >= list->size) {
        return NULL;
    }

    ListNode *node = list->head;
    for (size_t i = 0; i < index; i++) {
        node = node->next;
    }
    return node;
}

static bool managed_insert(ManagedList *list, size_t index, int value) {
    assert(managed_list_valid(list));
    if (index > list->size) {
        return false;
    }
    if (index == 0) {
        return managed_push_front(list, value);
    }
    if (index == list->size) {
        return managed_push_back(list, value);
    }

    ListNode *previous = managed_node_at(list, index - 1);
    ListNode *node = managed_node_create(value);
    if (node == NULL) {
        return false;
    }
    node->next = previous->next;
    previous->next = node;
    list->size++;
    assert(managed_list_valid(list));
    return true;
}

static bool managed_erase(ManagedList *list, size_t index,
                          int *removed) {
    assert(managed_list_valid(list));
    if (index >= list->size) {
        return false;
    }

    ListNode *victim;
    if (index == 0) {
        victim = list->head;
        list->head = victim->next;
    } else {
        ListNode *previous = managed_node_at(list, index - 1);
        victim = previous->next;
        previous->next = victim->next;
        if (victim == list->tail) {
            list->tail = previous;
        }
    }

    if (removed != NULL) {
        *removed = victim->value;
    }
    free(victim);
    list->size--;
    if (list->size == 0) {
        list->tail = NULL;
    }
    assert(managed_list_valid(list));
    return true;
}

static const ListNode *managed_find(const ManagedList *list, int target) {
    assert(managed_list_valid(list));
    for (const ListNode *node = list->head;
         node != NULL;
         node = node->next) {
        if (node->value == target) {
            return node;
        }
    }
    return NULL;
}

static void managed_reverse(ManagedList *list) {
    assert(managed_list_valid(list));
    ListNode *previous = NULL;
    ListNode *current = list->head;
    list->tail = list->head;

    while (current != NULL) {
        ListNode *next = current->next;
        current->next = previous;
        previous = current;
        current = next;
    }
    list->head = previous;
    assert(managed_list_valid(list));
}

static void managed_clear(ManagedList *list) {
    ListNode *current = list->head;
    while (current != NULL) {
        ListNode *next = current->next;
        free(current);
        current = next;
    }
    managed_list_init(list);
}

static void managed_print(const ManagedList *list) {
    if (list->head == NULL) {
        printf("empty\n");
        return;
    }
    for (const ListNode *node = list->head;
         node != NULL;
         node = node->next) {
        printf("%d%s", node->value,
               node->next == NULL ? "\n" : " -> ");
    }
}

int main(void) {
    ManagedList list;
    managed_list_init(&list);

    if (!managed_push_back(&list, 12) ||
        !managed_push_back(&list, 27) ||
        !managed_push_back(&list, 8) ||
        !managed_insert(&list, 1, 19)) {
        managed_clear(&list);
        return EXIT_FAILURE;
    }

    managed_print(&list);
    managed_reverse(&list);
    managed_print(&list);

    int removed;
    if (!managed_erase(&list, 2, &removed)) {
        managed_clear(&list);
        return EXIT_FAILURE;
    }
    printf("removed %d, found 27: %s, size %zu\n",
           removed,
           managed_find(&list, 27) != NULL ? "yes" : "no",
           list.size);

    managed_clear(&list);
    return EXIT_SUCCESS;
}

managed_list_valid deliberately walks the structure. Besides comparing reachable nodes with size and tail, it rejects any additional node after the declared count, so an accidental reachable cycle cannot make validation loop forever. That cost is appropriate for assertions and tests; normal list mutations still change only the links required by their stated operation.

List Splicing

A linked list can transfer a chain of existing nodes without copying their values. This is called splicing. If source should move to the end of destination, the conceptual cases are:

source empty:
    no change

destination empty:
    destination takes source head, tail, and size

both non-empty:
    destination.tail->next = source.head
    destination.tail = source.tail
    destination.size += source.size

after every successful case:
    source becomes {head=NULL, tail=NULL, size=0}

Because both wrappers already know their ends and sizes, whole-list splicing is O(1). The source must be reset; leaving its old head would give two list objects ownership of the same nodes and cause later double destruction.

The API should reject destination == source. Self-splicing is not ordinary concatenation: assigning the tail’s successor to the same head creates a cycle, then clearing the source clears the destination because both names refer to one wrapper.

Moving an interior range is more subtle. In a doubly linked list, known boundary nodes let the implementation unlink and relink the range with constant pointer changes. If the wrapper stores size, it must also know how many nodes moved. Counting the range makes the complete operation linear even though rewiring is constant. A range object can carry a verified count when constant-time metadata updates are required.

Splicing demonstrates why complexity should describe the public request. “Four pointer assignments” does not include searching for boundaries, validating that they belong to the claimed lists, or counting moved nodes.

Node Stability

Ordinary insertion and reversal do not relocate existing separately allocated nodes. A pointer to an untouched node keeps the same address. Its structural meaning can still change:

before reversal: saved->next is the node after saved
after reversal:  saved->next is the former predecessor

Deletion invalidates the removed node pointer immediately. Clearing invalidates every node pointer. Splicing preserves addresses but transfers ownership to another list. These facts form an iterator contract:

• reading values does not invalidate an iterator;
• inserting elsewhere preserves the saved node but may change sequence context;
• deleting the saved node invalidates it;
• reversal preserves the address but changes future traversal order;
• destruction invalidates all iterators.

A modification counter can implement fail-fast iteration. The list increments version on structural mutation; an iterator stores the version it observed. Before following next, it reports invalidation if the versions differ. This is safer than guessing whether a saved link survived a mutation, although it deliberately rejects some mutations that might have been harmless.

Never expose a Node * as permanent identity unless this invalidation policy is intentional. An opaque handle can include a generation count, or the interface can expose values and positions while keeping nodes private.

Cycle Diagnosis

A linear singly linked list must terminate at null. A corrupted link may instead create:

A -> B -> C -> D
         ^    |
         |____|

An unrestricted traversal, display, or cleanup then loops forever. A size-aware validator can stop after size links, as the reference implementation does. Without reliable size metadata, Floyd’s two-cursor test detects a cycle using constant extra space:

static bool list_has_cycle(const ListNode *head) {
    const ListNode *slow = head;
    const ListNode *fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

slow advances one edge while fast advances two. Inside a finite cycle, the faster cursor eventually catches the slower one. No meeting proves a valid list by itself—nodes could still be dangling or metadata could be wrong—but a meeting proves the null-terminated invariant is broken.

Do not run ordinary recursive or iterative cleanup on a detected cycle. First diagnose or break the repeated link under controlled ownership; otherwise nodes may be freed twice or traversal may dereference an already freed node.

Allocation Strategy

One malloc per node makes local insertion convenient, but allocation overhead may exceed the payload size for a node holding one integer and one pointer. A node pool allocates blocks and maintains a free-node chain:

allocate node: pop from pool free chain
release node:  push onto pool free chain
destroy pool:  release whole backing blocks

Pools can improve locality and make repeated insert/delete workloads predictable. They also change ownership: a released node returns to the pool rather than to the system, and destroying a pool invalidates every list node allocated from it. Mixing nodes from different pools complicates splicing unless the destination retains all contributing pools.

An intrusive list places link fields inside the client’s record. It avoids a separate node allocation and can link one object into several lists using separate link fields. The list then usually does not own the record. Removing it only rewires links; the client decides when the record itself can be destroyed.

The simplest list should remain the default for small programs. Pools and intrusive links are useful when measurements show allocator cost or when record identity already exists outside the container.

Sequence Oracles

A dynamic array is a convenient reference model for randomized list testing. Apply the same push, insert, erase, reverse, and splice operations to both representations, then compare size and every value in order. The array’s slower middle updates are acceptable in a test.

After each list mutation, verify head/tail emptiness, the exact reachable count, the final node, absence of cycles, and—for doubly linked lists—both directions of every adjacent pair. Test allocation failure at every node-creation point during cloning or bulk construction and confirm that the original lists and ownership remain unchanged.

Value output alone is insufficient. A list may print correctly forward while one prev link is wrong, while tail dangles, or while an unreachable node leaks. Structural checks and sanitizers cover those independent failure modes.

Choosing Lists

Pointer rewiring is only part of an operation’s cost. Insertion after a supplied node is constant time, while searching for that node and then inserting remains linear. Independently allocated nodes also carry allocator metadata and usually have weaker cache locality than a contiguous array.

List Challenges

Tail Limits

1. Explain why a tail pointer alone does not make pop_back constant time in a singly linked list.

Link Transitions

2. Draw the pointer and metadata changes for appending to an empty list, deleting its only node, and removing the tail of a three-node doubly linked list.

List Operations

3. Implement list_push_front, list_push_back, list_pop_front, and list_pop_back for the metadata wrapper, preserving its invariant after every call.
4. Write a validator for a doubly linked list that checks size, both boundaries, and every reciprocal link.
5. Complete insertion and deletion for a circular tail-based list and test empty, singleton, head, tail, and middle cases.

Payload Ownership

6. Define ownership rules for a list of dynamically allocated strings, then implement cleanup without leaks or double frees.
7. Design an iterator and document which operations invalidate its saved node pointer.

Constant Splicing

8. Splice a complete source list onto the end of a destination list in constant time. Handle empty inputs and leave the source as a valid empty list.

Iterators and Ranges

9. Design an iterator and state exactly which insertions, deletions, reversals, and destruction invalidate its saved node.
10. Clone a list with a strong failure guarantee: allocation failure must leave the source unchanged and release every node of the partial copy.
11. Splice a half-open range [first, after_last) between two doubly linked lists using constant pointer-update work.
12. Build an intrusive list whose client records contain their own link fields, then explain how that changes allocation and ownership.