Linked lists

A linked list stores each element in its own block together with a pointer to the next block. Insertion in the middle costs one pointer change and no copying, which is what the dynamic array of lesson 50 cannot do. The price is a pointer per element and a traversal that follows the chain instead of indexing.

Nodes and a list

A node holds a value and a pointer to the next node; the last one points to NULL. The list itself is only the head pointer, which is why an empty list is a null pointer and why the head changes when an element is inserted at the front. Each node is allocated separately and must be freed separately.

#include <stdio.h> #include <stdlib.h> struct Node { int value; struct Node *next; }; static struct Node *push_front(struct Node *head, int value) { struct Node *node = malloc(sizeof *node); if (node == NULL) { return head; } node->value = value; node->next = head; return node; } static void print(const struct Node *head) { for (const struct Node *node = head; node != NULL; node = node->next) { printf("%d ", node->value); } printf("\n"); } static void free_list(struct Node *head) { while (head != NULL) { struct Node *next = head->next; free(head); head = next; } } int main(void) { struct Node *head = NULL; head = push_front(head, 3); head = push_front(head, 2); head = push_front(head, 1); print(head); free_list(head); return 0; }

gcc -Wall -Wextra node.c -o node
./node

1 2 3

Each push puts the new value at the front, so the printed order is the reverse of the insertion order. free_list saves next before freeing the node, which is the safe order the last section comes back to.

Walking the list

Every operation on a list is a walk from the head. Counting is a loop that follows next until it reaches NULL. The nodes in this example are automatic variables linked on the stack, which shows that a node does not have to be allocated to be a node.

#include <stdio.h> #include <stdlib.h> struct Node { int value; struct Node *next; }; static int length(const struct Node *head) { int count = 0; while (head != NULL) { count++; head = head->next; } return count; } int main(void) { struct Node third = {3, NULL}; struct Node second = {2, &third}; struct Node first = {1, &second}; printf("length: %d\n", length(&first)); return 0; }

gcc -Wall -Wextra length.c -o length
./length

length: 3

The count is the number of iterations, and an empty list returns zero without entering the loop. A list has no random access: reaching element n costs n steps, which is why a dynamic array is better when the code indexes often.

Sorted insertion

Inserting in order needs the node before the new one, so the walk stops at the first successor that is greater. The three cases are an empty list, a value smaller than the head, and a value in the middle. The head is returned because the first case changes it.

#include <stdio.h> #include <stdlib.h> struct Node { int value; struct Node *next; }; static struct Node *insert_sorted(struct Node *head, int value) { struct Node *node = malloc(sizeof *node); if (node == NULL) { return head; } node->value = value; if (head == NULL || value < head->value) { node->next = head; return node; } struct Node *current = head; while (current->next != NULL && current->next->value < value) { current = current->next; } node->next = current->next; current->next = node; return head; } int main(void) { struct Node *head = NULL; head = insert_sorted(head, 5); head = insert_sorted(head, 1); head = insert_sorted(head, 3); head = insert_sorted(head, 2); for (struct Node *node = head; node != NULL; node = node->next) { printf("%d ", node->value); } printf("\n"); while (head != NULL) { struct Node *next = head->next; free(head); head = next; } return 0; }

gcc -Wall -Wextra sorted.c -o sorted
./sorted

1 2 3 5

The condition current->next->value < value keeps equal values after the existing ones, so the insertion is stable. The new node is linked before the loop variable is changed, and the head is returned unchanged for every case except the first.

Deleting a node

Deleting needs the link that points at the victim, not the victim itself: the link is overwritten with the victim's next. Using a pointer to the link, starting with the head, removes the special case for the first node. The function below removes the first match and frees it.

#include <stdio.h> #include <stdlib.h> struct Node { int value; struct Node *next; }; static struct Node *push_front(struct Node *head, int value) { struct Node *node = malloc(sizeof *node); if (node == NULL) { return head; } node->value = value; node->next = head; return node; } static struct Node *remove_value(struct Node *head, int value) { struct Node **link = &head; while (*link != NULL) { if ((*link)->value == value) { struct Node *dead = *link; *link = dead->next; free(dead); return head; } link = &(*link)->next; } return head; } int main(void) { struct Node *head = NULL; head = push_front(head, 3); head = push_front(head, 2); head = push_front(head, 1); head = remove_value(head, 2); for (struct Node *node = head; node != NULL; node = node->next) { printf("%d ", node->value); } printf("\n"); while (head != NULL) { struct Node *next = head->next; free(head); head = next; } return 0; }

gcc -Wall -Wextra delete.c -o delete
./delete

1 3

link starts as the address of the head variable, so the first node is removed by the same code as any other. The pointer to the link has type struct Node **, and *link is the node that the previous element points at.

Freeing while walking

The free loop must read the next pointer before it frees the node. Reading it afterwards uses a block that no longer belongs to the program. GCC warns about the pattern, and AddressSanitizer reports the actual read:

#include <stdio.h> #include <stdlib.h> struct Node { int value; struct Node *next; }; int main(void) { struct Node *first = malloc(sizeof *first); struct Node *second = malloc(sizeof *second); if (first == NULL || second == NULL) { return 1; } first->value = 1; first->next = second; second->value = 2; second->next = NULL; struct Node *node = first; while (node != NULL) { free(node); node = node->next; } return 0; }

gcc -fsanitize=address -g -Wall -Wextra uaf.c -o uaf
./uaf 2>&1 | head -n 5

uaf.c: In function 'main':
uaf.c:25:14: warning: pointer 'node' used after 'free' [-Wuse-after-free]
25 | node = node->next;
uaf.c:24:9: note: call to 'free' here
24 | free(node);
24 | ^~~~~~~~~~~
=================================================================
==842==ERROR: AddressSanitizer: heap-use-after-free on address 0x75acf8040018 at pc 0x5cf1fdf21330 bp 0x7fff674e46d0 sp 0x7ffc8ce02e90

The warning and the sanitizer agree: the read happens after the free. The fix is one line earlier, saving node->next in a local as free_list did in the first section. Pointers and their addresses vary per run; the line numbers and the type of error do not.

Exercises

  1. Add a push_back function that walks to the end and appends a node, and print the list from head to tail.
  2. Write a function that reverses the list in place by changing the pointers and returns the new head.
  3. Count the nodes of a list that contains a cycle and stop after a fixed number of steps instead of looping forever.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does the last node of a singly linked list point to?

    Answer

    NULL, which marks the end of the chain

    The chain ends at a null pointer, and every walk stops when the current node becomes NULL.

  2. Why does insert_sorted return the head pointer?

    Answer

    A new smallest value changes the head

    When the value belongs before the current head, the new node becomes the head, so the caller stores the returned pointer.

  3. How does deletion avoid a special case for the first node?

    Answer

    It keeps a pointer to the link that points at the node

    A struct Node **link starts at the head variable, so overwriting *link removes the first node like any other.

  4. Why save node->next before free(node) in a walk?

    Answer

    The next pointer lives in the freed block

    Reading node->next after the free touches released memory, so the next address is copied into a local first.

  5. What does this program print? #include <stdio.h> #include <stdlib.h> struct Node{int v;struct Node*n;}; static struct Node*push(struct Node*h,int v){struct Node*x=malloc(sizeof*x);x->v=v;x->n=h;return x;} int main(void){struct Node*h=NULL;h=push(h,3);h=push(h,2);h=push(h,1);for(struct Node*x=h;x;x=x->n)printf("%d ",x->v);printf("\n");return 0;}

    Answer

    1 2 3

    Each new value becomes the head, so the last inserted value, 1, is printed first.

  6. What does this program print? #include <stdio.h> struct Node{int v;struct Node*n;}; static int length(const struct Node*h){int c=0;while(h){c++;h=h->n;}return c;} int main(void){struct Node c={3,NULL},b={2,&c},a={1,&b};printf("%d\n",length(&a));return 0;}

    Answer

    3

    The walk follows three links before reaching the null pointer and prints the count.

  7. What does this program print? #include <stdio.h> #include <stdlib.h> struct Node{int v;struct Node*n;}; static struct Node*ins(struct Node*h,int v){struct Node*x=malloc(sizeof*x);x->v=v;if(!h||v<h->v){x->n=h;return x;}struct Node*c=h;while(c->n&&c->n->v<v)c=c->n;x->n=c->n;c->n=x;return h;} int main(void){struct Node*h=NULL;int a[4]={5,1,3,2};for(int i=0;i<4;i++)h=ins(h,a[i]);for(struct Node*x=h;x;x=x->n)printf("%d ",x->v);printf("\n");return 0;}

    Answer

    1 2 3 5

    Each value is inserted between the smaller and larger nodes, so the traversal is ascending.

  8. What does this program print after removing 2 from 1, 2, 3? #include <stdio.h> #include <stdlib.h> struct Node{int v;struct Node*n;}; static struct Node*push(struct Node*h,int v){struct Node*x=malloc(sizeof*x);x->v=v;x->n=h;return x;} static struct Node*del(struct Node*h,int v){struct Node**l=&h;while(*l){if((*l)->v==v){struct Node*d=*l;*l=d->n;free(d);return h;}l=&(*l)->n;}return h;} int main(void){struct Node*h=NULL;h=push(h,3);h=push(h,2);h=push(h,1);h=del(h,2);for(struct Node*x=h;x;x=x->n)printf("%d ",x->v);printf("\n");return 0;}

    Answer

    1 3

    The middle node is unlinked and freed, leaving the first and last values.

  9. What does GCC warn about in a free loop that reads node->next afterwards?

    Answer

    That the pointer is used after free

    -Wuse-after-free points at the read and at the free that invalidated the pointer; the sanitizer reports the same access.

  10. What happens if insert_sorted changes the head but the caller ignores the returned pointer?

    Answer

    The caller keeps the old head and loses the new node

    The head is a value, not a global, so the caller must store the pointer returned by the function.

The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 with the AddressSanitizer runtime on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev

Banner image