Linked lists

How nodes and pointers trade away indexing for cheap insertion at the ends. · 10 min read

A linked list stores each element in its own node. Each node has data plus a pointer to the next node. Unlike an array, nodes are not contiguous in memory — they can live anywhere, stitched together by next pointers. You keep one pointer called head that points to the first node.

A node in C++

struct Node {
    int value;
    Node* next;

    Node(int v) : value(v), next(nullptr) {}
};

This definition says: a node stores an integer and a pointer to another Node. The final node has next == nullptr.

Walking a list

Traversal is pointer-following. Start at head, read the current node, then move to current->next:

void printList(Node* head) {
    Node* current = head;

    while (current != nullptr) {
        cout << current->value << " ";
        current = current->next;
    }
}

The loop stops at nullptr, which marks the end of the chain.

Insert at the head, then delete a value by walking to it and unlinking:

Interactive visualization: Insert at head, then delete a node — step through it frame by frame on this page.

Insert at the head

Head insertion is constant time because it changes only two pointers:

void pushFront(Node*& head, int x) {
    Node* node = new Node(x);  // 1. allocate
    node->next = head;         // 2. new node points to old first node
    head = node;               // 3. head now points to new node
}

Node*& head means a reference to the head pointer. Without the &, the function would receive a copy of the pointer and changing it would not update the caller's head.

Delete a value

Deletion has two cases: deleting the head, or deleting a later node. The important pointer move is: make the previous node skip over the deleted node.

bool removeValue(Node*& head, int x) {
    if (head == nullptr) return false;

    if (head->value == x) {
        Node* doomed = head;
        head = head->next;
        delete doomed;
        return true;
    }

    Node* prev = head;
    Node* cur = head->next;

    while (cur != nullptr && cur->value != x) {
        prev = cur;
        cur = cur->next;
    }

    if (cur == nullptr) return false;

    prev->next = cur->next;  // unlink cur
    delete cur;
    return true;
}

Why access is linear

Linked lists are the backbone of other structures: a stack and a queue can both be built from one, and hash tables chain collisions with them.

Practice: Reverse a Linked List (Easy) — Flip the order of the nodes.

Practice: Remove Nth Node From End (Medium) — Delete the n-th node counting from the tail in one pass.

Practice: Add Two Numbers (Linked Lists) (Hard) — Add two numbers stored as digit lists, least-significant first.