C++ Linked Lists

A linked list is a data structure made of nodes, where each node stores a value and a pointer to the next node. Unlike an array or vector, linked list elements do not have to sit next to each other in memory.

The most common beginner version is a singly linked list. Each node points forward to the next node, and the last node points to nullptr.

Nodes and Links

A node usually contains two parts: the data you want to store, and a pointer named something like next. The list itself keeps a pointer to the first node, often called head.

#include <iostream>

class LinkedList {
private:
    struct Node {
        int value;
        Node* next;
    };

    Node* head;

public:
    LinkedList(void) {
        head = nullptr;
    }

    ~LinkedList(void) {
        clear();
    }

    void append(int value) {
        Node* newNode = new Node{value, nullptr};

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

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

        current->next = newNode;
    }

    bool contains(int value) const {
        Node* current = head;

        while (current != nullptr) {
            if (current->value == value) {
                return true;
            }
            current = current->next;
        }

        return false;
    }

    void print(void) const {
        Node* current = head;

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

        std::cout << std::endl;
    }

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

        while (current != nullptr) {
            Node* nextNode = current->next;
            delete current;
            current = nextNode;
        }

        head = nullptr;
    }
};

int main(void) {
    LinkedList numbers;

    numbers.append(10);
    numbers.append(20);
    numbers.append(30);

    std::cout << "List: ";
    numbers.print();

    std::cout << "Contains 20: " << numbers.contains(20) << std::endl;
    std::cout << "Contains 99: " << numbers.contains(99) << std::endl;

    return 0;
}

Output:

List: 10 -> 20 -> 30
Contains 20: 1
Contains 99: 0

How the Example Works

The Node structure stores one int and one pointer to another Node. The head pointer stores the address of the first node. If head is nullptr, the list is empty.

The append() function creates a new node with new. If the list is empty, that new node becomes the head. Otherwise, the function walks from node to node until it reaches the last node, then stores the new node’s address in the last node’s next pointer.

The contains() and print() functions use traversal. Traversal means starting at head, reading the current node, then moving to current->next until the pointer becomes nullptr.

Why Cleanup Matters

This example allocates each node with new, so each node must later be released with delete. The clear() function saves the next pointer before deleting the current node. That matters because after a node is deleted, you must not read from it again.

The destructor ~LinkedList() calls clear() automatically when the list object is destroyed at the end of main().

Linked Lists vs Vectors

Feature	std::vector	Linked list
Memory layout	Elements are stored next to each other	Nodes can be spread around memory
Index access	Fast access with items[i]	Must traverse from the head
Adding after a known node	May require shifting elements	Can be done by changing pointers
Extra memory	Stores values	Stores values plus pointers

In modern C++, use std::vector for most ordered lists unless you specifically need linked-list behavior. The standard library also provides std::list, but building a small linked list helps you understand pointers and dynamic data structures.

Takeaway: a linked list stores values in nodes connected by pointers, so traversal follows links instead of using indexes.