Linked List Fundamentals

A linked list is a linear data structure where elements are not stored in contiguous memory locations. Instead, each component consists of a data field and a reference pointer that chains to the subsequent element. This architecture contrasts sharply with arrays, which rely on fixed, continuous memory blocks.

Structural Variations

Linked lists can be categorized based on their traversal capabilities:

• Singly Linked: Each node only references the next element, allowing forward traversal.
• Doubly Linked: Nodes maintain two references: one forward and one backward. This enables bidirectional navigation.
• Circular: The final node's pointer loops back to the first node. This structure is particularly useful for modeling cyclic processes like the Josephus problem.

Memory Allocation and Node Definition

Unlike arrays, linked lists dynamically allocate memory across the heap. The operating system's memory manager determines the exact physical addresses, resulting in a scattered layout. Access is purely pointer-driven.

Below is a standard C++ node definition utilizing a constructor for clean initialization:

struct ListNode {
    int data;
    ListNode* link;
    explicit ListNode(int v) : data(v), link(nullptr) {}
};

Insertion and Deletion Mechanics

The primary advantage of linked lists lies in O(1) insertion and deletion when the preceding node's address is known. To remove a target node, the predecessor's pointer simply bypasses it and points to the successor. Memory management differs by language: C++ requires explicit deallocation, while Java and Python utilize garbage collection.

Conversely, locating a specific node requires sequential traversal, resulting in O(n) time compplexity. This makes linked lists ideal for scenarios with frequent modifications but infrequent random access.

LeetCode 203: Eliminating Target Values

Objective: Remove all nodes containing a specified integer value.

Strategy: Direct head removal requires special handling because the root pointer itself changes. A cleaner approach introduces a sentinel (dummy) node preceding the actual head. This unifies the deletion logic for both the head and interior nodes.

class Solution {
public:
    ListNode* eliminateOccurrences(ListNode* root, int target) {
        ListNode* sentinel = new ListNode(0);
        sentinel->link = root;
        ListNode* tracker = sentinel;

        while (tracker->link != nullptr) {
            if (tracker->link->data == target) {
                ListNode* discard = tracker->link;
                tracker->link = tracker->link->link;
                delete discard;
            } else {
                tracker = tracker->link;
            }
        }
        root = sentinel->link;
        delete sentinel;
        return root;
    }
};

LeetCode 707: Implementing a Custom Linked List

Objective: Build a class supporting standard list operations: retrieval, head/tail insertion, indexed insertion, and indexed deletion.

Strategy: Maintain a dummy head to simplify boundary conditions and a counter to track size for O(1) length queries and bounds validation. Iteration always starts from the dummy head.

class CustomLinkedList {
private:
    struct Node {
        int value;
        Node* nextPtr;
        explicit Node(int v) : value(v), nextPtr(nullptr) {}
    };
    Node* dummy;
    int count;

public:
    CustomLinkedList() {
        dummy = new Node(0);
        count = 0;
    }

    int fetchElement(int idx) {
        if (idx < 0 || idx >= count) return -1;
        Node* walker = dummy->nextPtr;
        for (int i = 0; i < idx; ++i) {
            walker = walker->nextPtr;
        }
        return walker->value;
    }

    void prepend(int val) {
        Node* fresh = new Node(val);
        fresh->nextPtr = dummy->nextPtr;
        dummy->nextPtr = fresh;
        ++count;
    }

    void append(int val) {
        Node* fresh = new Node(val);
        Node* walker = dummy;
        while (walker->nextPtr != nullptr) {
            walker = walker->nextPtr;
        }
        walker->nextPtr = fresh;
        ++count;
    }

    void insertAt(int idx, int val) {
        if (idx > count) return;
        if (idx < 0) idx = 0;
        Node* fresh = new Node(val);
        Node* walker = dummy;
        for (int i = 0; i < idx; ++i) {
            walker = walker->nextPtr;
        }
        fresh->nextPtr = walker->nextPtr;
        walker->nextPtr = fresh;
        ++count;
    }

    void removeAt(int idx) {
        if (idx < 0 || idx >= count) return;
        Node* walker = dummy;
        for (int i = 0; i < idx; ++i) {
            walker = walker->nextPtr;
        }
        Node* discard = walker->nextPtr;
        walker->nextPtr = walker->nextPtr->nextPtr;
        delete discard;
        --count;
    }
};

LeetCode 206: Inverting Pointer Direction

Objective: Reverse the sequence of nodes by flipping their forward pointers.

Iterative Approach: Traverse the list while maintaining a reference to the previously visited node. At each step, store the next node, redirect the current node's pointer to the previous one, and advance both pointers.

class Solution {
public:
    ListNode* invertStructure(ListNode* root) {
        ListNode* preceding = nullptr;
        ListNode* current = root;

        while (current != nullptr) {
            ListNode* ahead = current->link;
            current->link = preceding;
            preceding = current;
            current = ahead;
        }
        return preceding;
    }
};

Recursive Approach (Tail Style): Pass the accumulated previous node and current node through recursive calls. The base case occurs when the current node is null, at which point the accumulated pointer becomes the new head.

class Solution {
private:
    ListNode* helper(ListNode* preceding, ListNode* current) {
        if (current == nullptr) return preceding;
        ListNode* ahead = current->link;
        current->link = preceding;
        return helper(current, ahead);
    }
public:
    ListNode* invertStructure(ListNode* root) {
        return helper(nullptr, root);
    }
};

Recursive Approach (Head Style): Recurse to the end of the list first. On the unwinding phase, redirect the next node's pointer back to the current node, and sever the current node's forward link.

class Solution {
public:
    ListNode* invertStructure(ListNode* root) {
        if (root == nullptr || root->link == nullptr) return root;
        ListNode* newHead = invertStructure(root->link);
        root->link->link = root;
        root->link = nullptr;
        return newHead;
    }
};