W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

Linked List

Dynamic data structure with nodes connected through pointers.

What is a Linked List?

Access: O(n) | Search: O(n) | Insert at head: O(1)

Scavenger Hunt Memory Model

Think of a scavenger hunt. The first clue (head) does not tell you where the final treasure (tail) lies. Instead, the first clue only gives you the location of the second clue, which contains the location of the third, and so on. You must visit each location sequentially to reach the end.

A Linked List is a linear data structure where elements are not stored at contiguous (adjacent) memory locations. Instead, each element is stored as a self-contained object called a Node, and nodes are chained together using Pointers (memory addresses).

Key Components of a Node:

Data: The actual payload or value stored in the node.
Next Pointer: A reference link storing the memory address of the next node in the chain.

Essential Features:

Dynamic Size: Can grow or shrink at runtime without requiring re-allocation of the entire structure.
Scattered Memory Allocation: Nodes can be allocated anywhere in the heap memory; they don't need a single contiguous block like arrays.
No Random Access: To read index i, you must traverse step-by-step from the head (O(n) access cost).

C++ Code — What is a Linked List?

#include <iostream>
using namespace std;

// Define the Node structure
struct Node {
    int data;      // Data part
    Node* next;    // Pointer to next node
    
    // Constructor for easy node creation
    Node(int value) {
        data = value;
        next = nullptr;  // NULL in older C++
    }
};

int main() {
    // Create nodes
    Node* head = new Node(10);      // First node
    Node* second = new Node(20);    // Second node
    Node* third = new Node(30);     // Third node
    
    // Link the nodes
    head->next = second;
    second->next = third;
    // third->next is already nullptr
    
    // Traverse and print
    cout << "Linked List: ";
    Node* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
    // Output: 10 -> 20 -> 30 -> NULL
    
    return 0;
}

Types of Linked Lists

Doubly: Insert/Delete O(1) if node given | Access O(n)

Structural Variations

Depending on how nodes reference each other, linked lists are classified into four variations:

1. Singly Linked Lists

Each node stores exactly one pointer referencing the next node.
Traversals can only proceed forward in one direction.
The final node's next pointer points to nullptr to mark the end.

2. Doubly Linked Lists

Each node stores two pointers: next and prev (previous).
Allows bidirectional traversal (forward and backward).
Requires more memory (extra pointer per node) but makes deletion of a given node O(1) because you have instant access to its predecessor.

3. Circular Linked Lists

The final node points back to the first node instead of pointing to nullptr.
Application: Round-robin process scheduling in Operating Systems, circular buffers.

4. Circular Doubly Linked Lists

A combination of doubly linked and circular. The head's previous pointer references the tail, and the tail's next pointer references the head.

C++ Code — Types of Linked Lists

#include <iostream>
using namespace std;

// Singly Linked List Node
struct SinglyNode {
    int data;
    SinglyNode* next;
    
    SinglyNode(int val) : data(val), next(nullptr) {}
};

// Doubly Linked List Node
struct DoublyNode {
    int data;
    DoublyNode* next;
    DoublyNode* prev;
    
    DoublyNode(int val) : data(val), next(nullptr), prev(nullptr) {}
};

int main() {
    // Doubly Linked List Example
    DoublyNode* head = new DoublyNode(10);
    DoublyNode* second = new DoublyNode(20);
    DoublyNode* third = new DoublyNode(30);
    
    // Link forward
    head->next = second;
    second->next = third;
    
    // Link backward
    second->prev = head;
    third->prev = second;
    
    // Forward traversal
    cout << "Forward: ";
    DoublyNode* temp = head;
    while (temp != nullptr) {
        cout << temp->data << " <-> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
    
    // Backward traversal
    cout << "Backward: ";
    temp = third;
    while (temp != nullptr) {
        cout << temp->data << " <-> ";
        temp = temp->prev;
    }
    cout << "NULL" << endl;
    
    return 0;
}

Insertion Operations

At Head: O(1) | At Tail: O(n) | At Position: O(n)

Modifying the Links

Inserting elements into a linked list requires rearranging pointer addresses. Unlike arrays, you never have to shift elements:

1. Insert at Beginning (Head) (`O(1)` Time)

Create a new node.
Point the new node's next pointer to the current head node.
Update the head pointer of the list to point to your new node.

2. Insert at End (Tail) (`O(n)` Time, or `O(1)` with Tail Pointer)

Create a new node.
If no tail pointer is stored, traverse from the head to locate the last node.
Point the last node's next reference to the new node.

3. Insert at Specific Position (`O(n)` Time)

Traverse to the node just before the target insertion index (position pos - 1).
Point the new node's next reference to the predecessor's next node.
Point the predecessor's next reference to the new node.

C++ Code — Insertion Operations

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;
    
    LinkedList() : head(nullptr) {}
    
    // Insert at beginning - O(1)
    void insertAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }
    
    // Insert at end - O(n)
    void insertAtTail(int val) {
        Node* newNode = new Node(val);
        
        if (head == nullptr) {
            head = newNode;
            return;
        }
        
        Node* temp = head;
        while (temp->next != nullptr) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
    
    // Insert at position (1-indexed) - O(n)
    void insertAtPosition(int val, int pos) {
        if (pos == 1) {
            insertAtHead(val);
            return;
        }
        
        Node* newNode = new Node(val);
        Node* temp = head;
        
        for (int i = 1; i < pos - 1 && temp != nullptr; i++) {
            temp = temp->next;
        }
        
        if (temp == nullptr) return;  // Invalid position
        
        newNode->next = temp->next;
        temp->next = newNode;
    }
    
    void display() {
        Node* temp = head;
        while (temp != nullptr) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }
};

int main() {
    LinkedList list;
    
    list.insertAtHead(30);
    list.insertAtHead(20);
    list.insertAtHead(10);
    cout << "After inserting at head: ";
    list.display();  // 10 -> 20 -> 30 -> NULL
    
    list.insertAtTail(40);
    cout << "After inserting at tail: ";
    list.display();  // 10 -> 20 -> 30 -> 40 -> NULL
    
    list.insertAtPosition(25, 3);
    cout << "After inserting 25 at position 3: ";
    list.display();  // 10 -> 20 -> 25 -> 30 -> 40 -> NULL
    
    return 0;
}

Deletion Operations

From Head: O(1) | From Tail: O(n) | By Value: O(n)

Disconnecting and Freeing Nodes

To delete a node, you must bypass it in the chain and manually clean up heap allocations to avoid memory leaks:

1. Delete from Beginning (`O(1)` Time)

Create a temporary pointer pointing to the current head.
Move the head pointer forward to the next node (head = head->next).
Manually free the memory of the temporary node using the delete keyword.

2. Delete from End (`O(n)` Time)

Traverse to the second-to-last node.
Delete the node that follows it (the tail).
Set the second-to-last node's next pointer to nullptr to mark it as the new end.

3. Delete by Value (`O(n)` Time)

Find the node preceding the target value node.
Bypass the target node: point the predecessor's next pointer directly to the target's next node.
Delete the isolated target node to free up RAM.

C++ Code — Deletion Operations

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;
    
    LinkedList() : head(nullptr) {}
    
    void insertAtTail(int val) {
        Node* newNode = new Node(val);
        if (head == nullptr) { head = newNode; return; }
        Node* temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
    }
    
    // Delete from beginning - O(1)
    void deleteFromHead() {
        if (head == nullptr) return;
        
        Node* temp = head;
        head = head->next;
        delete temp;  // Free memory!
    }
    
    // Delete from end - O(n)
    void deleteFromTail() {
        if (head == nullptr) return;
        
        if (head->next == nullptr) {
            delete head;
            head = nullptr;
            return;
        }
        
        Node* temp = head;
        while (temp->next->next != nullptr) {
            temp = temp->next;
        }
        delete temp->next;
        temp->next = nullptr;
    }
    
    // Delete by value - O(n)
    void deleteValue(int val) {
        if (head == nullptr) return;
        
        // If head has the value
        if (head->data == val) {
            deleteFromHead();
            return;
        }
        
        Node* temp = head;
        while (temp->next != nullptr && temp->next->data != val) {
            temp = temp->next;
        }
        
        if (temp->next == nullptr) return;  // Value not found
        
        Node* toDelete = temp->next;
        temp->next = temp->next->next;
        delete toDelete;
    }
    
    void display() {
        Node* temp = head;
        while (temp) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }
};

int main() {
    LinkedList list;
    for (int i = 1; i <= 5; i++) list.insertAtTail(i * 10);
    
    cout << "Original: ";
    list.display();  // 10 -> 20 -> 30 -> 40 -> 50 -> NULL
    
    list.deleteFromHead();
    cout << "After delete head: ";
    list.display();  // 20 -> 30 -> 40 -> 50 -> NULL
    
    list.deleteFromTail();
    cout << "After delete tail: ";
    list.display();  // 20 -> 30 -> 40 -> NULL
    
    list.deleteValue(30);
    cout << "After delete 30: ";
    list.display();  // 20 -> 40 -> NULL
    
    return 0;
}

Reversing a Linked List

Iterative: O(n) time, O(1) space | Recursive: O(n) time, O(n) space

Pointer Redirection

Reversing a linked list in-place is a classic technical interview problem. It tests your pointer manipulation skills without allocating extra space.

Iterative Reversal (`O(n)` Time, `O(1)` Space)

We maintain three pointers to slide along the chain, reversing links behind us:

prev (initialized to nullptr)
curr (initialized to head)
next (initialized to nullptr)

At each node, we execute:

Save the next node: next = curr->next
Reverse the current node's pointer: curr->next = prev
Move the pointers forward: prev = curr, curr = next
Once finished, update head = prev.

Recursive Reversal (`O(n)` Time, `O(n)` Call Stack Space)

Recursively reverse the sublist starting from the second node, then point the second node's next pointer back to the current node and clear the current node's next pointer.

C++ Code — Reversing a Linked List

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedList {
public:
    Node* head;
    
    LinkedList() : head(nullptr) {}
    
    void insertAtTail(int val) {
        Node* newNode = new Node(val);
        if (!head) { head = newNode; return; }
        Node* temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
    }
    
    // Iterative Reverse - O(n) time, O(1) space
    void reverseIterative() {
        Node* prev = nullptr;
        Node* curr = head;
        Node* next = nullptr;
        
        while (curr != nullptr) {
            next = curr->next;   // Save next
            curr->next = prev;   // Reverse pointer
            prev = curr;         // Move prev forward
            curr = next;         // Move curr forward
        }
        head = prev;
    }
    
    // Recursive Reverse - O(n) time, O(n) space (call stack)
    Node* reverseRecursive(Node* node) {
        // Base case: empty or single node
        if (node == nullptr || node->next == nullptr) {
            return node;
        }
        
        // Reverse the rest of the list
        Node* newHead = reverseRecursive(node->next);
        
        // Make next node point back to current
        node->next->next = node;
        node->next = nullptr;
        
        return newHead;
    }
    
    void reverseUsingRecursion() {
        head = reverseRecursive(head);
    }
    
    void display() {
        Node* temp = head;
        while (temp) {
            cout << temp->data << " -> ";
            temp = temp->next;
        }
        cout << "NULL" << endl;
    }
};

int main() {
    LinkedList list;
    for (int i = 1; i <= 5; i++) {
        list.insertAtTail(i * 10);
    }
    
    cout << "Original: ";
    list.display();  // 10 -> 20 -> 30 -> 40 -> 50 -> NULL
    
    list.reverseIterative();
    cout << "After iterative reverse: ";
    list.display();  // 50 -> 40 -> 30 -> 20 -> 10 -> NULL
    
    list.reverseUsingRecursion();
    cout << "After recursive reverse: ";
    list.display();  // 10 -> 20 -> 30 -> 40 -> 50 -> NULL
    
    return 0;
}

Common Interview Problems

Cycle Detection: O(n) | Find Middle: O(n) | Merge: O(n+m)

Standard Interview Patterns

These algorithms are highly valued for testing pointer control and optimal space usage:

1. Cycle Detection (Floyd's Tortoise and Hare) (`O(n)` Time, `O(1)` Space)

Use two pointers: a slow pointer (moves 1 step) and a fast pointer (moves 2 steps). If a cycle exists, the fast pointer will eventually overlap and meet the slow pointer inside the loop.

2. Find Middle Element (`O(n)` Time, `O(1)` Space)

Use two pointers. Advance the fast pointer by 2 steps for every 1 step the slow pointer moves. When the fast pointer reaches the end of the list, the slow pointer will be pointing exactly at the middle element.

3. Merge Two Sorted Lists (`O(n + m)` Time)

Use a dummy node to build a new list. Compare the head elements of both lists, attach the smaller node to the merged list's tail, and advance that list's pointer. Repeat until one list is exhausted, then append the remaining items.

C++ Code — Common Interview Problems

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

// Detect Cycle - Floyd's Cycle Detection
bool hasCycle(Node* head) {
    if (!head || !head->next) return false;
    
    Node* slow = head;
    Node* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;         // Move 1 step
        fast = fast->next->next;   // Move 2 steps
        
        if (slow == fast) return true;  // Cycle detected!
    }
    return false;
}

// Find Middle Element
Node* findMiddle(Node* head) {
    if (!head) return nullptr;
    
    Node* slow = head;
    Node* fast = head;
    
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;  // slow is at middle
}

// Merge Two Sorted Lists
Node* mergeSorted(Node* l1, Node* l2) {
    Node dummy(0);
    Node* tail = &dummy;
    
    while (l1 && l2) {
        if (l1->data <= l2->data) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    tail->next = l1 ? l1 : l2;  // Attach remaining
    return dummy.next;
}

int main() {
    // Create list: 1 -> 2 -> 3 -> 4 -> 5
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    
    // Find middle
    Node* mid = findMiddle(head);
    cout << "Middle element: " << mid->data << endl;  // Output: 3
    
    // Check cycle
    cout << "Has cycle: " << (hasCycle(head) ? "Yes" : "No") << endl;  // No
    
    // Create cycle for testing
    // head->next->next->next->next->next = head->next;
    // cout << "Has cycle: " << (hasCycle(head) ? "Yes" : "No") << endl;  // Yes
    
    return 0;
}

#include <iostream> using namespace std; // Define the Node structure struct Node { int data; // Data part Node* next; // Pointer to next node // Constructor for easy node creation Node(int value) { data = value; next = nullptr; // NULL in older C++ } }; int main() { // Create nodes Node* head = new Node(10); // First node Node* second = new Node(20); // Second node Node* third = new Node(30); // Third node // Link the nodes head->next = second; second->next = third; // third->next is already nullptr // Traverse and print cout << "Linked List: "; Node* temp = head; while (temp != nullptr) { cout << temp->data << " -> "; temp = temp->next; } cout << "NULL" << endl; // Output: 10 -> 20 -> 30 -> NULL return 0; }

#include <iostream> using namespace std; // Singly Linked List Node struct SinglyNode { int data; SinglyNode* next; SinglyNode(int val) : data(val), next(nullptr) {} }; // Doubly Linked List Node struct DoublyNode { int data; DoublyNode* next; DoublyNode* prev; DoublyNode(int val) : data(val), next(nullptr), prev(nullptr) {} }; int main() { // Doubly Linked List Example DoublyNode* head = new DoublyNode(10); DoublyNode* second = new DoublyNode(20); DoublyNode* third = new DoublyNode(30); // Link forward head->next = second; second->next = third; // Link backward second->prev = head; third->prev = second; // Forward traversal cout << "Forward: "; DoublyNode* temp = head; while (temp != nullptr) { cout << temp->data << " <-> "; temp = temp->next; } cout << "NULL" << endl; // Backward traversal cout << "Backward: "; temp = third; while (temp != nullptr) { cout << temp->data << " <-> "; temp = temp->prev; } cout << "NULL" << endl; return 0; }

#include <iostream> using namespace std; struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; class LinkedList { public: Node* head; LinkedList() : head(nullptr) {} // Insert at beginning - O(1) void insertAtHead(int val) { Node* newNode = new Node(val); newNode->next = head; head = newNode; } // Insert at end - O(n) void insertAtTail(int val) { Node* newNode = new Node(val); if (head == nullptr) { head = newNode; return; } Node* temp = head; while (temp->next != nullptr) { temp = temp->next; } temp->next = newNode; } // Insert at position (1-indexed) - O(n) void insertAtPosition(int val, int pos) { if (pos == 1) { insertAtHead(val); return; } Node* newNode = new Node(val); Node* temp = head; for (int i = 1; i < pos - 1 && temp != nullptr; i++) { temp = temp->next; } if (temp == nullptr) return; // Invalid position newNode->next = temp->next; temp->next = newNode; } void display() { Node* temp = head; while (temp != nullptr) { cout << temp->data << " -> "; temp = temp->next; } cout << "NULL" << endl; } }; int main() { LinkedList list; list.insertAtHead(30); list.insertAtHead(20); list.insertAtHead(10); cout << "After inserting at head: "; list.display(); // 10 -> 20 -> 30 -> NULL list.insertAtTail(40); cout << "After inserting at tail: "; list.display(); // 10 -> 20 -> 30 -> 40 -> NULL list.insertAtPosition(25, 3); cout << "After inserting 25 at position 3: "; list.display(); // 10 -> 20 -> 25 -> 30 -> 40 -> NULL return 0; }

#include <iostream> using namespace std; struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; class LinkedList { public: Node* head; LinkedList() : head(nullptr) {} void insertAtTail(int val) { Node* newNode = new Node(val); if (head == nullptr) { head = newNode; return; } Node* temp = head; while (temp->next) temp = temp->next; temp->next = newNode; } // Delete from beginning - O(1) void deleteFromHead() { if (head == nullptr) return; Node* temp = head; head = head->next; delete temp; // Free memory! } // Delete from end - O(n) void deleteFromTail() { if (head == nullptr) return; if (head->next == nullptr) { delete head; head = nullptr; return; } Node* temp = head; while (temp->next->next != nullptr) { temp = temp->next; } delete temp->next; temp->next = nullptr; } // Delete by value - O(n) void deleteValue(int val) { if (head == nullptr) return; // If head has the value if (head->data == val) { deleteFromHead(); return; } Node* temp = head; while (temp->next != nullptr && temp->next->data != val) { temp = temp->next; } if (temp->next == nullptr) return; // Value not found Node* toDelete = temp->next; temp->next = temp->next->next; delete toDelete; } void display() { Node* temp = head; while (temp) { cout << temp->data << " -> "; temp = temp->next; } cout << "NULL" << endl; } }; int main() { LinkedList list; for (int i = 1; i <= 5; i++) list.insertAtTail(i * 10); cout << "Original: "; list.display(); // 10 -> 20 -> 30 -> 40 -> 50 -> NULL list.deleteFromHead(); cout << "After delete head: "; list.display(); // 20 -> 30 -> 40 -> 50 -> NULL list.deleteFromTail(); cout << "After delete tail: "; list.display(); // 20 -> 30 -> 40 -> NULL list.deleteValue(30); cout << "After delete 30: "; list.display(); // 20 -> 40 -> NULL return 0; }

#include <iostream> using namespace std; struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; class LinkedList { public: Node* head; LinkedList() : head(nullptr) {} void insertAtTail(int val) { Node* newNode = new Node(val); if (!head) { head = newNode; return; } Node* temp = head; while (temp->next) temp = temp->next; temp->next = newNode; } // Iterative Reverse - O(n) time, O(1) space void reverseIterative() { Node* prev = nullptr; Node* curr = head; Node* next = nullptr; while (curr != nullptr) { next = curr->next; // Save next curr->next = prev; // Reverse pointer prev = curr; // Move prev forward curr = next; // Move curr forward } head = prev; } // Recursive Reverse - O(n) time, O(n) space (call stack) Node* reverseRecursive(Node* node) { // Base case: empty or single node if (node == nullptr || node->next == nullptr) { return node; } // Reverse the rest of the list Node* newHead = reverseRecursive(node->next); // Make next node point back to current node->next->next = node; node->next = nullptr; return newHead; } void reverseUsingRecursion() { head = reverseRecursive(head); } void display() { Node* temp = head; while (temp) { cout << temp->data << " -> "; temp = temp->next; } cout << "NULL" << endl; } }; int main() { LinkedList list; for (int i = 1; i <= 5; i++) { list.insertAtTail(i * 10); } cout << "Original: "; list.display(); // 10 -> 20 -> 30 -> 40 -> 50 -> NULL list.reverseIterative(); cout << "After iterative reverse: "; list.display(); // 50 -> 40 -> 30 -> 20 -> 10 -> NULL list.reverseUsingRecursion(); cout << "After recursive reverse: "; list.display(); // 10 -> 20 -> 30 -> 40 -> 50 -> NULL return 0; }

#include <iostream> using namespace std; struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; // Detect Cycle - Floyd's Cycle Detection bool hasCycle(Node* head) { if (!head || !head->next) return false; Node* slow = head; Node* fast = head; while (fast && fast->next) { slow = slow->next; // Move 1 step fast = fast->next->next; // Move 2 steps if (slow == fast) return true; // Cycle detected! } return false; } // Find Middle Element Node* findMiddle(Node* head) { if (!head) return nullptr; Node* slow = head; Node* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; // slow is at middle } // Merge Two Sorted Lists Node* mergeSorted(Node* l1, Node* l2) { Node dummy(0); Node* tail = &dummy; while (l1 && l2) { if (l1->data <= l2->data) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } tail = tail->next; } tail->next = l1 ? l1 : l2; // Attach remaining return dummy.next; } int main() { // Create list: 1 -> 2 -> 3 -> 4 -> 5 Node* head = new Node(1); head->next = new Node(2); head->next->next = new Node(3); head->next->next->next = new Node(4); head->next->next->next->next = new Node(5); // Find middle Node* mid = findMiddle(head); cout << "Middle element: " << mid->data << endl; // Output: 3 // Check cycle cout << "Has cycle: " << (hasCycle(head) ? "Yes" : "No") << endl; // No // Create cycle for testing // head->next->next->next->next->next = head->next; // cout << "Has cycle: " << (hasCycle(head) ? "Yes" : "No") << endl; // Yes return 0; }

Linked List

What is a Linked List?

Scavenger Hunt Memory Model

Key Components of a Node:

Essential Features:

Types of Linked Lists

Structural Variations

1. Singly Linked Lists

2. Doubly Linked Lists

3. Circular Linked Lists

4. Circular Doubly Linked Lists

Insertion Operations

Modifying the Links

1. Insert at Beginning (Head) (O(1) Time)

2. Insert at End (Tail) (O(n) Time, or O(1) with Tail Pointer)

3. Insert at Specific Position (O(n) Time)

Deletion Operations

Disconnecting and Freeing Nodes

1. Delete from Beginning (O(1) Time)

2. Delete from End (O(n) Time)

3. Delete by Value (O(n) Time)

Reversing a Linked List

Pointer Redirection

Iterative Reversal (O(n) Time, O(1) Space)

Recursive Reversal (O(n) Time, O(n) Call Stack Space)

Common Interview Problems

Standard Interview Patterns

1. Cycle Detection (Floyd's Tortoise and Hare) (O(n) Time, O(1) Space)

2. Find Middle Element (O(n) Time, O(1) Space)

3. Merge Two Sorted Lists (O(n + m) Time)

Linked List

What is a Linked List?

Scavenger Hunt Memory Model

Key Components of a Node:

Essential Features:

Types of Linked Lists

Structural Variations

1. Singly Linked Lists

2. Doubly Linked Lists

3. Circular Linked Lists

4. Circular Doubly Linked Lists

Insertion Operations

Modifying the Links

1. Insert at Beginning (Head) (O(1) Time)

2. Insert at End (Tail) (O(n) Time, or O(1) with Tail Pointer)

3. Insert at Specific Position (O(n) Time)

Deletion Operations

Disconnecting and Freeing Nodes

1. Delete from Beginning (O(1) Time)

2. Delete from End (O(n) Time)

3. Delete by Value (O(n) Time)

Reversing a Linked List

Pointer Redirection

Iterative Reversal (O(n) Time, O(1) Space)

Recursive Reversal (O(n) Time, O(n) Call Stack Space)

Common Interview Problems

Standard Interview Patterns

1. Cycle Detection (Floyd's Tortoise and Hare) (O(n) Time, O(1) Space)

2. Find Middle Element (O(n) Time, O(1) Space)

3. Merge Two Sorted Lists (O(n + m) Time)

1. Insert at Beginning (Head) (`O(1)` Time)

2. Insert at End (Tail) (`O(n)` Time, or `O(1)` with Tail Pointer)

3. Insert at Specific Position (`O(n)` Time)

1. Delete from Beginning (`O(1)` Time)

2. Delete from End (`O(n)` Time)

3. Delete by Value (`O(n)` Time)

Iterative Reversal (`O(n)` Time, `O(1)` Space)

Recursive Reversal (`O(n)` Time, `O(n)` Call Stack Space)

1. Cycle Detection (Floyd's Tortoise and Hare) (`O(n)` Time, `O(1)` Space)

2. Find Middle Element (`O(n)` Time, `O(1)` Space)

3. Merge Two Sorted Lists (`O(n + m)` Time)

1. Insert at Beginning (Head) (`O(1)` Time)

2. Insert at End (Tail) (`O(n)` Time, or `O(1)` with Tail Pointer)

3. Insert at Specific Position (`O(n)` Time)

1. Delete from Beginning (`O(1)` Time)

2. Delete from End (`O(n)` Time)

3. Delete by Value (`O(n)` Time)

Iterative Reversal (`O(n)` Time, `O(1)` Space)

Recursive Reversal (`O(n)` Time, `O(n)` Call Stack Space)

1. Cycle Detection (Floyd's Tortoise and Hare) (`O(n)` Time, `O(1)` Space)

2. Find Middle Element (`O(n)` Time, `O(1)` Space)

3. Merge Two Sorted Lists (`O(n + m)` Time)