Linked List Structure

A linked list organizes data in a linear sequence using nodes. Each node contains a data element and a pointer to the subsequent node. The initial node is called the head.

Variants of Linked Lists

Singly Linked List

Nodes contain a single pointer to the next node.

Doubly Linked List

Nodes maintain two pointers: one to the next node and another to the previous node. Enables bidirectional traversal.

Circular Linked List

The terminal node conncets back to the head node. Useful for implementing circular buffers or solving Josephus problem variations.

Memory Allocation Characteristics

Unlike arrays, linked lists allocate nodes non-contiguously in memory. Operating system memory managers handle physical distribution. Nodes reference each other through explicit pointer connections.

Node Representation

struct Node {
    int data;
    Node* next_ptr;
    Node(int value) : data(value), next_ptr(nullptr) {}
};

Initialization approaches:

// Constructor-based
Node* start_node = new Node(10);

// Manual assignment
Node* start_node = new Node();
start_node->data = 10;

Core Operations

Deletion

Modify predecessor's pointer to bypass target node. Memory reclamation required in manual management languages.

Insertion

Adjust adjacent node pointers. Constant time complexity O(1) when position is known, though search requires O(n).

Algorithmic Challenges

Value-Based Removal

Eliminate nodes matching specified value using sentinel node technique.

class Solution {
public:
    Node* eliminateValues(Node* list_head, int target) {
        Node sentinel(0);
        sentinel.next_ptr = list_head;
        Node* current = &sentinel;
        
        while (current->next_ptr) {
            if (current->next_ptr->data == target) {
                Node* obsolete = current->next_ptr;
                current->next_ptr = obsolete->next_ptr;
                delete obsolete;
            } else {
                current = current->next_ptr;
            }
        }
        return sentinel.next_ptr;
    }
};

Custom List Implementation

class LinkedListManager {
    Node dummy_head{0};
    int element_count = 0;
    
public:
    int fetchElement(int position) {
        if (position < 0 || position >= element_count) return -1;
        Node* navigator = dummy_head.next_ptr;
        for (int i = 0; i < position; ++i)
            navigator = navigator->next_ptr;
        return navigator->data;
    }
    
    void prependElement(int value) {
        Node* new_node = new Node(value);
        new_node->next_ptr = dummy_head.next_ptr;
        dummy_head.next_ptr = new_node;
        element_count++;
    }
    
    void appendElement(int value) {
        Node* new_node = new Node(value);
        Node* tail_finder = &dummy_head;
        while (tail_finder->next_ptr)
            tail_finder = tail_finder->next_ptr;
        tail_finder->next_ptr = new_node;
        element_count++;
    }
    
    void insertAtPosition(int pos, int value) {
        if (pos > element_count) return;
        if (pos < 0) pos = 0;
        
        Node* new_node = new Node(value);
        Node* locator = &dummy_head;
        for (int i = 0; i < pos; ++i)
            locator = locator->next_ptr;
        
        new_node->next_ptr = locator->next_ptr;
        locator->next_ptr = new_node;
        element_count++;
    }
    
    void removeAtPosition(int pos) {
        if (pos < 0 || pos >= element_count) return;
        
        Node* locator = &dummy_head;
        for (int i = 0; i < pos; ++i)
            locator = locator->next_ptr;
        
        Node* removed = locator->next_ptr;
        locator->next_ptr = removed->next_ptr;
        delete removed;
        element_count--;
    }
};

List Reversal

In-place iterative reversal:

Node* reverseSequence(Node* head) {
    Node* preceding = nullptr;
    Node* current = head;
    
    while (current) {
        Node* successor = current->next_ptr;
        current->next_ptr = preceding;
        preceding = current;
        current = successor;
    }
    return preceding;
}

Adjacent Pair Swapping

Node* exchangePairs(Node* head) {
    Node sentinel(0);
    sentinel.next_ptr = head;
    Node* anchor = &sentinel;
    
    while (anchor->next_ptr && anchor->next_ptr->next_ptr) {
        Node* first = anchor->next_ptr;
        Node* second = first->next_ptr;
        Node* subsequent = second->next_ptr;
        
        anchor->next_ptr = second;
        second->next_ptr = first;
        first->next_ptr = subsequent;
        
        anchor = first;
    }
    return sentinel.next_ptr;
}

Terminal Nth Node Removal

Two-pointer approach:

Node* removeNthFromEnd(Node* head, int n) {
    Node sentinel(0);
    sentinel.next_ptr = head;
    Node* lead = &sentinel;
    Node* follow = &sentinel;
    
    for (int i = 0; i <= n; ++i)
        lead = lead->next_ptr;
    
    while (lead) {
        lead = lead->next_ptr;
        follow = follow->next_ptr;
    }
    
    Node* obsolete = follow->next_ptr;
    follow->next_ptr = obsolete->next_ptr;
    delete obsolete;
    
    return sentinel.next_ptr;
}

Intersection Detection

Length-alignment strategy:

Node* findIntersection(Node* first, Node* second) {
    auto len_a = listLength(first);
    auto len_b = listLength(second);
    
    if (len_a > len_b)
        return traverseForIntersection(first, second, len_a, len_b);
    else
        return traverseForIntersection(second, first, len_b, len_a);
}

int listLength(Node* head) {
    int count = 0;
    while (head) {
        count++;
        head = head->next_ptr;
    }
    return count;
}

Node* traverseForIntersection(Node* longer, Node* shorter, int long_len, int short_len) {
    int advance = long_len - short_len;
    while (advance--) longer = longer->next_ptr;
    
    while (longer && shorter) {
        if (longer == shorter) return longer;
        longer = longer->next_ptr;
        shorter = shorter->next_ptr;
    }
    return nullptr;
}

Cycle Detection and Origin

Floyd's tortoise-hare algorithm:

Node* detectCycleOrigin(Node* head) {
    Node* slow = head;
    Node* fast = head;
    
    while (fast && fast->next_ptr) {
        slow = slow->next_ptr;
        fast = fast->next_ptr->next_ptr;
        
        if (slow == fast) {
            Node* cycle_entry = head;
            while (cycle_entry != slow) {
                cycle_entry = cycle_entry->next_ptr;
                slow = slow->next_ptr;
            }
            return cycle_entry;
        }
    }
    return nullptr;
}