SyntaxPilot
Courses/C Programming/Lesson 22

C Programming · Lesson 22 of 30 · 11 min

Linked lists

queued

These are the notes for C episode 22. Pointers (episodes 10-11), structures (episode 12) and malloc (episode 14) come together here into your first real data structure. It starts with a clinic token queue stored in an array, where every emergency patient at the front makes everyone move back one place, until the program can't finish at all. You fix it by inventing the linked list: a chain of nodes, each holding its data and a pointer to the next node, like coaches coupled into a train. Every example was compiled with gcc -O2 -Wno-unused-result main.c -o main -lm (gcc 13, the same command as the SyntaxPilot compiler) and run as shown. The online compiler stops a program after 8 seconds and reports Time Limit Exceeded.

The problem: the emergency patient

Real-life example: a clinic waiting room. Patients sit on a row of chairs in token order: 101, 102, 103. An emergency patient must be seen first, so he needs chair number one. Everyone stands up and moves one chair back. With three people that's fine; with a hundred, a hundred people shuffle, and every emergency makes the whole row move again.

An array is that row of chairs:

#include <stdio.h>

#define N 1000
int queue[N];
int count = 0;

void add_front(int token) {
    for (int i = count; i > 0; i--)
        queue[i] = queue[i - 1];
    queue[0] = token;
    count++;
}

int main() {
    for (int t = 1; t <= N; t++)
        add_front(t);
    printf("Front: token %d, patients: %d\n", queue[0], count);
    return 0;
}
Front: token 1000, patients: 1000

Instant. Now change N to 600000, the size of a city hospital's records: the program runs for 8 seconds and the online compiler stops it with Time Limit Exceeded. (On a fast machine 300,000 front inserts already take about 3.5 seconds; 600,000 take four times as long.)

Why the array is slow

  • Array items sit side by side in memory and index 0 must be the front, so one insert at the front moves every item already there.
  • 600,000 inserts × up to 600,000 moves ≈ 180 billion moves. The work grows with the square of the number of patients: double the patients, four times the time. In Big-O notation that's O(n) per insert and O(n²) for all of them.
  • N is fixed when you compile: patient N + 1 has no chair at all.

Idea: stop keeping them side by side.

The idea: a train, not a row of chairs

A train A linked list In C
A coach (passengers + a coupling) a node struct node { int token; struct node *next; };
The coupling to the next coach the next pointer n->next
The engine, where the train starts the head struct node *head
The last coach couples to nothing the end of the list next == NULL
Add a coach at the front: couple it on insert at the front two pointer changes, nobody moves

A linked list is a chain of nodes where each node stores its data and the address of the next node. The nodes don't need to be next to each other in memory: each one only knows where the next one is.

A node: a struct that points to its own type

The obvious attempt puts the next node inside the node:

struct node {
    int token;
    struct node next;
};
main.c:5:17: error: field 'next' has incomplete type

A node containing a whole node, which contains a whole node, forever, would be infinitely big. A coupling doesn't contain the next coach; it holds on to it. So next is a pointer, which is always the same size (8 bytes on a 64-bit machine):

struct node {
    int token;
    struct node *next;
};

A struct with a pointer to its own type is a self-referential structure.

Walking a list

Three nodes linked by hand, then printed by following the pointers:

#include <stdio.h>

struct node {
    int token;
    struct node *next;
};

int main() {
    struct node c = {103, NULL};
    struct node b = {102, &c};
    struct node a = {101, &b};
    struct node *head = &a;

    struct node *p = head;
    while (p != NULL) {
        printf("%d -> ", p->token);
        p = p->next;
    }
    printf("NULL\n");
    return 0;
}
101 -> 102 -> 103 -> NULL
head ──► [101 | next] ──► [102 | next] ──► [103 | NULL]
  • p = p->next moves one node forward; while (p != NULL) stops after the last node. This is called traversing the list.
  • p->token is short for (*p).token (episode 12).
  • There is no index: to reach the fifth node you walk past the first four. Arrays are fast at jumping to an index; lists are fast at inserting and removing.

Insert at the front with malloc

Real queues grow while the program runs, so each node comes from malloc (episode 14).

The obvious attempt loses the list

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

struct node {
    int token;
    struct node *next;
};

void print(struct node *head) {
    printf("Queue: ");
    for (struct node *p = head; p != NULL; p = p->next)
        printf("%d ", p->token);
    printf("\n");
}

void add_front(struct node *head, int token) {
    struct node *n = malloc(sizeof(struct node));
    n->token = token;
    n->next = head;
    head = n;
}

int main() {
    struct node *head = NULL;
    add_front(head, 103);
    add_front(head, 102);
    add_front(head, 101);
    print(head);
    return 0;
}
Queue: 

Three nodes were created, and the list is empty. C passes arguments by value (episode 7): add_front got its own copy of head, head = n changed the copy, and main's head stayed NULL. The three nodes are lost in memory (a memory leak).

The fix: return the new head

struct node *add_front(struct node *head, int token) {
    struct node *n = malloc(sizeof(struct node));
    n->token = token;
    n->next = head;      // the new node points at the old first node
    return n;            // and becomes the new head
}

int main() {
    struct node *head = NULL;
    head = add_front(head, 103);
    head = add_front(head, 102);
    head = add_front(head, 101);
    print(head);
    return 0;
}
Queue: 101 102 103 

(The other common style passes the address of head, void add_front(struct node **head, int token) with *head = n;, called as add_front(&head, 101);. Both are correct; returning the head is easier to read when you're starting.)

The test that broke the array

int main() {
    struct node *head = NULL;
    int count = 0;
    for (int t = 1; t <= 600000; t++) {
        head = add_front(head, t);
        count++;
    }
    printf("Front: token %d, patients: %d\n", head->token, count);
    return 0;
}
Front: token 600000, patients: 600000

A fraction of a second (about 0.01 s for 300,000 on the same machine where the array took 3.5 s). Each insert at the front changes two pointers however long the list is: O(1).

Insert at the end

Normal patients join at the back:

struct node *add_back(struct node *head, int token) {
    struct node *n = malloc(sizeof(struct node));
    n->token = token;
    n->next = NULL;              // it will be the last node
    if (head == NULL)            // empty list: the new node is the whole list
        return n;
    struct node *p = head;
    while (p->next != NULL)      // walk to the last node
        p = p->next;
    p->next = n;                 // couple it on
    return head;                 // the head didn't change
}

Walking to the end takes as many steps as there are nodes (O(n)). Programs that add at the back often keep a second pointer, tail, to the last node, making it O(1); you'll use that in the queues of episode 23.

Delete the first node

struct node *call_next(struct node *head) {
    if (head == NULL) {
        printf("No one is waiting\n");
        return NULL;
    }
    struct node *first = head;
    printf("Calling token %d\n", first->token);
    head = head->next;           // move head to the second node
    free(first);                 // then give the first node back
    return head;
}

Order matters: keep a pointer to the node, move head, then free. If you freed first you could no longer read its next.

Free the whole list

Every malloc needs a free:

void free_all(struct node *head) {
    while (head != NULL) {
        struct node *next = head->next;   // save the next address first
        free(head);
        head = next;
    }
}

Writing free(p); p = p->next; reads a node that has already been freed: a use-after-free bug. It may even seem to work, until it doesn't. Episode 26 shows tools (AddressSanitizer, valgrind) that catch it.

Mini project: a clinic token queue

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

struct node {
    int token;
    struct node *next;
};

void print(struct node *head) {
    printf("Queue: ");
    for (struct node *p = head; p != NULL; p = p->next)
        printf("%d ", p->token);
    printf("\n");
}

struct node *add_front(struct node *head, int token) {
    struct node *n = malloc(sizeof(struct node));
    n->token = token;
    n->next = head;
    return n;
}

struct node *add_back(struct node *head, int token) {
    struct node *n = malloc(sizeof(struct node));
    n->token = token;
    n->next = NULL;
    if (head == NULL)
        return n;
    struct node *p = head;
    while (p->next != NULL)
        p = p->next;
    p->next = n;
    return head;
}

struct node *call_next(struct node *head) {
    if (head == NULL) {
        printf("No one is waiting\n");
        return NULL;
    }
    struct node *first = head;
    printf("Calling token %d\n", first->token);
    head = head->next;
    free(first);
    return head;
}

void free_all(struct node *head) {
    while (head != NULL) {
        struct node *next = head->next;
        free(head);
        head = next;
    }
}

int main() {
    struct node *q = NULL;
    q = add_back(q, 101);
    q = add_back(q, 102);
    q = add_back(q, 103);
    print(q);
    q = add_front(q, 999);   // emergency!
    print(q);
    q = call_next(q);
    q = call_next(q);
    print(q);
    free_all(q);
    return 0;
}
Queue: 101 102 103 
Queue: 999 101 102 103 
Calling token 999
Calling token 101
Queue: 102 103 

Token 999 jumps the queue without anyone moving.

Arrays vs linked lists

Array Linked list
Memory one block, side by side separate nodes anywhere, linked by pointers
Size fixed (or realloc and copy) grows and shrinks one node at a time
Get item number k instant: a[k] (O(1)) walk k nodes (O(k))
Insert/delete at the front move everything (O(n)) two pointer changes (O(1))
Insert/delete in the middle move everything after it (O(n)) O(1) once you have the node before it
Extra memory none one pointer per node
Cache friendly yes (neighbours are close) less (nodes are scattered)

Use an array when you mostly read by index; use a list when you insert and remove a lot, especially at the front.

Common mistakes (and the real messages)

Mistake What you see Why Fix
struct node next; inside struct node error: field 'next' has incomplete type A node can't contain itself struct node *next;
void add_front(head, ...) { head = n; } No error: the list stays empty The function changed a copy of head head = add_front(head, ...) (or pass &head)
head->token on an empty list Segmentation fault head is NULL if (head == NULL) ... first
free(p); p = p->next; Use after free (may seem to work) Reads freed memory Save next, then free
Forgetting free No error: a memory leak Nodes are never given back free_all(head) at the end
while (p->next != NULL) on an empty list Segmentation fault p itself is NULL Handle head == NULL first, like add_back
Forgetting n->next = NULL for the last node Garbage or a crash while walking malloc memory isn't zeroed Always set next

The empty-list crash, run in the online compiler:

int main() {
    struct node *head = NULL;
    printf("First token: %d\n", head->token);
    return 0;
}
Segmentation fault

Practice

  1. Write struct node *cancel(struct node *head, int token) that removes the patient with that token from anywhere in the queue (front, middle or end), and does nothing if the token isn't there.
  2. Write int count(struct node *head).
  3. Reverse a list in place (no new nodes): struct node *reverse(struct node *head). A classic interview question.
  4. Break free_all on purpose (free(head); head = head->next;) and compile with gcc -g -fsanitize=address. What does it report?
Solutions

1-3 (verified together; uses print, add_back and free_all from the mini project):

struct node *cancel(struct node *head, int token) {
    if (head == NULL)
        return NULL;
    if (head->token == token) {          // removing the first node changes head
        struct node *rest = head->next;
        free(head);
        return rest;
    }
    struct node *prev = head;            // find the node BEFORE the one to remove
    while (prev->next != NULL && prev->next->token != token)
        prev = prev->next;
    if (prev->next != NULL) {
        struct node *gone = prev->next;
        prev->next = gone->next;         // link around it
        free(gone);
    }
    return head;
}

int count(struct node *head) {
    int n = 0;
    for (struct node *p = head; p != NULL; p = p->next)
        n++;
    return n;
}

struct node *reverse(struct node *head) {
    struct node *prev = NULL;
    while (head != NULL) {
        struct node *next = head->next;  // save the rest of the list
        head->next = prev;               // turn this node's pointer around
        prev = head;
        head = next;
    }
    return prev;                         // the old last node is the new head
}

int main() {
    struct node *q = NULL;
    for (int t = 101; t <= 105; t++)
        q = add_back(q, t);
    print(q);
    q = cancel(q, 103);
    q = cancel(q, 101);
    q = cancel(q, 999);
    print(q);
    printf("Waiting: %d\n", count(q));
    q = reverse(q);
    print(q);
    free_all(q);
    return 0;
}
Queue: 101 102 103 104 105 
Queue: 102 104 105 
Waiting: 3
Queue: 105 104 102 

4. AddressSanitizer stops the program with ERROR: AddressSanitizer: heap-use-after-free and points at the line head = head->next;. Episode 26 covers it in detail.

Quick quiz

// list: head -> 10 -> 20 -> 30 -> NULL
struct node *p = head;
while (p->next != NULL)
    p = p->next;
printf("%d", p->token);
  • A. 10
  • B. 20
  • C. 30
  • D. Segmentation fault
Answer

C: 30. The loop stops on the node whose next is NULL, which is the last node. That is exactly how add_back finds the end. (On an empty list, with head == NULL, this loop would crash: that's why add_back checks first.)

Interview questions

  • What is a linked list? How is it different from an array?
  • Why must next be a pointer? What is a self-referential structure?
  • What is the time complexity of inserting at the front, at the end, and of finding the k-th element?
  • Why does void add_front(struct node *head, int x) not change the caller's list? Give two ways to fix it.
  • How do you delete a node from the middle of a singly linked list?
  • How do you free a linked list without a use-after-free?
  • Reverse a singly linked list in place. What are its time and space complexity? (O(n) time, O(1) extra space.)
  • How do you find the middle of a list in one pass? (Two pointers: one moves 1 step, the other 2.)
  • How do you detect a cycle in a linked list? (Floyd's slow/fast pointers.)
  • What is a doubly linked list? What does it cost and what does it make easier?
  • When would you still prefer an array?

Glossary

Term Meaning Example
Data structure A way of organising data in memory so certain operations are fast array, linked list
Linked list A chain of nodes, each pointing to the next 101 -> 102 -> 103 -> NULL
Node One element of a linked list: data plus a pointer to the next node struct node { int token; struct node *next; };
next pointer The address of the following node; NULL in the last node n->next = head;
Head A pointer to the first node; NULL means the list is empty struct node *head = NULL;
Tail The last node (or a pointer kept to it) the node whose next is NULL
NULL A pointer to nothing; marks the end of the list while (p != NULL)
Self-referential structure A struct with a pointer to its own type struct node *next;
Incomplete type A type whose size the compiler doesn't know yet (a struct still being defined) struct node next; inside struct node
Traverse Visit every node by following next pointers p = p->next
-> Member access through a pointer: p->token is (*p).token p->next
malloc Asks for a block of memory at run time (episode 14) malloc(sizeof(struct node))
free Gives malloced memory back free(first);
Memory leak Memory that was allocated and never freed nodes lost by the void add_front
Use after free Reading or writing memory after it was freed free(p); p = p->next;
Pass by value A function gets copies of its arguments why head = n didn't reach main
Pointer to pointer The address of a pointer variable, so a function can change it struct node **head
Time Limit Exceeded The online compiler stopped a program that ran longer than 8 seconds the array with 600,000 inserts
Big-O (time complexity) How the work grows with the input size n O(1) list front insert, O(n) array front insert
Singly linked list Each node points only to the next one this episode
Doubly linked list Each node also points to the previous one struct node *prev, *next;

Summary

  • Inserting at the front of an array moves every item: fine for 1,000 items, Time Limit Exceeded for 600,000. Arrays also have a fixed size.
  • A linked list is a chain of nodes. Each node holds data and a pointer to the next node: struct node { int token; struct node *next; };. head points to the first node, and the last node's next is NULL.
  • Walk a list with p = p->next while p != NULL. There is no index.
  • Insert at the front with malloc in O(1). A function that changes the head must return the new head (or take &head), because C passes arguments by value.
  • Insert at the end by walking to the node whose next is NULL; handle the empty list first.
  • Delete: keep a pointer to the node, relink, then free. Free a list by saving next before each free.

Next episode: Stacks and queues: the undo button and the railway ticket counter, built from arrays and linked lists.