Linked lists: nodes, traversal, and C++ implementation

What you should be able to do

• Explain the roles of a node, its data, its next pointer, and the head pointer.
• Trace traversal and insertion without losing the rest of the chain.
• Implement a small singly linked list in C++ and release its allocated nodes.
• Compare the time and memory costs of a linked list with a dynamic array.

1. The problem: a sequence without adjacent storage

An array stores elements in a contiguous region, which makes calculating the address of an indexed element efficient. A linked list represents the same logical sequence differently: each element lives in a node, and each node stores a link to the next node. The nodes do not need to sit next to one another in memory.

For a singly linked list, a node contains two things:

• Data: the value being stored.
• Next: a pointer to the following node, or nullptr when there is no following node.

head
  |
  v
[10 | •] → [20 | •] → [30 | nullptr]
 node 1     node 2     node 3

head is the pointer that gives us access to the first node. If head == nullptr, the list is empty. The final node's next pointer is nullptr, which marks the end.

2. Traversal: why finding an item takes linear time

A linked list has no built-in way to jump directly to position 2. To reach a node, start at head and follow one next link at a time.

Start: current = head       (10)
Step 1: current = current->next  (20)
Step 2: current = current->next  (30)
Stop:  current->next == nullptr

To visit all n nodes, the algorithm follows at most n links, so traversal is O(n). Searching for a value is also O(n) in the worst case. This is the key contrast with array indexing, which is normally O(1).

3. A small C++ implementation

This teaching example uses a singly linked list of integers. Each call to new creates one node. The list owns those nodes, so clear must delete each one exactly once. The example deliberately keeps ownership visible rather than hiding it behind a library container.

#include <iostream>

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

void push_front(Node*& head, int value) {
    Node* node = new Node{value, head};
    head = node;
}

void print_list(const Node* head) {
    for (const Node* current = head; current != nullptr;
         current = current->next) {
        std::cout << current->data << " -> ";
    }
    std::cout << "nullptr\n";
}

void clear(Node*& head) {
    while (head != nullptr) {
        Node* old_head = head;
        head = head->next;
        delete old_head;
    }
}

int main() {
    Node* head = nullptr;       // empty list
    push_front(head, 30);
    push_front(head, 20);
    push_front(head, 10);

    print_list(head);           // 10 -> 20 -> 30 -> nullptr
    clear(head);                // release every allocated node
}

Expected output

10 -> 20 -> 30 -> nullptr

Why the output is in this order: every push_front inserts at the beginning. The first call creates 30; the second places 20 before it; the third places 10 before both. No existing node needs to move.

4. Trace insertion at the head

Suppose the current list is 20 → 30 → nullptr and we want to insert 10 at the front.

1. Create a new node whose data is 10.
2. Set the new node's next to the current head (the node containing 20).
3. Move head to the new node.

Before: head → [20 | •] → [30 | nullptr]

After step 2:
        new  → [10 | •] ─────┐
                             v
        head → [20 | •] → [30 | nullptr]

After step 3:
        head → [10 | •] → [20 | •] → [30 | nullptr]

The order matters. If you overwrite the only pointer to the old first node before connecting the new node to it, you lose access to the remainder of the list. In the implementation, Node{value, head} establishes the link before head = node changes the list's entry point.

5. Operation costs and the array comparison

Assume a singly linked list with a pointer to its head, but no stored tail pointer or stored size. These are worst-case costs unless stated otherwise.

Important qualification: inserting after a known node is O(1), but finding that node may first cost O(n). A list with a tail pointer can append in O(1), but it still does not gain constant-time indexed access.

6. Common bugs and edge cases

• Empty list: check whether head is nullptr before dereferencing it.
• Lost chain: save or connect the next pointer before replacing a pointer that is the only route to the remaining nodes.
• Use after delete: do not read a node after delete has released it.
• Memory leak: every node created with new must eventually be released with delete, or ownership should be managed by an appropriate RAII type.
• Wrong loop condition: stop when the current pointer is nullptr; do not access current->next after current has become null.
• Duplicate values: a value is not a unique node identity. Searching by value finds a matching value, not necessarily a particular node.

7. When should you choose a linked list?

A linked list can be useful when an algorithm frequently inserts or removes elements at positions where it already has node references, and when stable node addresses matter. It is often a poor default for general-purpose sequences: pointer storage, separate allocations, and weaker cache locality can make it slower and more memory-intensive than a vector in real programs.

In modern C++, use standard containers unless you have a reason to implement the structure yourself. std::forward_list provides a standard singly linked list; std::list is doubly linked; std::vector is usually the first sequence container to consider.

8. Check your understanding

1. A list contains 4 → 8 → 12 → nullptr. How many next links must you follow from the head to reach the node containing 12?
2. What should head contain after inserting 5 at the front of an empty list?
3. You already have a pointer to a node in the middle of a singly linked list. What is the time complexity of inserting a new node immediately after it?
4. Why is searching for an item still O(n) even though insertion after a known node is O(1)?

Key takeaways

• A singly linked list is a chain of nodes connected by next pointers.
• Traversal and indexed access are linear; insertion at the head is constant-time.
• Fast insertion assumes the target position is already known.
• Pointer ownership and cleanup are part of a correct implementation, not optional details.
• Choose a linked list for its operation pattern—not because it is automatically faster than an array.

References and further study

• Open Data Structures (C++): Linked Lists — a freely available textbook treatment of list representations and operations.
• cppreference: std::forward_list — standard-library interface and operation details.
• cppreference: std::vector — useful for comparing contiguous sequence storage.