Skip to content
Tutorials Center
My learning

Topics

Lesson 84 of 135 ยท Data Structures in C

Linked Lists

Build a singly linked list in C step by step - nodes, insertion at both ends, search, deletion with pointer-to-pointer, reversal and freeing - plus doubly linked lists.

An array stores its elements side by side in one block of memory. That makes indexing instant, but inserting in the middle means shifting everything after it, and growing means reallocating the whole block. A linked list takes the opposite approach: every element lives in its own small allocation, called a node, and each node holds a pointer to the next one. Inserting or removing an element only rewires a couple of pointers, no matter how long the list is.

C has no built-in list type, so you build one from the tools you already know: structures, pointers to structures and malloc and free. Writing a linked list is a rite of passage for C programmers because it exercises all three at once. In this lesson you'll build a complete singly linked list of integers (insert, search, delete, reverse, free) and then look at the doubly linked variant.

The node

A node holds one value and a pointer to the following node. The struct refers to itself, which is allowed because a pointer to an incomplete type is fine:

C
struct node {
    int value;
    struct node *next;   /* NULL in the last node */
};

The list itself is just a pointer to the first node, usually called the head. An empty list is a head equal to NULL. There's no length stored anywhere unless you add one; you find the end by following next until you hit NULL.

TEXT
head
 โ”‚
 โ–ผ
โ”Œโ”€โ”€โ”€โ”€โ”ฌโ”€โ”€โ”€โ”   โ”Œโ”€โ”€โ”€โ”€โ”ฌโ”€โ”€โ”€โ”   โ”Œโ”€โ”€โ”€โ”€โ”ฌโ”€โ”€โ”€โ”€โ”€โ”€โ”
โ”‚ 10 โ”‚ โ—โ”€โ”ผโ”€โ”€โ–บโ”‚ 20 โ”‚ โ—โ”€โ”ผโ”€โ”€โ–บโ”‚ 30 โ”‚ NULL โ”‚
โ””โ”€โ”€โ”€โ”€โ”ดโ”€โ”€โ”€โ”˜   โ””โ”€โ”€โ”€โ”€โ”ดโ”€โ”€โ”€โ”˜   โ””โ”€โ”€โ”€โ”€โ”ดโ”€โ”€โ”€โ”€โ”€โ”€โ”˜

Here is that picture as code. Three nodes are allocated, linked, printed by walking the chain, and freed again:

C Three nodes linked by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The traversal loop for (p = head; p != NULL; p = p->next) is the heartbeat of every list algorithm; you'll write it again and again. The freeing loop shows the first classic trap: once free(p) runs, reading p->next is a use-after-free (see Memory Errors). Always copy the next pointer out first.

Inserting at the front and the back

Pushing to the front is the cheapest operation: make a node whose next is the old head, then make it the new head. Because the function must change the caller's head variable, it takes a pointer to the head (a struct node **), exactly like any out-parameter in Pointers to Pointers.

C
void push_front(struct node **head, int value)
{
    struct node *n = new_node(value, *head);
    *head = n;
}

Appending to the back needs to find the last node first, which takes time proportional to the length, written O(n). The neat trick is to walk a struct node ** that points at the link you might change: first the head pointer itself, then each node's next field. When it points at a NULL link, that's where the new node goes, and there's no special case for an empty list:

C
void push_back(struct node **head, int value)
{
    struct node **link = head;
    while (*link != NULL) {
        link = &(*link)->next;     /* move to the next link */
    }
    *link = new_node(value, NULL);
}

If you append often, keep a separate tail pointer too, so appending becomes O(1). Queues in the next lesson do exactly that.

Searching and deleting

Searching is the traversal loop with an early exit. It returns a pointer to the node, or NULL if the value isn't there.

Deleting is where the pointer-to-pointer technique really shines. To unlink a node, you have to change whatever points to it: the head pointer for the first node, or the previous node's next for any other. Walking a struct node **link gives you that "whatever" directly, so one short loop handles every position:

C
bool remove_value(struct node **head, int value)
{
    for (struct node **link = head; *link != NULL; link = &(*link)->next) {
        if ((*link)->value == value) {
            struct node *doomed = *link;
            *link = doomed->next;      /* bypass the node */
            free(doomed);
            return true;
        }
    }
    return false;
}

The textbook alternative keeps a prev pointer and checks "is this the head?" separately. Both work; the double-pointer version has fewer branches, so it has fewer places to hide bugs.

Here is the full API in one program. Run it, then change the values in main:

C A complete singly linked list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The program prints:

TEXT
built:        [10, 20, 30, 40] (length 4)
find 30: found
find 99: missing
after remove: [20] (length 1)
remove 99: not found
after free:   [] (length 0)

Notice that remove_value handled the first, a middle and the last node with the same code, and that free_list takes struct node ** so it can reset the caller's pointer to NULL. Afterwards list is a valid empty list instead of a dangling pointer.

Tip: Mark functions that don't modify the list with const struct node * (like length and print_list). It documents intent and lets the compiler catch accidental writes. See const and Pointers.

Reversing a list and inserting in order

Reversing a singly linked list in place is a favorite interview question, and the answer is short. Walk the list once with three pointers: prev (the already reversed part), current, and next (saved so you don't lose the rest). Each step flips one arrow:

TEXT
prev      current    next
NULL      10 โ”€โ”€โ–บ     20 โ”€โ”€โ–บ 30 โ”€โ”€โ–บ NULL
          after one step:
NULL โ—„โ”€โ”€ 10          20 โ”€โ”€โ–บ 30 โ”€โ”€โ–บ NULL
         prev        current

Sorted insertion uses the double-pointer walk again: advance while the next value is smaller, then splice the new node in. Feeding unsorted numbers through it is a simple way to keep a list sorted at all times (it's insertion sort, which you'll meet in Sorting and Searching Algorithms). This example reads numbers from the Input box:

C Sorted insert and in-place reverse

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

It prints sorted: 3 7 19 19 42 56 88 and reversed: 88 56 42 19 19 7 3. Duplicates are kept (the loop uses <, so a new 19 goes after the existing 19, which makes the insert stable). Reversing returns the new head instead of taking struct node **; both designs are common, but with a return value you must remember to assign it: list = reverse(list);.

Doubly linked lists

A doubly linked list gives each node a prev pointer as well as next. That costs one extra pointer per node, and every insertion and deletion must update twice as many links, but it buys two things:

  • You can walk the list backwards.
  • Given a pointer to a node, you can unlink it in O(1) without searching for its predecessor.

Production code (the Linux kernel's list_head, many allocators and LRU caches) usually adds a sentinel node: a dummy node that is never removed, with the list arranged in a circle around it. An empty list is a sentinel pointing at itself, and insert/remove need no NULL checks at all:

C A circular doubly linked list with a sentinel

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The three lines of output are forward: 1 2 3 4 | backward: 4 3 2 1, then the same without the 2, and finally an empty list in both directions. link_between and unlink_node are the only places that touch pointers, which is why this design is so robust.

Linked lists versus arrays

Linked lists are elegant, but on modern hardware they're often slower than you'd expect. Each node is a separate allocation, possibly far from its neighbors in memory, so walking a list causes many cache misses, while an array is read in one smooth stream. Compare:

Operation Array / dynamic array Singly linked list
Access element i O(1) O(n), walk from the head
Insert/remove at front O(n), shift everything O(1)
Insert/remove after a known node O(n) O(1)
Append at the end O(1) amortized (dynamic array) O(n), or O(1) with a tail pointer
Search for a value O(n), cache-friendly O(n), cache-unfriendly
Memory per element just the value value + pointer + allocator overhead

Reach for a linked list when you need stable addresses (other code holds pointers to elements that must not move), frequent insertion and removal in the middle at known positions, or lists threaded through objects that also live elsewhere. For "a growable bunch of values", a dynamic array usually wins.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does push_front take a struct node **head instead of a struct node *head?

    C passes arguments by value. To make the caller's head point at the new node, the function must receive the address of head.
  2. 2. What is wrong with this loop? for (p = head; p != NULL; p = p->next) { free(p); }

    The increment p = p->next runs after free(p). Save p->next in a temporary before freeing.
  3. 3. The list is 5 -> 8 -> 12. After remove_value(&list, 5), what does list point to?

    When the first node matches, link is &list itself, so *link = doomed->next makes list point at the 8 node.
  4. 4. Which operation is O(1) in a doubly linked list but O(n) in a singly linked list without extra information?

    Removal needs the predecessor. A doubly linked node knows it through prev; a singly linked list has to search from the head.
  5. 5. What does reverse return for the list 1 -> 2 -> 3?

    The nodes are reused, not copied. When the loop ends, prev points at the old tail (3), which is the new head; the node holding 1 is now the last node.

Summary

  • A linked list is a chain of heap-allocated nodes; each holds a value and a next pointer, and the last next is NULL.
  • The list is represented by a head pointer; NULL means empty. Walk it with for (p = head; p != NULL; p = p->next).
  • Functions that change the head take struct node **. Walking a struct node **link makes insertion and deletion work the same at every position.
  • Free nodes with a loop that saves next before calling free; reset the head to NULL afterwards.
  • Reverse in place with prev, current and next pointers; keep a list sorted by inserting at the right link.
  • Doubly linked lists add prev pointers for backward walks and O(1) removal; a circular list with a sentinel removes all special cases.
  • Linked lists give O(1) insertion at known positions and stable addresses, but arrays are faster for indexing and scanning.

Next: Stacks and Queues, two simple but essential structures you can build on arrays or linked lists.