These are the notes for C Coding Questions, episode 26, placement practice for people who finished the SyntaxPilot C course. Linked list questions, part one: building a list in input order and printing it, inserting at the head and at the tail from a function, and deleting a node by value (the head, the middle, the last node and a missing value).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, glibc, Linux x86-64: 4-byte int, 8-byte pointers), the SyntaxPilot compiler's C command with warnings on, and every output below is real. The fixed programs were also run under valgrind --leak-check=full: no errors and no leaks. In the input lines below, / separates lines.
Real-life pictures
| In real life | In C |
|---|---|
| the engine, where the train starts | head: a pointer to the first node |
| a coach with passengers and a coupling hook | a node: data and next (the address of the next node) |
| nothing behind the last coach | NULL: the last node's next |
| add a coach at the front or the back; no other coach moves | insert: change one or two arrows |
| take a coach out and couple its neighbours | delete: prev->next = p->next; free(p); |
A node in C
struct Node {
int data;
struct Node *next; /* address of the next node */
};
struct Node *n = malloc(sizeof *n); /* memory that lives until free(n) */
n->data = 7; /* n->data means (*n).data */
n->next = NULL; /* nothing after it yet */
for (struct Node *p = head; p != NULL; p = p->next) /* walk any list */
printf("%d -> ", p->data);
- A linked list is a chain of nodes; each node stores a value and the address of the next node. The list is reached through one pointer, head. An empty list is
head == NULL. - A struct may contain a pointer to its own type (a self-referential structure). It can't contain a whole copy of itself:
#include <stdio.h>
struct Node { int d; struct Node next; };
int main(){return 0;}
main.c:2:34: error: field 'next' has incomplete type
2 | struct Node { int d; struct Node next; };
| ^~~~
- Nodes come from
malloc(the heap), so they outlive the function that made them. Everymallocneeds onefree.sizeof(struct Node)is 16 here: 4 fordata, 4 bytes of padding, 8 fornext. sizeof *nmeans "the size of what n points to", so the line stays right if the type changes.
Q1: Build a list and print it
Problem. Read numbers until the input ends, build a linked list in the same order, print it as 1 -> 2 -> … -> NULL, and free it.
Think out loud.
1 2 3 4 5→1 -> 2 -> 3 -> 4 -> 5 -> NULL.- Edge cases: no numbers (print
NULL), one number, freeing every node.
The obvious attempt: insert every number at the head
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next; /* address of the next node */
};
void print_list(struct Node *head) {
for (struct Node *p = head; p != NULL; p = p->next)
printf("%d -> ", p->data);
printf("NULL\n");
}
int main() {
struct Node *head = NULL;
int v;
while (scanf("%d", &v) == 1) {
struct Node *n = malloc(sizeof *n);
if (n == NULL) return 1;
n->data = v;
n->next = head; /* new node in front */
head = n;
}
print_list(head);
return 0;
}
Input: 1 2 3 4 5
5 -> 4 -> 3 -> 2 -> 1 -> NULL
Why it failed
Inserting at the head puts each new number in front of all the earlier ones, so the last number read comes first. (This program also never frees its nodes: a memory leak.)
Walking to the end for every new number would give the right order, but each walk costs O(n), so building n nodes would cost O(n²).
The fix: keep a tail pointer
Remember the last node in tail; hang each new node after it and move tail on: O(1) per number. The first node is special: when head is NULL there is no last node yet.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next; /* address of the next node */
};
void print_list(struct Node *head) {
for (struct Node *p = head; p != NULL; p = p->next)
printf("%d -> ", p->data);
printf("NULL\n");
}
void free_list(struct Node *head) {
while (head != NULL) {
struct Node *next = head->next; /* save it before free */
free(head);
head = next;
}
}
int main() {
struct Node *head = NULL, *tail = NULL;
int v;
while (scanf("%d", &v) == 1) {
struct Node *n = malloc(sizeof *n);
if (n == NULL) return 1;
n->data = v;
n->next = NULL;
if (head == NULL) head = n; /* the first node */
else tail->next = n; /* hang it after the last */
tail = n;
}
print_list(head);
free_list(head);
return 0;
}
| Input | Output |
|---|---|
1 2 3 4 5 |
1 -> 2 -> 3 -> 4 -> 5 -> NULL |
| (nothing) | NULL |
42 |
42 -> NULL |
free_list saves head->next before free(head): after free, that node's memory is no longer ours, and reading it is use after free (undefined behaviour).
Complexity: O(n) time to build, print and free; O(n) space (one 16-byte node per number).
Q2: Insert at the head and at the tail, in functions
Problem. Write push_front(head, v) and push_back(head, v). Input lines say where: b 20 = back, f 10 = front. Print the list after each insert.
Think out loud.
b 20,b 30,f 10,b 40→10 -> 20 -> 30 -> 40 -> NULL.- Edge cases: inserting into an empty list, a one-node list, and main's
headmust change when we insert at the front (or into an empty list).
The obvious attempt: pass head
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
void print_list(struct Node *head) {
for (struct Node *p = head; p != NULL; p = p->next)
printf("%d -> ", p->data);
printf("NULL\n");
}
void push_front(struct Node *head, int v) {
struct Node *n = malloc(sizeof *n);
if (n == NULL) exit(1);
n->data = v;
n->next = head;
head = n; /* the new front */
}
int main() {
struct Node *head = NULL;
push_front(head, 30);
push_front(head, 20);
push_front(head, 10);
print_list(head);
return 0;
}
NULL
No warning, no error, and an empty list.
Why it failed
C passes every argument by value: the head inside push_front is a copy of main's head. head = n; changed the copy; main's head stayed NULL. The three nodes were allocated and are now unreachable: leaked. It's the swap(x, y) mistake from episode 20.
The fix: pass the address of head (struct Node **)
head is a pointer, so its address is a pointer to a pointer, struct Node **. Call push_front(&head, 10); inside, *head is main's head, and *head = n; changes it. (Another common style: return the new head, head = push_front(head, 10);.)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
void print_list(struct Node *head) {
for (struct Node *p = head; p != NULL; p = p->next)
printf("%d -> ", p->data);
printf("NULL\n");
}
struct Node *new_node(int v) {
struct Node *n = malloc(sizeof *n);
if (n == NULL) exit(1);
n->data = v;
n->next = NULL;
return n;
}
void push_front(struct Node **head, int v) { /* O(1) */
struct Node *n = new_node(v);
n->next = *head;
*head = n; /* changes main's head */
}
void push_back(struct Node **head, int v) { /* O(n) */
struct Node *n = new_node(v);
if (*head == NULL) { *head = n; return; } /* empty list */
struct Node *p = *head;
while (p->next != NULL) p = p->next; /* walk to the last */
p->next = n;
}
int main() {
struct Node *head = NULL;
char where;
int v;
while (scanf(" %c %d", &where, &v) == 2) {
if (where == 'f') push_front(&head, v);
else push_back(&head, v);
print_list(head);
}
while (head != NULL) { struct Node *t = head->next; free(head); head = t; }
return 0;
}
Input: b 20 / b 30 / f 10 / b 40
20 -> NULL
20 -> 30 -> NULL
10 -> 20 -> 30 -> NULL
10 -> 20 -> 30 -> 40 -> NULL
Input: f 7
7 -> NULL
The first push_back went into an empty list; push_front changed main's head.
Complexity: push_front O(1). push_back O(n) (it walks to the last node), or O(1) if you also keep a tail pointer as in Q1. O(1) extra space per insert.
Q3: Delete the first node with value v
Problem. Read n, n numbers (the list), then values to delete one by one; print the list after each delete, or not found.
Think out loud.
10 -> 20 -> 30 -> 40: delete 30 →10 -> 20 -> 40; delete 10 (the head) →20 -> 40; delete 99 → not found.- Edge cases: the head, the last node, a missing value, the list becoming empty, duplicates (delete the first one).
The obvious attempt: stop just before v
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
void print_list(struct Node *head) {
for (struct Node *p = head; p != NULL; p = p->next)
printf("%d -> ", p->data);
printf("NULL\n");
}
void push_back(struct Node **head, int v);
void delete_value(struct Node *head, int v) {
struct Node *p = head;
while (p->next->data != v) /* stop just before v */
p = p->next;
struct Node *gone = p->next;
p->next = gone->next; /* skip over it */
free(gone);
}
int main() {
struct Node *head = NULL;
int n, v;
scanf("%d", &n);
for (int i = 0; i < n; i++) { scanf("%d", &v); push_back(&head, v); }
while (scanf("%d", &v) == 1) {
printf("delete %d: ", v);
fflush(stdout);
delete_value(head, v);
print_list(head);
}
return 0;
}
void push_back(struct Node **head, int v) { /* from Q2 */
struct Node *n = malloc(sizeof *n);
if (n == NULL) exit(1);
n->data = v;
n->next = NULL;
if (*head == NULL) { *head = n; return; }
struct Node *p = *head;
while (p->next != NULL) p = p->next;
p->next = n;
}
Input: 4 / 10 20 30 40 / 30 10
delete 30: 10 -> 20 -> 40 -> NULL
delete 10:
Segmentation fault
fflush(stdout) pushes the printed text out immediately; without it, the buffered delete 10: would be lost when the program is killed.
Why it failed
The loop only ever looks at p->next->data, never at the head's own data. Deleting 10, nothing matches, p walks to 40, and p->next is NULL, so p->next->data reads through a NULL pointer. That is undefined behaviour; on Linux the operating system stops the program: Segmentation fault. A missing value (99) crashes the same way.
The head is special: no node points to it, so there is no "previous" node to re-hook. Deleting it means moving head itself, which (as in Q2) needs struct Node **.
The fix: walk with prev and p; handle the head and not found
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
void print_list(struct Node *head) {
for (struct Node *p = head; p != NULL; p = p->next)
printf("%d -> ", p->data);
printf("NULL\n");
}
void push_back(struct Node **head, int v);
int delete_value(struct Node **head, int v) {
struct Node *p = *head, *prev = NULL;
while (p != NULL && p->data != v) { /* find v */
prev = p;
p = p->next;
}
if (p == NULL) return 0; /* not in the list */
if (prev == NULL) *head = p->next; /* deleting the head */
else prev->next = p->next; /* skip over it */
free(p);
return 1;
}
int main() {
struct Node *head = NULL;
int n, v;
scanf("%d", &n);
for (int i = 0; i < n; i++) { scanf("%d", &v); push_back(&head, v); }
while (scanf("%d", &v) == 1) {
printf("delete %d: ", v);
if (delete_value(&head, v)) print_list(head);
else printf("not found\n");
}
while (head != NULL) delete_value(&head, head->data); /* free all */
return 0;
}
void push_back(struct Node **head, int v) { /* from Q2 */
struct Node *n = malloc(sizeof *n);
if (n == NULL) exit(1);
n->data = v;
n->next = NULL;
if (*head == NULL) { *head = n; return; }
struct Node *p = *head;
while (p->next != NULL) p = p->next;
p->next = n;
}
Input: 4 / 10 20 30 40 / 30 10 99 40 20
delete 30: 10 -> 20 -> 40 -> NULL
delete 10: 20 -> 40 -> NULL
delete 99: not found
delete 40: 20 -> NULL
delete 20: NULL
| Input | Output |
|---|---|
3 / 7 7 8 / 7 (duplicates) |
delete 7: 7 -> 8 -> NULL |
0 / 5 (empty list) |
delete 5: not found |
Complexity: O(n) to find v (it may be last, or missing); O(1) to unlink once found; O(1) extra space.
Complexity summary
| Operation | Time | Extra space |
|---|---|---|
| Build n nodes with a tail pointer | O(n) | O(n) for the nodes |
| Build by walking to the end each time | O(n²) | O(n) |
| Print / free | O(n) | O(1) |
push_front |
O(1) | O(1) |
push_back |
O(n), O(1) with a tail | O(1) |
| Delete by value | O(n) find + O(1) unlink | O(1) |
Array vs linked list: an array reaches a[i] in O(1) but inserting at the front shifts every element (O(n)); a list inserts at the front in O(1) but reaching the i-th node means walking (O(n)). Arrays are also faster to scan in practice, because their elements sit next to each other in memory.
Common mistakes (and the real results)
| Mistake | What happens | Why | Fix |
|---|---|---|---|
| insert every number at the head | 5 -> 4 -> 3 -> 2 -> 1 -> NULL |
each goes in front | a tail pointer |
void push_front(struct Node *head, …) |
NULL: an empty list, no warning |
head is a copy |
struct Node **head, or return the new head |
while (p->next->data != v) |
Segmentation fault |
head skipped; reads NULL->data |
prev + p, check p != NULL |
free(p); p = p->next; |
use after free (undefined behaviour) | p's memory is gone |
save next first |
never calling free |
memory leak (valgrind reports it) | malloc without free |
free every node |
struct Node next; inside struct Node |
error: field 'next' has incomplete type |
a struct can't contain itself | struct Node *next; |
forgetting n->next = NULL |
prints garbage or crashes | malloc memory isn't zeroed |
always set next |
Your turn: insert into a sorted list (solution)
Problem. The list is sorted (smallest first). Insert v so it stays sorted.
Idea. It's Q3 backwards: walk with prev and p until p->data >= v (or the end), then hook the new node between them. If prev is still NULL, the new node is the new head (this also covers the empty list). O(n) time, O(1) extra space.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
void print_list(struct Node *head) {
for (struct Node *p = head; p != NULL; p = p->next)
printf("%d -> ", p->data);
printf("NULL\n");
}
void insert_sorted(struct Node **head, int v) {
struct Node *n = malloc(sizeof *n);
if (n == NULL) exit(1);
n->data = v;
struct Node *p = *head, *prev = NULL;
while (p != NULL && p->data < v) { /* stop at the first bigger-or-equal */
prev = p;
p = p->next;
}
n->next = p; /* hook in front of p */
if (prev == NULL) *head = n; /* new head (or empty list) */
else prev->next = n;
}
int main() {
struct Node *head = NULL;
int v;
while (scanf("%d", &v) == 1) {
insert_sorted(&head, v);
printf("insert %d: ", v);
print_list(head);
}
while (head != NULL) { struct Node *t = head->next; free(head); head = t; }
return 0;
}
Input: 20 10 40 30 5 50
insert 20: 20 -> NULL
insert 10: 10 -> 20 -> NULL
insert 40: 10 -> 20 -> 40 -> NULL
insert 30: 10 -> 20 -> 30 -> 40 -> NULL
insert 5: 5 -> 10 -> 20 -> 30 -> 40 -> NULL
insert 50: 5 -> 10 -> 20 -> 30 -> 40 -> 50 -> NULL
Inserting every number this way is insertion sort on a list: O(n²) in total.
Practice questions (with solutions)
1. Count the nodes and sum the data.
Solution
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
void push_front(struct Node **head, int v) {
struct Node *n = malloc(sizeof *n);
if (n == NULL) exit(1);
n->data = v;
n->next = *head;
*head = n;
}
int main() {
struct Node *head = NULL;
int v;
while (scanf("%d", &v) == 1) push_front(&head, v);
int count = 0;
long sum = 0;
for (struct Node *p = head; p != NULL; p = p->next) {
count++;
sum += p->data;
}
printf("count = %d, sum = %ld\n", count, sum);
while (head != NULL) { struct Node *t = head->next; free(head); head = t; }
return 0;
}
| Input | Output |
|---|---|
10 20 30 40 |
count = 4, sum = 100 |
| (nothing) | count = 0, sum = 0 |
The sum is a long so that many large ints don't overflow as easily. O(n) time, O(1) extra space.
2. Delete every node with value v.
Solution
This one uses a pointer to the arrow (struct Node **pp): pp points at whichever next field (or head itself) points at the current node, so the head needs no special case.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
void print_list(struct Node *head) {
for (struct Node *p = head; p != NULL; p = p->next)
printf("%d -> ", p->data);
printf("NULL\n");
}
int delete_all(struct Node **head, int v) { /* returns how many were deleted */
int removed = 0;
struct Node **pp = head; /* the arrow that points at the current node */
while (*pp != NULL) {
if ((*pp)->data == v) {
struct Node *gone = *pp;
*pp = gone->next; /* re-hook the arrow past it */
free(gone);
removed++;
} else {
pp = &(*pp)->next; /* move to the next arrow */
}
}
return removed;
}
int main() {
struct Node *head = NULL, *tail = NULL;
int n, v;
if (scanf("%d", &n) != 1) return 1;
for (int i = 0; i < n; i++) {
scanf("%d", &v);
struct Node *x = malloc(sizeof *x);
if (x == NULL) return 1;
x->data = v;
x->next = NULL;
if (head == NULL) head = x; else tail->next = x;
tail = x;
}
while (scanf("%d", &v) == 1) {
int r = delete_all(&head, v);
printf("delete all %d (%d removed): ", v, r);
print_list(head);
}
while (head != NULL) { struct Node *t = head->next; free(head); head = t; }
return 0;
}
Input: 6 / 7 1 7 7 2 7 / 7 3 1 2
delete all 7 (4 removed): 1 -> 2 -> NULL
delete all 3 (0 removed): 1 -> 2 -> NULL
delete all 1 (1 removed): 2 -> NULL
delete all 2 (1 removed): NULL
O(n) time, O(1) extra space.
3. Insert at position k (0 = the head).
Solution
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
void print_list(struct Node *head) {
for (struct Node *p = head; p != NULL; p = p->next)
printf("%d -> ", p->data);
printf("NULL\n");
}
int insert_at(struct Node **head, int k, int v) { /* k = 0: new head; returns 0 if k is too big */
struct Node **pp = head;
for (int i = 0; i < k; i++) {
if (*pp == NULL) return 0; /* the list is shorter than k */
pp = &(*pp)->next;
}
struct Node *n = malloc(sizeof *n);
if (n == NULL) exit(1);
n->data = v;
n->next = *pp;
*pp = n;
return 1;
}
int main() {
struct Node *head = NULL;
int k, v;
while (scanf("%d %d", &k, &v) == 2) {
printf("insert %d at %d: ", v, k);
if (insert_at(&head, k, v)) print_list(head);
else printf("position too big\n");
}
while (head != NULL) { struct Node *t = head->next; free(head); head = t; }
return 0;
}
Input (k v per line): 0 20 / 0 10 / 2 40 / 2 30 / 9 99
insert 20 at 0: 20 -> NULL
insert 10 at 0: 10 -> 20 -> NULL
insert 40 at 2: 10 -> 20 -> 40 -> NULL
insert 30 at 2: 10 -> 20 -> 30 -> 40 -> NULL
insert 99 at 9: position too big
O(k) time, O(1) extra space.
Quick quiz
#include <stdio.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node c = {3, NULL};
struct Node b = {2, &c};
struct Node a = {1, &b};
printf("%d\n", a.next->next->data);
return 0;
}
What does it print? (A) 1 (B) 2 (C) 3 (D) Segmentation fault
Answer
(C) 3 (real output: 3). a.next is &b, b.next is &c, so a.next->next->data is c.data. a is a struct, so it uses .; a.next and a.next->next are pointers, so they use ->. The nodes don't come from malloc here: they are local variables on the stack, which is fine as long as nothing uses them after main returns.
Interview questions
- What is a linked list? How is it different from an array? Nodes joined by pointers vs one contiguous block; O(1) front insert vs O(1) indexing.
- What is a self-referential structure? A struct with a pointer to its own type:
struct Node *next;. - How do you insert at the head?
n->next = head; head = n;O(1). - How do you insert at the tail in O(1)? Keep a
tailpointer. - Why does
void push_front(struct Node *head, int v)not change the caller's list? Arguments are passed by value; pass&head(struct Node **) or return the new head. - How do you delete a node by value? Which cases are special? Walk with
prevandp; the head (no previous node), not found (pbecomes NULL), the list becoming empty. - Why save
nextbeforefree? Reading a freed node is use after free. - How do you free a whole list? Walk it, saving
nextbefore eachfree. - What is a memory leak? How do you find one? Allocated memory that can no longer be freed; tools like valgrind or AddressSanitizer report it.
- What does
sizeof(struct Node)print, and why not 12? 16 on x86-64: the 8-byte pointer must start at a multiple of 8, so 4 padding bytes followdata.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Linked list | Nodes chained by pointers | 10 -> 20 -> 30 -> NULL |
| Node | One element: data + a pointer to the next node | struct Node |
data |
The value a node holds | n->data = 7; |
next |
The address of the next node | n->next = NULL; |
| head | Pointer to the first node; NULL for an empty list | struct Node *head = NULL; |
| tail | Pointer to the last node | Q1 |
| NULL | The pointer value that points nowhere | the end of the list |
| Self-referential structure | A struct with a pointer to its own type | struct Node *next; |
-> (arrow) |
Member access through a pointer | p->data = (*p).data |
malloc / free |
Get / give back heap memory | malloc(sizeof *n) |
| Heap | Memory that lives until freed | every node |
| Traverse / walk | Visit every node from head, following next | p = p->next |
| Insert at the head / tail | Add a node before the first / after the last | push_front, push_back |
| Pass by value | A function gets a copy of each argument | Q2's bug |
| Pointer to pointer | The address of a pointer variable | struct Node **head |
| Segmentation fault | The OS stops a program that touches memory it doesn't own | NULL->data |
| Undefined behaviour | The C standard says nothing about what happens | NULL dereference, use after free |
| Use after free | Reading memory after free |
free(p); p = p->next; |
| Memory leak | Memory that is never freed and can't be reached | Q2's bug |
| valgrind | A tool that reports memory errors and leaks | valgrind --leak-check=full ./main |
fflush(stdout) |
Send buffered output now | before a crash |
| Padding | Unused bytes for alignment | 4 bytes in struct Node |
Summary
- A node holds
dataandnext; the list starts at head and ends at NULL. Walk withfor (p = head; p != NULL; p = p->next). - Build in input order with a tail pointer (O(1) per number). Free every node, saving
nextfirst. - A function that must change
headtakesstruct Node **(or returns the new head): arguments are copies. - Insert at the head: O(1). At the tail: O(n), or O(1) with a tail pointer.
- Delete: walk with prev and p; the head and "not found" are the special cases; never read through NULL.
Next episode: Linked list questions II: reverse a linked list, find the middle with slow and fast pointers, and detect a loop with Floyd's cycle detection.