C Linked Lists

A linked list is a linear data structure in which each element, called a node, stores a value together with a pointer to the next node in the sequence. Unlike an array, whose elements occupy one contiguous block of memory, the nodes of a linked list can live anywhere on the heap and are connected purely through pointers. This gives linked lists a flexibility arrays don’t have: you can insert or remove an element without shifting every other element, and the list can grow or shrink at runtime without ever being resized. Linked lists are also the foundation for many other structures you will build in C, such as stacks, queues, hash table buckets, and graphs, so learning to build and manipulate one with raw pointers and malloc is a core C skill.

Overview / How It Works

Every node has two parts: a data field that holds the value you care about, and a pointer field, usually named next, that stores the address of the following node. The list itself is represented by a single pointer variable, conventionally called head, which points at the first node. The last node’s next field is set to NULL, which is how code knows it has reached the end of the list. An empty list is simply a head that equals NULL.

Each node is allocated individually on the heap with malloc, not declared as a normal variable or array element. This is the key difference from an array: an array is one allocation of n contiguous slots, so reading element i is a single pointer-arithmetic calculation, an O(1) operation, but inserting in the middle means shifting every element after it. A linked list has no contiguous block at all; each node is a separate allocation scattered wherever the heap allocator happens to place it. Reaching the k-th node means starting at head and following next pointers one at a time, an O(n) walk, but once you are positioned at a node, inserting or removing a neighbor is just a couple of pointer reassignments, O(1), with no shifting required.

Operation	Array	Singly Linked List
Access by index	O(1)	O(n)
Insert/delete at front	O(n) (shift)	O(1)
Insert/delete at end	O(1) amortized (dynamic array)	O(n) without a tail pointer
Insert/delete once positioned	O(n) (shift)	O(1)
Extra memory per element	none	one pointer (+ padding)

This trade-off is the whole reason linked lists exist: reach for one when you need frequent insertion and deletion, especially at the front or once you already have a pointer to the location, and prefer arrays when you need fast random access or better cache locality. Because nodes are scattered across the heap, iterating a linked list is also slower in practice than iterating an array of the same size, even though both are described as O(n); this is due to CPU cache misses, since an array’s elements sit next to each other in memory while a list’s nodes do not. Each node also carries the overhead of one extra pointer, 8 bytes on a typical 64-bit system, plus whatever padding the compiler adds for alignment.

The variant described in this lesson is a singly linked list, where each node points only to the next one, so you can only walk forward. A doubly linked list adds a second pointer, prev, so you can walk backward too, at the cost of extra memory and more pointer updates per insert or delete. A circular linked list makes the last node point back to the first instead of to NULL. Once you are comfortable with the singly linked list, those variants are small extensions of the same idea.

Syntax

A linked list node is declared as a struct that contains a pointer to its own type:

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

The parts of this declaration:

• struct Node is the tag name of the structure. It must appear before *next because the struct refers to itself; this is legal in C specifically because next is a pointer, whose size is known at compile time, rather than a nested struct Node value, whose size would not be.
• int data is the payload. It can be any type, or even another struct, depending on what the list needs to store.
• struct Node *next is a pointer to the next node, or NULL if this is the last node.

Many programmers add a typedef so they don’t have to write struct Node everywhere:

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

With the typedef, a pointer to a node can be declared as Node *head; instead of struct Node *head;. The examples below use the plain struct Node form for clarity, but both styles are common in real code.

Examples

Example 1: Building and printing a list by hand

This first example allocates three nodes individually and links them together manually, then walks the list to print every value.

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

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

struct Node *createNode(int value) {
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

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

int main(void) {
    struct Node *head = createNode(10);
    head->next = createNode(20);
    head->next->next = createNode(30);

    printList(head);

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

    return 0;
}

Output:

10 -> 20 -> 30 -> NULL

createNode asks the heap allocator for enough memory to hold one struct Node, fills in its fields, and hands back the address. main chains three of these nodes together by pointing each node’s next field at the following one, and printList starts at head and keeps following next until it hits NULL. Notice the final loop, which frees every node before the program exits; every successful malloc must eventually be matched with a free, and it must happen in this order, saving the next pointer before freeing the current node, or you lose access to the rest of the list.

Example 2: Insert-at-head and insert-at-end helper functions

Manually wiring pointers in main does not scale. Real code wraps insertion in reusable functions that take the current head and return the (possibly new) head.

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

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

struct Node *insertAtHead(struct Node *head, int value) {
    struct Node *newNode = malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = head;
    return newNode;
}

struct Node *insertAtEnd(struct Node *head, int value) {
    struct Node *newNode = malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        return newNode;
    }

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

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

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

int main(void) {
    struct Node *list = NULL;

    list = insertAtEnd(list, 2);
    list = insertAtEnd(list, 3);
    list = insertAtEnd(list, 4);
    list = insertAtHead(list, 1);

    printf("List: ");
    printList(list);

    freeList(list);
    return 0;
}

Output:

List: 1 2 3 4 

insertAtEnd handles two cases: an empty list, where the new node simply becomes the head, and a non-empty list, where it walks to the last node (the one whose next is NULL) and attaches the new node there. insertAtHead is simpler and O(1) because it never has to walk anything; it just points the new node at the old head and returns the new node as the new head. This is why lists that only ever insert at the front are cheap, while repeatedly inserting at the end of a long list without a tail pointer gets slower as the list grows.

Example 3: Searching for and deleting a node by value

Deleting from the middle of a list requires keeping track of the node before the one you want to remove, so you can reconnect the list around the gap.

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

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

struct Node *insertAtEnd(struct Node *head, int value) {
    struct Node *newNode = malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    if (head == NULL) {
        return newNode;
    }
    struct Node *current = head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
    return head;
}

struct Node *deleteValue(struct Node *head, int value) {
    struct Node *current = head;
    struct Node *previous = NULL;

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

    if (current == NULL) {
        printf("Value %d not found\n", value);
        return head;
    }

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

    free(current);
    return head;
}

void printList(struct Node *head) {
    for (struct Node *c = head; c != NULL; c = c->next) {
        printf("%d ", c->data);
    }
    printf("\n");
}

int main(void) {
    struct Node *list = NULL;
    list = insertAtEnd(list, 5);
    list = insertAtEnd(list, 10);
    list = insertAtEnd(list, 15);
    list = insertAtEnd(list, 20);

    printf("Before: ");
    printList(list);

    list = deleteValue(list, 10);

    printf("After:  ");
    printList(list);

    struct Node *current = list;
    while (current != NULL) {
        struct Node *temp = current;
        current = current->next;
        free(temp);
    }

    return 0;
}

Output:

Before: 5 10 15 20 
After:  5 15 20 

deleteValue walks the list keeping two pointers: current, the node being examined, and previous, the node right before it. If the value is found at the head (previous is still NULL), the function moves head forward. Otherwise it splices the node out by making previous->next skip over current, then frees current. Searching for a value that is not present is handled too: the loop stops when current becomes NULL, and the function reports failure instead of crashing.

How It Works Step by Step (Under the Hood)

Walking through Example 1 line by line shows what is actually happening in memory:

• malloc(sizeof(struct Node)) asks the operating system’s heap allocator for a block of bytes large enough to hold an int and a pointer, and returns the address of that block, or NULL if the request cannot be satisfied.
• That address is stored in the local pointer variable newNode. At this point the memory is uninitialized; the two field assignments that follow (newNode->data = value; and newNode->next = NULL;) write actual values into it.
• When main does head->next = createNode(20);, it is storing the address of the second node inside the next field of the first node. Nothing is copied except that address; the two nodes now simply know about each other through pointers, wherever the allocator actually placed them in memory.
• printList starts a local pointer, current, at head, and repeatedly dereferences it with current->data to print the value, then reassigns current = current->next to hop to the next node. The loop condition current != NULL is what eventually stops the walk, because the last node’s next was explicitly set to NULL when it was created.
• The cleanup loop in main is careful to copy current into temp before calling free(temp), and only advances current using the value it already saved. If you called free(current) and then tried to read current->next afterward, you would be reading memory the allocator considers free to reuse, which is undefined behavior.

Common Mistakes

1. Losing the head pointer

Overwriting head before the old chain has been reattached orphans every node that was reachable through it; that memory can never be freed again and is leaked for the life of the program.

/* Wrong: the node holding 1 becomes unreachable */
struct Node *head = createNode(1);
head = createNode(2);

/* Correct: link the new node to the old head first */
struct Node *head = createNode(1);
struct Node *second = createNode(2);
second->next = head;
head = second;

2. Using a node after freeing it

free returns the memory to the allocator, but the pointer variable still holds the old address. Dereferencing it afterward is a use-after-free, one of the most common sources of crashes and security bugs in C.

/* Wrong: current->data is read after the memory was freed */
free(current);
printf("%d\n", current->data);

/* Correct: save what you need before freeing */
struct Node *temp = current;
current = current->next;
free(temp);

3. Dereferencing without checking for NULL

Chasing two pointers deep, such as current->next->data, crashes with a segmentation fault whenever current->next happens to be NULL, which is exactly the case at the end of every list.

/* Wrong: crashes when current is the last node */
int peek = current->next->data;

/* Correct: check before dereferencing */
int peek = 0;
if (current->next != NULL) {
    peek = current->next->data;
}

Best Practices

• Always initialize an empty list’s head pointer to NULL, and treat NULL as a valid, expected state everywhere you write list code.
• Check the return value of every malloc before dereferencing it; a failed allocation returns NULL, and writing through a NULL pointer crashes the program.
• Free every node you allocate, and free them in traversal order, saving the next pointer before calling free on the current node.
• When a function can change which node is first, such as inserting at the head or deleting the head, have it return the new head and make callers reassign it, as shown in every example above.
• If you frequently append to the end of a long list, keep a separate tail pointer alongside head so appends are O(1) instead of requiring a full traversal.
• Run new list code under a tool like Valgrind or AddressSanitizer while learning; leaks and use-after-free bugs are common and these tools catch them immediately.
• Draw the list on paper as boxes and arrows before writing pointer-reassignment code; most linked list bugs come from updating pointers in the wrong order and losing a reference.

Practice Exercises

• Write a function struct Node *reverseList(struct Node *head) that reverses a singly linked list in place, using only pointer reassignment (no extra array or recursion), and returns the new head.
• Write a function int listLength(struct Node *head) that returns the number of nodes in a list, then use it to build struct Node *insertAtPosition(struct Node *head, int value, int position) that inserts a new node at a given zero-based position.
• Write a function struct Node *findMiddle(struct Node *head) that returns a pointer to the middle node of a list in a single pass, using two pointers that advance at different speeds (a "slow" pointer moving one node at a time and a "fast" pointer moving two).

Summary

• A linked list is a chain of individually heap-allocated nodes, each holding a value and a pointer to the next node, terminated by a NULL pointer.
• A self-referential struct, such as struct Node { int data; struct Node *next; };, is what makes a node able to point to another node of the same type.
• Compared to an array, a linked list trades O(1) random access for O(1) insertion and deletion once you are positioned at a node, at the cost of pointer-chasing overhead and one extra pointer of memory per element.
• Insertion and deletion functions typically take the current head and return the possibly-updated head, since the first node itself can change.
• Every node obtained with malloc must eventually be released with free, saving the next pointer first, and freed pointers should never be dereferenced again.
• Variants like the doubly linked list (a prev pointer added) and the circular linked list (the tail points back to the head) build directly on the singly linked list covered here.