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.
Nis fixed when you compile: patientN + 1has 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->nextmoves one node forward;while (p != NULL)stops after the last node. This is called traversing the list.p->tokenis 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
- 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. - Write
int count(struct node *head). - Reverse a list in place (no new nodes):
struct node *reverse(struct node *head). A classic interview question. - Break
free_allon purpose (free(head); head = head->next;) and compile withgcc -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
nextbe 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; };.headpoints to the first node, and the last node'snextisNULL. - Walk a list with
p = p->nextwhilep != NULL. There is no index. - Insert at the front with
mallocin 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
nextisNULL; handle the empty list first. - Delete: keep a pointer to the node, relink, then
free. Free a list by savingnextbefore eachfree.
Next episode: Stacks and queues: the undo button and the railway ticket counter, built from arrays and linked lists.