Linked Lists in C

Singly Linked List

A singly linked list is a chain of nodes where each node holds data and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory — each node can be anywhere on the heap. This makes O(1) insertion at the head trivial and eliminates the need to shift elements on insertion or deletion, but it sacrifices random access and cache locality.

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

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

/* Create a new node on the heap */
Node *node_create(int data) {
    Node *n = malloc(sizeof(Node));
    if (!n) { perror("malloc"); exit(1); }
    n->data = data;
    n->next = NULL;
    return n;
}

/* Insert at the front — O(1): just update the head pointer */
Node *list_prepend(Node *head, int data) {
    Node *n = node_create(data);
    n->next = head;
    return n;   /* new head */
}

/* Insert at the end — O(n): must walk to the last node */
Node *list_append(Node *head, int data) {
    Node *n = node_create(data);
    if (!head) return n;

    Node *curr = head;
    while (curr->next) curr = curr->next;
    curr->next = n;
    return head;
}

/* Insert in sorted order — O(n): walk to find the right position */
Node *list_insert_sorted(Node *head, int data) {
    Node *n = node_create(data);

    /* Insert before head if list is empty or data belongs first */
    if (!head || data <= head->data) {
        n->next = head;
        return n;
    }

    Node *curr = head;
    while (curr->next && curr->next->data < data) {
        curr = curr->next;
    }
    n->next    = curr->next;
    curr->next = n;
    return head;
}

/* Delete first node with given value — O(n) */
Node *list_delete(Node *head, int data) {
    if (!head) return NULL;

    /* Special case: deleting the head node */
    if (head->data == data) {
        Node *new_head = head->next;
        free(head);
        return new_head;
    }

    /* Walk to find the node just before the target */
    Node *curr = head;
    while (curr->next && curr->next->data != data) {
        curr = curr->next;
    }

    if (curr->next) {   /* found it */
        Node *to_delete = curr->next;
        curr->next = to_delete->next;
        free(to_delete);
    }
    return head;
}

/* Search — O(n) */
Node *list_find(Node *head, int data) {
    while (head) {
        if (head->data == data) return head;
        head = head->next;
    }
    return NULL;
}

/* Reverse in-place — O(n): classic three-pointer technique */
Node *list_reverse(Node *head) {
    Node *prev = NULL;
    Node *curr = head;
    while (curr) {
        Node *next = curr->next;  /* save next before overwriting */
        curr->next = prev;        /* reverse the link */
        prev = curr;
        curr = next;
    }
    return prev;   /* prev is the new head */
}

/* Free every node — save next before freeing current */
void list_free(Node *head) {
    while (head) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

void list_print(const Node *head) {
    while (head) {
        printf("%d", head->data);
        if (head->next) printf(" -> ");
        head = head->next;
    }
    printf(" -> NULL\n");
}

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

    /* Build: 1 -> 2 -> 3 -> 4 -> 5 */
    for (int i = 1; i <= 5; i++) {
        list = list_append(list, i);
    }
    list_print(list);   /* 1 -> 2 -> 3 -> 4 -> 5 -> NULL */

    list = list_prepend(list, 0);
    list_print(list);   /* 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL */

    list = list_delete(list, 3);
    list_print(list);   /* 0 -> 1 -> 2 -> 4 -> 5 -> NULL */

    list = list_reverse(list);
    list_print(list);   /* 5 -> 4 -> 2 -> 1 -> 0 -> NULL */

    Node *found = list_find(list, 4);
    printf("Found: %d\n", found ? found->data : -1);

    list_free(list);
    return 0;
}

Doubly Linked List

A doubly linked list adds a prev pointer to each node, enabling O(1) backward traversal and O(1) deletion of any node given a direct pointer to it (no need to find the previous node first). The trade-off is slightly more memory per node and more pointer bookkeeping during insertions and deletions.

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

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

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

void dlist_init(DList *l) {
    l->head = l->tail = NULL;
    l->size = 0;
}

DNode *dnode_create(int data) {
    DNode *n = malloc(sizeof(DNode));
    if (!n) { perror("malloc"); exit(1); }
    n->data = data;
    n->prev = n->next = NULL;
    return n;
}

/* Push to front — O(1) */
void dlist_push_front(DList *l, int data) {
    DNode *n = dnode_create(data);
    if (!l->head) {
        l->head = l->tail = n;
    } else {
        n->next = l->head;
        l->head->prev = n;
        l->head = n;
    }
    l->size++;
}

/* Push to back — O(1) because we keep a tail pointer */
void dlist_push_back(DList *l, int data) {
    DNode *n = dnode_create(data);
    if (!l->tail) {
        l->head = l->tail = n;
    } else {
        n->prev = l->tail;
        l->tail->next = n;
        l->tail = n;
    }
    l->size++;
}

/* Remove a specific node — O(1) given the node pointer */
void dlist_remove(DList *l, DNode *n) {
    if (n->prev) n->prev->next = n->next;
    else         l->head = n->next;   /* n was the head */

    if (n->next) n->next->prev = n->prev;
    else         l->tail = n->prev;   /* n was the tail */

    free(n);
    l->size--;
}

/* Pop from front */
int dlist_pop_front(DList *l) {
    if (!l->head) return -1;
    int val = l->head->data;
    dlist_remove(l, l->head);
    return val;
}

/* Pop from back */
int dlist_pop_back(DList *l) {
    if (!l->tail) return -1;
    int val = l->tail->data;
    dlist_remove(l, l->tail);
    return val;
}

void dlist_print(const DList *l) {
    printf("NULL <-> ");
    for (DNode *n = l->head; n; n = n->next) {
        printf("%d <-> ", n->data);
    }
    printf("NULL  (size=%zu)\n", l->size);
}

void dlist_free(DList *l) {
    DNode *curr = l->head;
    while (curr) {
        DNode *next = curr->next;
        free(curr);
        curr = next;
    }
    l->head = l->tail = NULL;
    l->size = 0;
}

int main(void) {
    DList list;
    dlist_init(&list);

    dlist_push_back(&list, 1);
    dlist_push_back(&list, 2);
    dlist_push_back(&list, 3);
    dlist_push_front(&list, 0);
    dlist_print(&list);   /* NULL <-> 0 <-> 1 <-> 2 <-> 3 <-> NULL */

    printf("Pop front: %d\n", dlist_pop_front(&list));  /* 0 */
    printf("Pop back:  %d\n", dlist_pop_back(&list));   /* 3 */
    dlist_print(&list);   /* NULL <-> 1 <-> 2 <-> NULL */

    /* Remove middle node in O(1) — no need to find the previous node */
    DNode *middle = list.head->next;
    dlist_remove(&list, middle);
    dlist_print(&list);   /* NULL <-> 1 <-> NULL */

    dlist_free(&list);
    return 0;
}

Circular Linked List

In a circular linked list the last node’s next pointer points back to the first node instead of NULL. This enables continuous traversal — useful for round-robin scheduling, game turn order, and the Josephus problem.

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

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

/* Insert at end; tail->next always points to head */
CNode *circular_insert(CNode *tail, int data) {
    CNode *n = malloc(sizeof(CNode));
    n->data = data;
    if (!tail) {
        n->next = n;   /* single node points to itself */
        return n;
    }
    n->next    = tail->next;   /* n points to head */
    tail->next = n;            /* old tail points to n */
    return n;                  /* n is the new tail */
}

void circular_print(CNode *tail, int count) {
    if (!tail) return;
    CNode *curr = tail->next;   /* start at head */
    for (int i = 0; i < count; i++) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("...\n");
}

/* Josephus problem: n people in a circle, eliminate every k-th person */
int josephus(int n, int k) {
    CNode *tail = NULL;
    for (int i = 1; i <= n; i++) {
        tail = circular_insert(tail, i);
    }

    CNode *curr = tail->next;   /* start at head (person 1) */
    CNode *prev = tail;

    while (curr->next != curr) {   /* more than one person remains */
        /* Advance k-1 steps */
        for (int i = 1; i < k; i++) {
            prev = curr;
            curr = curr->next;
        }
        printf("Eliminated: %d\n", curr->data);
        prev->next = curr->next;
        free(curr);
        curr = prev->next;
    }

    int survivor = curr->data;
    free(curr);
    return survivor;
}

int main(void) {
    printf("Josephus survivor (n=7, k=3): %d\n", josephus(7, 3));  /* 4 */
    return 0;
}