Lesson 9 · 9 of 20

A linked list · C

Program a linked list of tasks in C: nodes on the heap, adding at the end and at the front, removing by id and freeing the whole list.

C · A linked list in DMarlon Studio: the example's code and its output in the terminal

A linked list is a chain of nodes: each Task holds its data and a next pointer to the following one, and the last one has next set to NULL. Unlike an array, inserting or removing in the middle moves nothing: you just change a pointer.

new_task allocates a node with malloc, fills it in and links it in front of next. With NULL it creates a standalone node; with the current list, as in todo = new_task(4, "Server", todo), it puts it at the front, the fastest operation on a list.

append and remove_id use a pointer to a pointer, Task **link. It starts out pointing at todo and, at each step, moves on to point at the current node's next field. That removes the special case for the first node: when the loop stops, *link is exactly the pointer to change, whether it is the head or another node's next.

To remove a node, remove_id keeps it in gone, makes *link skip to gone->next and frees gone. In the output, task 2 disappears and the rest stay linked.

At the end, the while loop frees the whole list: it saves next before calling free, because once a node is freed you can no longer read its next field.

Code · main.c

#include <stdio.h>#include <stdlib.h>typedef struct Task { int id; const char *title; struct Task *next; } Task;// A new node on the heap, linked in front of `next` (NULL: the end).Task *new_task(int id, const char *title, Task *next) {    Task *t = malloc(sizeof *t);    if (!t) exit(EXIT_FAILURE);    t->id = id; t->title = title; t->next = next;    return t;}// Task **link points at the pointer we may change: head or some ->next.void append(Task **link, Task *t) {    while (*link) link = &(*link)->next;    *link = t;}void remove_id(Task **link, int id) {    while (*link && (*link)->id != id) link = &(*link)->next;    if (*link) { Task *gone = *link; *link = gone->next; free(gone); }}void print(const char *label, const Task *t) {    for (printf("%-9s", label); t; t = t->next) printf(" [%d %s]", t->id, t->title);    printf("\n");}int main(void) {    Task *todo = NULL;  // an empty list    append(&todo, new_task(1, "Invoice", NULL)); append(&todo, new_task(2, "Call Ana", NULL));    append(&todo, new_task(3, "Backup", NULL));  print("Start:", todo);    remove_id(&todo, 2);                         print("Done 2:", todo);    todo = new_task(4, "Server", todo);          print("Urgent:", todo);    while (todo) { Task *next = todo->next; free(todo); todo = next; }  // free all    return 0;}

Output · cc main.c -o main && ./main

Start:    [1 Invoice] [2 Call Ana] [3 Backup]
Done 2:   [1 Invoice] [3 Backup]
Urgent:   [4 Server] [1 Invoice] [3 Backup]

Key points

Each node points to the next; the last one to NULL.
Inserting at the front walks nothing.
Task **link changes the head or any next with no special cases.
When freeing, save next before calling free.

Exercise

Write int count(const Task *t) and Task *find(Task *t, int id), and use the latter to rename task 3 to "Backup NAS".