Memory Layout and the Role of Pointers

A linked list orgnaizes data across dynamically allocated, non-contiguous blocks of heap memory. Its core is the pointer relationship between nodes, not the data itself.

// Nodes are created at independent memory addresses
Node* first = new Node(15);   // address 0x7fa1c0
Node* second = new Node(28);  // address 0x7fa2e0 (not adjacent)
first->next = second;         // The link is established explicitly

In C++ exams, a common question is whether list nodes are stored contiguously. The answer is always non-contiguous, unlike arrays.

Pointer Reassignment Mechanics

Manipulating a linked list boils down to redirecting pointers. Think of the operations as distinct steps that must preserve the existing chain.

// Inserting node 'r' after node 'p'
Node* saved = p->next; // Step 1: retain the original successor
r->next = saved;       // Step 2: link new node to the saved successor
p->next = r;           // Step 3: link predecessor to the new node

A critical detail: p->next = r doesn't move any object; it overwrites the memory address stored in the next member of p.

Building and Managing a Singly Linked List

Node Definition and Pitfalls

// Robust definition with initializer list (recommended)
struct ListNode {
    int value;
    ListNode* successor;
    ListNode(int val) : value(val), successor(nullptr) {}
};

// Verbose alternative
struct ListNodeAlt {
    int value;
    ListNodeAlt* successor;
    ListNodeAlt(int val) {
        value = val;
        successor = nullptr; // Must explicitly initialize
    }
};

Forgetting to initialize successor (or next) leads to a dangling pointer, a common source of undefined behavior.

Insertion Operations

Prepend (Head Insertion)

void addToFront(ListNode*& head_ref, int data) {
    ListNode* fresh = new ListNode(data);
    fresh->successor = head_ref; // New node points to the old head
    head_ref = fresh;            // Head pointer now points to the new node
}

Append (Tail Insertion)

void addToBack(ListNode*& head_ref, int data) {
    ListNode* fresh = new ListNode(data);
    if (head_ref == nullptr) {
        head_ref = fresh;
        return;
    }
    ListNode* cursor = head_ref;
    // Traverse until the last actual node
    while (cursor->successor != nullptr) {
        cursor = cursor->successor;
    }
    cursor->successor = fresh;
}

Using while (cursor != nullptr) would move past the last node, preventing the assignment of fresh.

Deletion with Proper Memory Reclamation

void removeByValue(ListNode*& head_ref, int target) {
    if (head_ref == nullptr) return;

    if (head_ref->value == target) {
        ListNode* to_delete = head_ref;
        head_ref = head_ref->successor;
        delete to_delete; // Match every new with a delete
        return;
    }

    ListNode* cursor = head_ref;
    while (cursor->successor && cursor->successor->value != target) {
        cursor = cursor->successor;
    }

    if (cursor->successor) {
        ListNode* to_delete = cursor->successor;
        cursor->successor = cursor->successor->successor;
        delete to_delete;
    }
}

After delete, the memory is released, but any external pointer holding the old address remains—a classic dangling reference.

Core Algorithmic Techniques

The Dummy Node Pattern

A temporary sentinel node simplifies edge cases by giving every real node a predecessor, including the original head.

ListNode* removeAllByValue(ListNode* head_ref, int target) {
    ListNode placeholder(0); // Dummy, value irrelevant
    placeholder.successor = head_ref;

    ListNode* cursor = &placeholder;
    while (cursor->successor) {
        if (cursor->successor->value == target) {
            ListNode* discard = cursor->successor;
            cursor->successor = cursor->successor->successor;
            delete discard;
        } else {
            cursor = cursor->successor;
        }
    }
    // The real head is placeholder.successor
    return placeholder.successor;
}

Two-Pointer (Fast and Slow) Strategy

// Detecting a cycle
bool hasLoop(ListNode* head) {
    if (!head) return false;
    ListNode* walker = head;
    ListNode* runner = head;
    while (runner && runner->successor) {
        walker = walker->successor;
        runner = runner->successor->successor;
        if (walker == runner) return true;
    }
    return false;
}

// Finding the middle node (upper middle for even length)
ListNode* centerNode(ListNode* head) {
    if (!head) return nullptr;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast->successor && fast->successor->successor) {
        slow = slow->successor;
        fast = fast->successor->successor;
    }
    return slow;
}

The cycle detection works because the fast pointer gains one step on the slow pointer each iteration inside the loop, guaranteeing a meeting if a cycle exists.

Reversing a Linked List (Iterative and Recursive)

Iterative Reversal

ListNode* reverseIterative(ListNode* current) {
    ListNode* previous = nullptr;
    ListNode* next_node;

    while (current) {
        next_node = current->successor; // Save next
        current->successor = previous;  // Flip the link
        previous = current;             // Advance previous
        current = next_node;            // Advance current
    }
    return previous; // This is the new head
}

Recursive Reversal

ListNode* reverseRecursive(ListNode* node) {
    if (!node || !node->successor) return node;

    ListNode* new_root = reverseRecursive(node->successor);
    node->successor->successor = node;
    node->successor = nullptr;
    return new_root;
}

Comparing Arrays and Linked Lists

Characteristic	Array / Vector	Singly Linked List
Memory layout	Contiguous	Scattered (non-contiguous)
Element access	O(1) random access	O(n) sequential scan
Insert/Delete at head	O(n) shift elements	O(1)
Insert/Delete at tail	O(1) amortized	O(n) (unless tail pointer)
Insert/Delete in middle	O(n) shift elements	O(1) if node is known
Memory overhead	Minimal	One pointer per node

Practical Applications and Extended Structures

Implementing a Stack

class ListStack {
    ListNode* apex;
public:
    ListStack() : apex(nullptr) {}
    void push(int item) {
        ListNode* added = new ListNode(item);
        added->successor = apex;
        apex = added;
    }
    int pop() {
        if (!apex) throw std::runtime_error("Empty stack");
        int result = apex->value;
        ListNode* temp = apex;
        apex = apex->successor;
        delete temp;
        return result;
    }
    ~ListStack() { while (apex) pop(); }
};

Implemanting a Queue

class ListQueue {
    ListNode* front_ptr;
    ListNode* back_ptr;
public:
    ListQueue() : front_ptr(nullptr), back_ptr(nullptr) {}
    void enqueue(int item) {
        ListNode* added = new ListNode(item);
        if (!back_ptr) {
            front_ptr = back_ptr = added;
        } else {
            back_ptr->successor = added;
            back_ptr = added;
        }
    }
    int dequeue() {
        if (!front_ptr) throw std::runtime_error("Empty queue");
        int result = front_ptr->value;
        ListNode* temp = front_ptr;
        front_ptr = front_ptr->successor;
        if (!front_ptr) back_ptr = nullptr;
        delete temp;
        return result;
    }
    ~ListQueue() { while (front_ptr) dequeue(); }
};

Training and Exam Preparation

Too master linked lists, begin by drawing diagrams for each operation. Work through the following test cases for any function you write:

1. An empty list (nullptr).
2. A list with exactly one node.
3. A list with two nodes.
4. A multi-node list (both odd and even lengths).

When analyzing complexity, consider the need for traversal. Head insertions and deletions are O(1). Most other operations on a singly linked list, such as appending or searching by index, are O(n).

Practice problems include merging two sorted lists, detecting and locating the start of a cycle, and recursively partitioning a list for merge sort. Consistent practice with pointer redirection builds the mental model necessary for solving more complex data structure problems later.