Linked lists

Order lives in the links.

A singly linked list connects nodes using next pointers. The head identifies the first node. Following next reaches later nodes until a null pointer marks the end. Because the links establish order, the nodes do not need to occupy adjacent memory.

Finding a position costs work.

Given only the head, reaching the fifth node means following four links. There is no array-style address calculation from an index. Changing a link at a known position can be constant work, but finding that position can take a linear traversal.

Each next chooses the next node.

The last node is still a valid node even though its next pointer is null. A traversal should process that node and then stop when the current pointer becomes null.

Check the current pointer before following it.

The loop visits 10 and then 20. p != nullptr tests whether there is a current node. Only after that test does the body read its value and the update follow its next link. These nodes are automatic objects and require no manual deletion.

struct Node { int value; Node* next; };
Node last{20, nullptr};
Node first{10, &last};
for (Node* p = &first; p != nullptr; p = p->next) {
    std::cout << p->value << ' ';
}

Unlinking changes reachability, not lifetime.

For A → B → C, assigning A.next = B.next redirects A straight to C. The separate B object still exists. With automatic nodes, its scope controls destruction. With dynamic nodes, an owner must arrange cleanup when the node is no longer needed.

Node c{30, nullptr};
Node b{20, &c};
Node a{10, &b};
a.next = b.next; // a now links to c