Lab: Linked list in C

Build a complete singly linked list in C — supporting push_front, push_back, delete, search, and clean deallocation.

A singly linked list is the canonical C data structure: it requires structs, pointers, dynamic allocation, and careful memory management all at once. Building one from scratch is the most effective test of whether you have genuinely internalised the Intermediate tier concepts.

The node struct

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
    int   len;
} List;

The API to implement

void list_init(List *list);
void list_push_front(List *list, int value);
void list_push_back(List *list, int value);
int  list_remove(List *list, int value);  /* removes first occurrence, returns 1 if found */
int  list_contains(const List *list, int value);
void list_print(const List *list);
void list_free(List *list);

Implementation guide

push_front: Create a new node, set its next to the current head, then set head to the new node. O(1).

push_back: Walk to the last node (where node->next == NULL), then append. O(n). Note the edge case: empty list.

list_remove: Keep a pointer to the previous node so you can relink around the removed node. Edge case: removing the head.

list_free: Walk the list, saving cur->next before freeing cur.

Worked solution

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

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
    int   len;
} List;

void list_init(List *list) {
    list->head = NULL;
    list->len = 0;
}

Node *make_node(int value) {
    Node *n = malloc(sizeof(Node));
    if (!n) { perror("malloc"); exit(1); }
    n->data = value;
    n->next = NULL;
    return n;
}

void list_push_front(List *list, int value) {
    Node *n = make_node(value);
    n->next = list->head;
    list->head = n;
    list->len++;
}

void list_push_back(List *list, int value) {
    Node *n = make_node(value);
    if (list->head == NULL) {
        list->head = n;
    } else {
        Node *cur = list->head;
        while (cur->next) { cur = cur->next; }
        cur->next = n;
    }
    list->len++;
}

int list_remove(List *list, int value) {
    Node **prev = &list->head;
    for (Node *cur = list->head; cur != NULL; cur = cur->next) {
        if (cur->data == value) {
            *prev = cur->next;
            free(cur);
            list->len--;
            return 1;
        }
        prev = &cur->next;
    }
    return 0;
}

int list_contains(const List *list, int value) {
    for (Node *cur = list->head; cur != NULL; cur = cur->next) {
        if (cur->data == value) { return 1; }
    }
    return 0;
}

void list_print(const List *list) {
    printf("[");
    for (Node *cur = list->head; cur != NULL; cur = cur->next) {
        printf("%d%s", cur->data, cur->next ? ", " : "");
    }
    printf("] (len=%d)\n", list->len);
}

void list_free(List *list) {
    Node *cur = list->head;
    while (cur) {
        Node *tmp = cur->next;
        free(cur);
        cur = tmp;
    }
    list->head = NULL;
    list->len = 0;
}

int main(void) {
    List list;
    list_init(&list);

    list_push_back(&list, 1);
    list_push_back(&list, 2);
    list_push_back(&list, 3);
    list_push_front(&list, 0);
    list_print(&list); /* [0, 1, 2, 3] (len=4) */

    list_remove(&list, 2);
    list_print(&list); /* [0, 1, 3] (len=3) */

    printf("Contains 1: %d\n", list_contains(&list, 1)); /* 1 */
    printf("Contains 2: %d\n", list_contains(&list, 2)); /* 0 */

    list_free(&list);
    list_print(&list); /* [] (len=0) */

    return 0;
}

Verify with valgrind

gcc -g -O0 linkedlist.c -o linkedlist
valgrind --leak-check=full ./linkedlist

Zero errors, zero leaks required before submitting.

Extension: doubly linked list

Add a prev pointer to each node:

typedef struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
} Node;

Implement list_push_back in O(1) by keeping a tail pointer in the List struct. Implement list_remove in O(1) given a Node * (no need to find the previous node).

What you practised

Singly linked list traversal with a for loop
The Node **prev = &head trick for clean node removal
Memory management: allocating nodes and freeing them in the right order
Defensive programming: checking malloc, protecting the empty-list edge case

The next module is File I/O — reading and writing files with fopen, fclose, text and binary modes, and error handling with errno.

Finished reading? Mark it complete to track your progress.