Linked List in C: Complete Guide with Operations and Examples

Arrays are where every C programmer starts — and linked lists are where C programmers are made. Building one forces you to use everything that makes C powerful and dangerous at once: structs, pointers, dynamic memory, and the discipline to free what you allocate.

This guide builds a complete singly linked list in C from a single struct to a full working program: insertion at the front, end, and middle, deletion, search, reversal, and the classic interview problem of finding the middle element in one pass. Along the way you will see the time complexity of every operation, how doubly and circular linked lists differ, and where linked lists actually get used. The complete program near the end of this guide — the one every snippet here is taken from — compiles clean with gcc -std=c11 -Wall -Wextra and runs leak-free under AddressSanitizer.

Table of Contents

• What Is a Linked List in C?
• Defining a Node in C
• Inserting Nodes: Front, End and Middle
• Traversing, Searching and Counting
• Deleting a Node
• Reversing a Linked List
• Finding the Middle Element in One Pass
• The Complete Program
• Time Complexity of Linked List Operations
• Singly vs Doubly vs Circular Linked Lists
• Where Linked Lists Are Actually Used
• Key Takeaways
• Frequently Asked Questions
• Conclusion

What Is a Linked List in C?

A linked list is a linear data structure in which each element (a node) contains the data itself plus a pointer to the next node. Unlike an array, the nodes are not stored side by side in memory — each one is allocated separately on the heap, and the chain of pointers, starting from a head pointer, is what holds the list together.

That one structural difference drives every trade-off between the two:

The short version: linked lists win when you insert and remove a lot at known positions and don’t need random access; arrays win nearly everywhere else, especially on modern hardware where the cache-friendliness row matters more than the big-O rows suggest. Knowing when each wins is half of what data-structure interviews test — the other half is whether you can build one, so let’s build one.

Defining a Node in C

A node is a struct that contains its data and a pointer to another struct of the same type — a self-referential structure:

/* A node: the data plus a pointer to the next node */
struct Node {
    int data;
    struct Node *next;
};

An empty list is simply a head pointer that equals NULL. Every node lives on the heap, so creation means malloc — and in C, every malloc deserves a check:

/* Create a node on the heap -- always check malloc */
struct Node *createNode(int value)
{
    struct Node *node = malloc(sizeof(struct Node));
    if (node == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(EXIT_FAILURE);
    }
    node->data = value;
    node->next = NULL;
    return node;
}

If pointers and -> still feel shaky, this topic is the best pointer workout there is — and our data structures section has more of them once this one clicks.

Inserting Nodes: Front, End and Middle

At the front — O(1). The new node points to the old first node, and the head moves. Note the struct Node **head parameter: the function must modify the caller’s head pointer, so it receives the address of that pointer:

/* Insert at the beginning: O(1) */
void insertFront(struct Node **head, int value)
{
    struct Node *node = createNode(value);
    node->next = *head;   /* new node points to old first node */
    *head = node;         /* head now points to the new node   */
}

At the end — O(n). There is no shortcut to the last node in a singly linked list; you walk there:

/* Insert at the end: O(n) -- must walk to the last node */
void insertEnd(struct Node **head, int value)
{
    struct Node *node = createNode(value);
    if (*head == NULL) {          /* empty list: new node IS the head */
        *head = node;
        return;
    }
    struct Node *cur = *head;
    while (cur->next != NULL)     /* walk to the last node */
        cur = cur->next;
    cur->next = node;
}

After a position. The one rule that prevents lost nodes: link the new node into the chain before breaking the old link — node->next = cur->next; must come first:

/* Insert after position pos (0-based). pos 0 = after first node */
void insertAfter(struct Node *head, int pos, int value)
{
    struct Node *cur = head;
    for (int i = 0; cur != NULL && i < pos; i++)
        cur = cur->next;
    if (cur == NULL) return;      /* position past the end: ignore */

    struct Node *node = createNode(value);
    node->next = cur->next;       /* order matters: link new node first */
    cur->next = node;
}

Traversing, Searching and Counting

Traversal is the pattern underneath everything else — start at the head, follow next until NULL:

/* Search: returns the 0-based position, or -1 if absent */
int search(const struct Node *head, int value)
{
    int pos = 0;
    for (const struct Node *cur = head; cur != NULL; cur = cur->next) {
        if (cur->data == value) return pos;
        pos++;
    }
    return -1;
}

length() and printList() in the complete program below are the same loop with different bodies. Note the const on the parameter: these functions only read the list, and saying so lets the compiler enforce it.

Deleting a Node

Deletion is the operation that separates programmers who understand linked lists from those who memorized them, because it needs two pointers — the node to remove and the node before it — and it must free() the removed node:

/* Delete the first node holding value: O(n) */
void deleteValue(struct Node **head, int value)
{
    struct Node *cur = *head;
    struct Node *prev = NULL;

    while (cur != NULL && cur->data != value) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return;      /* not found */

    if (prev == NULL)
        *head = cur->next;        /* deleting the head node */
    else
        prev->next = cur->next;   /* bypass the node */
    free(cur);                    /* release its memory */
}

The forgotten free(cur) is the most common linked-list bug in student code — the node is unlinked, unreachable, and leaked.

Reversing a Linked List

The most-asked linked list interview question, and a beautiful three-pointer dance — prev, cur, and next walk the list flipping one arrow per step:

/* Reverse the list in place: O(n) time, O(1) space */
void reverse(struct Node **head)
{
    struct Node *prev = NULL;
    struct Node *cur = *head;

    while (cur != NULL) {
        struct Node *next = cur->next;  /* remember the rest  */
        cur->next = prev;               /* flip this pointer  */
        prev = cur;                     /* advance prev       */
        cur = next;                     /* advance cur        */
    }
    *head = prev;                       /* prev is the new head */
}

Why remember next first? Because the moment cur->next = prev executes, the rest of the list would otherwise be unreachable. That single line of foresight is the whole algorithm.

Finding the Middle Element in One Pass

The obvious approach takes two passes: count the nodes, then walk to position n/2. The interview-grade answer does it in one pass with two pointers — a slow pointer moving one node per step and a fast pointer moving two. When the fast pointer runs off the end, the slow pointer is standing on the middle:

/* Middle element in ONE pass: slow moves 1 step, fast moves 2 */
int findMiddle(const struct Node *head)
{
    const struct Node *slow = head;
    const struct Node *fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow->data;    /* caller must ensure the list is not empty */
}

For 10 -> 20 -> 30 -> 40 -> 50 the answer is 30; for an even-length list this version lands on the second of the two middle nodes. The same slow/fast technique (Floyd’s “tortoise and hare”) also detects cycles and finds the k-th node from the end — it comes up constantly in programming interviews, which is why it earned its own section here.

The Complete Program

Everything above, assembled and runnable — including the freeList() that releases every node at the end:

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

/* A node: the data plus a pointer to the next node */
struct Node {
    int data;
    struct Node *next;
};

/* Create a node on the heap -- always check malloc */
struct Node *createNode(int value)
{
    struct Node *node = malloc(sizeof(struct Node));
    if (node == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(EXIT_FAILURE);
    }
    node->data = value;
    node->next = NULL;
    return node;
}

/* Insert at the beginning: O(1) */
void insertFront(struct Node **head, int value)
{
    struct Node *node = createNode(value);
    node->next = *head;
    *head = node;
}

/* Insert at the end: O(n) -- must walk to the last node */
void insertEnd(struct Node **head, int value)
{
    struct Node *node = createNode(value);
    if (*head == NULL) {
        *head = node;
        return;
    }
    struct Node *cur = *head;
    while (cur->next != NULL)
        cur = cur->next;
    cur->next = node;
}

/* Insert after position pos (0-based). pos 0 = after first node */
void insertAfter(struct Node *head, int pos, int value)
{
    struct Node *cur = head;
    for (int i = 0; cur != NULL && i < pos; i++)
        cur = cur->next;
    if (cur == NULL) return;

    struct Node *node = createNode(value);
    node->next = cur->next;
    cur->next = node;
}

/* Delete the first node holding value: O(n) */
void deleteValue(struct Node **head, int value)
{
    struct Node *cur = *head;
    struct Node *prev = NULL;

    while (cur != NULL && cur->data != value) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return;

    if (prev == NULL)
        *head = cur->next;
    else
        prev->next = cur->next;
    free(cur);
}

/* Search: returns the 0-based position, or -1 if absent */
int search(const struct Node *head, int value)
{
    int pos = 0;
    for (const struct Node *cur = head; cur != NULL; cur = cur->next) {
        if (cur->data == value) return pos;
        pos++;
    }
    return -1;
}

/* Length: count the nodes */
int length(const struct Node *head)
{
    int n = 0;
    for (const struct Node *cur = head; cur != NULL; cur = cur->next)
        n++;
    return n;
}

/* Reverse the list in place: O(n) time, O(1) space */
void reverse(struct Node **head)
{
    struct Node *prev = NULL;
    struct Node *cur = *head;

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

/* Middle element in ONE pass: slow moves 1 step, fast moves 2 */
int findMiddle(const struct Node *head)
{
    const struct Node *slow = head;
    const struct Node *fast = head;

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

/* Print the whole list */
void printList(const struct Node *head)
{
    for (const struct Node *cur = head; cur != NULL; cur = cur->next)
        printf("%d -> ", cur->data);
    printf("NULL\n");
}

/* Free every node -- do this once, when done with the list */
void freeList(struct Node **head)
{
    struct Node *cur = *head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        free(cur);
        cur = next;
    }
    *head = NULL;
}

int main(void)
{
    struct Node *head = NULL;     /* an empty list is a NULL head */

    insertEnd(&head, 20);
    insertEnd(&head, 30);
    insertFront(&head, 10);       /* 10 -> 20 -> 30 */
    insertEnd(&head, 50);
    insertAfter(head, 2, 40);     /* insert 40 after position 2 */
    printList(head);              /* 10 -> 20 -> 30 -> 40 -> 50 */

    printf("Length: %d\n", length(head));
    printf("Position of 30: %d\n", search(head, 30));
    printf("Middle element: %d\n", findMiddle(head));

    deleteValue(&head, 20);
    printf("After deleting 20:  ");
    printList(head);

    reverse(&head);
    printf("After reversing:    ");
    printList(head);

    freeList(&head);
    return 0;
}

Output:

10 -> 20 -> 30 -> 40 -> 50 -> NULL
Length: 5
Position of 30: 2
Middle element: 30
After deleting 20:  10 -> 30 -> 40 -> 50 -> NULL
After reversing:    50 -> 40 -> 30 -> 10 -> NULL

Compile with gcc -std=c11 -Wall -Wextra linkedlist.c -o linkedlist. This exact program was additionally built with -fsanitize=address and reports zero leaks — every malloc has its free.

Time Complexity of Linked List Operations

*For a dynamic array that occasionally reallocates. A practical upgrade for real code: keep a tail pointer alongside head and insertEnd becomes O(1) too.

Singly vs Doubly vs Circular Linked Lists

A doubly linked node just adds one pointer — and buys O(1) deletion of a node you already hold, plus backward traversal, at the price of extra memory and more pointers to keep consistent:

/* Doubly linked node: pointers in BOTH directions */
struct DNode {
    int data;
    struct DNode *prev;
    struct DNode *next;
};

Wiring 1 <-> 2 <-> 3 and walking it both ways prints (from the compiled demo):

Forward:  1 2 3
Backward: 3 2 1

A circular linked list is a singly or doubly linked list whose last node points back to the first instead of to NULL. The traversal loop changes accordingly — you stop when you return to the starting node, not when you hit NULL — which is exactly the property that makes it natural for anything that cycles: round-robin schedulers, multiplayer turn order, ring buffers.

Where Linked Lists Are Actually Used

Beyond interviews, the pattern appears anywhere insertion and removal dominate:

• Stacks and queues are one-operation-restricted linked lists — a stack is insertFront + delete-front (see our stack implementation in C++), and a queue is insert-tail + delete-head.
• Memory allocators — malloc implementations classically track free blocks in linked lists (the “free list”).
• Operating system kernels — the Linux kernel’s list_head doubly linked list is one of the most-used data structures in its millions of lines.
• LRU caches — a doubly linked list plus a hash table is the textbook O(1) cache design.
• Adjacency lists — the standard representation of sparse graphs.
• Undo history and playlists — anything with a natural previous/next.

For a runnable warm-up before the full implementation above, our short linked list demo program shows the minimal version, and the algorithms section covers what to do with these structures once you can build them.

Key Takeaways

• A linked list is a chain of heap-allocated nodes — data plus a next pointer — reachable only through the head pointer; head == NULL means empty.
• Front operations are O(1), everything positional is O(n) — the exact mirror of an array’s strengths; arrays also win on cache behavior, which big-O tables hide.
• Functions that change the list’s first node take struct Node **head — they must modify the caller’s pointer, not a copy.
• When inserting mid-list, link the new node before breaking the old link; when deleting, free() the removed node — the two rules behind most linked-list bugs.
• The slow/fast two-pointer technique finds the middle in one pass and generalizes to cycle detection — an interview staple worth internalizing.
• Doubly linked lists buy backward traversal and O(1) known-node deletion for one extra pointer; circular lists suit anything that naturally wraps around.

Frequently Asked Questions

Conclusion

If arrays teach you what memory is, linked lists teach you what pointers are for. Every operation in this guide — repointing a head, bridging over a deleted node, flipping arrows in a reversal — is really an exercise in reasoning about which pointer must change, in what order, without losing the rest of the chain. That reasoning, more than the data structure itself, is what interviews are probing and what real C codebases demand.

The natural next steps branch in two directions: build a stack and a queue on top of the list you now have, or add a tail pointer and make insertEnd O(1) — both are hour-sized projects that cement the ideas. When you are ready for the structures that fix the linked list’s O(n) search, trees and hash tables are waiting in our data structures section.