Skip to content

Expert · Data structures in C · topic 46 of 60 · 30 min

Singly linked lists

Explanation

A linked list stores elements in separate heap nodes; each node holds a value and a pointer to the next node, and the last points to NULL. Inserting at the head is O(1) and the list grows one node at a time, but reaching the k-th element means walking from the head (O(n)). Deleting cleanly uses a pointer-to-pointer, and the whole list must be freed node by node.

Why a linked list?

An array is one contiguous block: fast to index, but inserting in the middle means shifting everything, and growing means reallocating. A linked list instead links separate small blocks. Inserting or removing next to a node you already have is just changing two pointers, and there is never a big copy.

output
typedef struct Node {
    int value;
    struct Node *next;
} Node;

head ──► [ 10 | ● ]──► [ 20 | ● ]──► [ 30 | NULL ]
          node at 0x5a0  node at 0x7c0  node at 0x610   (anywhere on the heap)

Insert at the head and traverse

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

int push_front(Node **head, int value) {     /* Node ** so we can change the caller's head */
    Node *n = malloc(sizeof *n);
    if (!n) return -1;
    n->value = value;
    n->next = *head;                         /* new node points to the old first node */
    *head = n;                               /* head now points to the new node */
    return 0;
}

void print_list(const Node *head) {
    for (const Node *p = head; p != NULL; p = p->next) printf("%d -> ", p->value);
    printf("NULL\n");
}

Node *list = NULL;                           /* an empty list */
push_front(&list, 30);
push_front(&list, 20);
push_front(&list, 10);
print_list(list);                            /* 10 -> 20 -> 30 -> NULL */

Append at the tail

c
int push_back(Node **head, int value) {
    Node *n = malloc(sizeof *n);
    if (!n) return -1;
    n->value = value;
    n->next = NULL;
    Node **link = head;                      /* walk the links, not the nodes */
    while (*link) link = &(*link)->next;
    *link = n;                               /* works for an empty list too */
    return 0;
}
O(n) because it walks the whole list; keeping a tail pointer makes it O(1).

Delete a value (the pointer-to-pointer trick)

c
int remove_value(Node **head, int value) {
    for (Node **link = head; *link; link = &(*link)->next) {
        if ((*link)->value == value) {
            Node *dead = *link;
            *link = dead->next;              /* bypass the node */
            free(dead);
            return 1;
        }
    }
    return 0;                                /* not found */
}

before:  head ──► [10] ──► [20] ──► [30] ──► NULL
remove 20: the link inside [10] is changed to point at [30]
after:   head ──► [10] ──► [30] ──► NULL    and [20] is freed
Using Node ** means removing the first node needs no special case.

Freeing the whole list

c
void free_list(Node **head) {
    Node *p = *head;
    while (p) {
        Node *next = p->next;    /* save the link BEFORE freeing */
        free(p);
        p = next;
    }
    *head = NULL;
}
Careful: Classic linked-list bugs: freeing a node and then reading p->next from it (use after free; save next first), losing the rest of the list by overwriting a next pointer before saving it (a leak), and dereferencing NULL at the end of the list. Draw the boxes and arrows before writing pointer updates.
OperationLinked listArray
Access k-th elementO(n)O(1)
Insert/remove at the frontO(1)O(n)
Insert/remove after a known nodeO(1)O(n)
MemoryExtra pointer per node, scatteredCompact, cache-friendly
Think of it like this: A linked list is like a treasure hunt: each clue (node) holds a prize (value) and tells you where the next clue is hidden. To get the fifth prize you must follow clues one to four. Adding a new clue at the start just means writing where the old first clue is.
Tip: In practice, arrays (or dynamic arrays) are often faster than linked lists because of CPU caches. Linked lists shine when you insert and remove a lot in the middle while holding pointers to nodes, as operating-system kernels do for task queues.

Need help?

Stuck on a word or an idea? Search this course, or every course, and jump straight to the explanation or a worked question.

Try:

Watch the lesson

Singly linked lists · 1/6

Linked lists

In this lesson you will build a linked list in C.

Prefer a video by a teacher? Find free videos on “linked list in c implementation insert delete reverse” on YouTube ↗

In real life: A print queue in an office printer

A network printer's firmware keeps waiting print jobs in a linked list: new jobs are appended, the first job is removed when printing starts, and a cancelled job anywhere in the list is unlinked in O(1) once it is found, without moving the other jobs.

c
typedef struct Job { int id; char owner[20]; int pages; struct Job *next; } Job;
/* enqueue: append at the tail; start printing: remove the head; cancel: remove_value by id */

Practice (0/3 done)

Task 1 · Question

What is printed for a list built with push_front(&l, 1); push_front(&l, 2); push_front(&l, 3);?

Task 2 · Code · Javascript

The same linked-list algorithms in JavaScript, which runs here (objects play the role of heap nodes, null plays NULL): write pushFront(head, value) returning the new head, toArray(head), and removeValue(head, value) returning the new head with the first matching node removed.

Task 3 · Practice

Implement in C: push_front, push_back, remove_value (pointer-to-pointer style), reverse (in place, by turning each next pointer around) and free_list. Test with a sequence of operations, print after each step, and run under valgrind or AddressSanitizer to confirm no leaks.

Quick quiz

Question 1

1.What is the time to access the 1000th element of a linked list?

Question 2

2.Why does push_front take Node **head?

Question 3

3.When freeing a list, why save p->next before free(p)?

Question 4

4.How does the last node show the end of the list?

Read more (free)

Open a question to see the answer and why. The first ones are this topic's own quiz, so try the quiz above before you peek.

What is the time to access the 1000th element of a linked list?

Answer: O(n): walk from the head

No random access.

Why does push_front take Node **head?

Answer: To change the caller's head pointer

The function must update the caller's pointer.

When freeing a list, why save p->next before free(p)?

Answer: After free, reading p->next is use after free

The node is gone after free.

How does the last node show the end of the list?

Answer: Its next pointer is NULL

NULL marks the end.

What does it cost to insert a new node at the head of a singly linked list with n nodes?Related

Answer: O(1)

Point the new node at the old head; nothing else moves.

From Linked lists

With while fast and fast.next, which node does slow stop at for 10 → 20 → 30 → 40?Related

Answer: 30

For an even length this loop gives the second middle: slow moves to 20, then 30, while fast moves to 30, then off the end.

From Fast and slow pointers and merging lists

For a struct pointer s, what is s->name the same as?Related

Answer: (*s).name

The arrow operator dereferences the pointer and then picks the member.

From Pointers, the stack and the heap

Where does an array NOT decay to a pointer?Related

Answer: In sizeof a

sizeof (and &a) see the whole array.

From Pointers and arrays

Pass the quiz (60% or more) or mark this topic as done when you are ready.

Your progress is saved on this device only.

Next: Stacks →

Next steps

  1. 4 more topics in “Data structures in C” before its exam: Stacks, Queues and circular buffers, Binary search trees, Hash tables.
  2. Module 10 exam: Data structures in C · 12 questions · 25 min, without help. 5 topics of this module still to finish first.
  3. Then the next module, Debugging and tools. 60 topics left in the course before the final exam.

← Previous: Function pointers and callbacks