Linked Lists

Singly, doubly, and circular linked lists; function-based C implementation, traversal, insertion, deletion, reversal, and pointer safety.

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.

More advanced implementations may also store tail and size, but beginners should first understand the head-pointer version. Once that is clear, adding a tail pointer is only an optimization.

Head Return

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

Pass the address of head.
Return the updated head.

For beginners, returning the updated head is usually easier to read:

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.

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.

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.

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 is the intended level of modularity for beginners: each operation has its own function, but the learner can still see how the head pointer changes.

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

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;
}

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.

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.

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).

Pitfalls

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)

Costs

Operation	Singly linked	Doubly linked
Access by index	`O(n)`	`O(n)`
Search by value	`O(n)`	`O(n)`
Insert at head	`O(1)`	`O(1)`
Insert after known node	`O(1)`	`O(1)`
Delete after predecessor	`O(1)`	`O(1)`
Delete known node directly	Needs predecessor	`O(1)`
Extra pointer storage	One pointer	Two pointers

Exercises

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