Singly Linked Lists

A linked list is a chain of separately allocated nodes, each pointing to the next one. Unlike an array, a linked list does not need a contiguous block of memory and can grow or shrink one node at a time, which makes insertion and deletion in the middle of the sequence cheap compared to shifting array elements. A singly linked list is the simplest form: each node stores its data and a single pointer to the next node.

The Node Structure

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

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

Note the use of struct Node inside its own definition — a node needs to refer to "another node like me," which is only possible through a pointer, since a struct cannot directly contain an instance of itself (that would require infinite memory).

Creating a Node

Node *create_node(int value) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(EXIT_FAILURE);
    }
    node->data = value;
    node->next = NULL;
    return node;
}

Inserting at the Head

Inserting a new node at the front of the list is an O(1) operation: point the new node's next at the current head, then make the new node the head.

void push_front(Node **head, int value) {
    Node *node = create_node(value);
    node->next = *head;
    *head = node;
}

Note

The function takes Node **head (a pointer to the head pointer) so it can modify the caller's head variable directly. If it took a plain Node *head, changes to the local copy of the pointer would not be visible to the caller.

Inserting at the Tail

Appending to the end requires walking the list until you find the last node (the one whose next is NULL), which makes it an O(n) operation unless you keep a separate tail pointer.

void push_back(Node **head, int value) {
    Node *node = create_node(value);

    if (*head == NULL) {
        *head = node;
        return;
    }

    Node *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = node;
}

Traversing and Printing

void print_list(const Node *head) {
    const Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

Deleting a Node

Deletion is where singly linked lists are easiest to get wrong. You must find the node to remove AND keep track of the node before it, so you can re-link the previous node's next pointer around the one being removed — otherwise you either leak memory or sever the rest of the list.

void delete_value(Node **head, int value) {
    Node *current = *head;
    Node *previous = NULL;

    while (current != NULL && current->data != value) {
        previous = current;
        current = current->next;
    }

    if (current == NULL) {
        return; /* value not found */
    }

    if (previous == NULL) {
        *head = current->next; /* removing the head node */
    } else {
        previous->next = current->next; /* bridge over the removed node */
    }

    free(current);
}

Warning

Two mistakes are extremely common here. First, freeing a node before saving its next pointer elsewhere loses the rest of the list forever (a memory leak, since nothing points to those later nodes anymore). Second, forgetting to re-link the previous node's next pointer leaves a dangling pointer into freed memory. Always re-link first (or save next in a temporary), then free.

Freeing the Whole List

Since every node was individually malloc'd, you must individually free every node, walking the list and saving the next pointer before freeing the current one:

void free_list(Node *head) {
    Node *current = head;
    while (current != NULL) {
        Node *next = current->next;
        free(current);
        current = next;
    }
}

Full Compilable Example

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

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

Node *create_node(int value) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        fprintf(stderr, "Out of memory\n");
        exit(EXIT_FAILURE);
    }
    node->data = value;
    node->next = NULL;
    return node;
}

void push_front(Node **head, int value) {
    Node *node = create_node(value);
    node->next = *head;
    *head = node;
}

void push_back(Node **head, int value) {
    Node *node = create_node(value);
    if (*head == NULL) {
        *head = node;
        return;
    }
    Node *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = node;
}

void delete_value(Node **head, int value) {
    Node *current = *head;
    Node *previous = NULL;

    while (current != NULL && current->data != value) {
        previous = current;
        current = current->next;
    }
    if (current == NULL) return;

    if (previous == NULL) {
        *head = current->next;
    } else {
        previous->next = current->next;
    }
    free(current);
}

void print_list(const Node *head) {
    const Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

void free_list(Node *head) {
    Node *current = head;
    while (current != NULL) {
        Node *next = current->next;
        free(current);
        current = next;
    }
}

int main(void) {
    Node *head = NULL;

    push_back(&head, 10);
    push_back(&head, 20);
    push_front(&head, 5);
    push_back(&head, 30);

    print_list(head); /* 5 -> 10 -> 20 -> 30 -> NULL */

    delete_value(&head, 20);
    print_list(head); /* 5 -> 10 -> 30 -> NULL */

    free_list(head);
    return 0;
}

Example

Bash

$ ./list

5 -> 10 -> 20 -> 30 -> NULL
5 -> 10 -> 30 -> NULL

Time Complexity

Operation	Complexity	Notes
push_front	O(1)	No traversal needed
push_back	O(n)	Must walk to the end unless a tail pointer is kept
search / delete by value	O(n)	Must walk from the head to find the value

Summary

A node holds data and a pointer to the next node.
push_front is O(1); push_back and search are O(n) without a tail pointer.
Deletion must re-link the previous node before freeing the target node.
Every malloc-ed node must eventually be freed to avoid memory leaks.