L2. Deletion and Insertion in LL | 8 Problems

These comprehensive study notes cover the deletion and insertion operations in a Singly Linked List across 8 distinct problem varieties. Based on the expert instruction, the guide explores edge cases, memory management (C++ vs. Java), time complexities, and step-by-step logic.

1. Why Do We Need Deletion and Insertion in Linked Lists?

In the previous lecture, we built the mental model of a Singly Linked List: a sequential chain of nodes where each node contains data and a pointer (next) to the next node, terminated by a null pointer.

While static arrays have fixed sizes and require expensive O(N) shifts for insertions and deletions in the middle, linked lists allow dynamic sizing. However, modifying a linked list requires careful pointer manipulation to avoid broken chains or memory leaks.

2. Core Mental Model / Analogy

Real-Life Analogy: The Railway Train Configuration

Think of a Singly Linked List as a railway train:

• The Head is the locomotive engine at the very front. If you want to "delete the head," you must detach the old engine, make the second carriage the new engine, and scrap the old engine.
• The Tail is the caboose at the very back. If you want to "delete the tail," you must walk up to the second-to-last carriage, tell it to sever its connection, and let go of the caboose.
• Insertion is like coupling a new passenger carriage anywhere in the train without having to rebuild the whole train from scratch. You simply reroute the coupling hooks (next pointers).

3. Overview of the 8 Problem Varieties

The lecture solves 8 specific algorithmic variations divided evenly between Deletion and Insertion:

4. Part A: Deletion Operations (Problems 1 to 4)

Problem 1: Deleting the Head of a Linked List

To delete the head, we cannot just drop the reference in languages like C++; we must explicitly free the memory to prevent memory leaks. In Java, the Garbage Collector handles this automatically.

Step-by-Step Flow:

C++ Implementation:

Node* removeHead(Node* head) {
    if (head == nullptr) return nullptr; // Edge Case: Empty list
    Node* temp = head;
    head = head->next;
    delete temp; // C++ manual memory release
    return head;
}

Problem 2: Deleting the Tail of a Linked List

To delete the tail, we must stop at the second-to-last element so we can set its next pointer to null.

Note: If the list is empty (head == nullptr) or has only one element (head->next == nullptr), deleting the tail results in an empty list (return nullptr).

C++ Implementation:

Node* removeTail(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        delete head;
        return nullptr;
    }
    Node* temp = head;
    // Stop at the second-to-last node
    while (temp->next->next != nullptr) {
        temp = temp->next;
    }
    delete temp->next;
    temp->next = nullptr;
    return head;
}

Problem 3: Deleting the $K^{\text{th}}$ Element

This generalizes deletion. We handle edge cases where $K=1$ (head deletion) and traverse up to the position using a counter.

C++ Implementation:

Node* removeKth(Node* head, int k) {
    if (head == nullptr) return nullptr;
    
    // Case 1: Delete Head
    if (k == 1) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return head;
    }

    Node* temp = head;
    Node* prev = nullptr;
    int count = 0;

    while (temp != nullptr) {
        count++;
        if (count == k) {
            prev->next = temp->next;
            delete temp;
            break;
        }
        prev = temp;
        temp = temp->next;
    }
    return head;
}

Problem 4: Deleting a Node by Value

Instead of an index $K$, we look for the first node matching a specific value.

C++ Implementation:

Node* removeElement(Node* head, int val) {
    if (head == nullptr) return nullptr;

    // Case 1: Head itself contains the value
    if (head->data == val) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return head;
    }

    Node* temp = head;
    Node* prev = nullptr;

    while (temp != nullptr) {
        if (temp->data == val) {
            prev->next = temp->next;
            delete temp;
            break;
        }
        prev = temp;
        temp = temp->next;
    }
    return head;
}

5. Part B: Insertion Operations (Problems 5 to 8)

Problem 5: Inserting at the Head

To insert a new node at the beginning, we instantiate a new node whose next pointer references the current head, and then return the new node as the updated head.

C++ Implementation:

Node* insertHead(Node* head, int val) {
    Node* temp = new Node(val, head);
    return temp; // New head
}

Problem 6: Inserting at the Tail

We traverse until temp->next == nullptr (the last node), then create a new node and link the last node's next to it.

Note: If the list is empty (head == nullptr), inserting at the tail is identical to inserting at the head.

C++ Implementation:

Node* insertTail(Node* head, int val) {
    if (head == nullptr) {
        return new Node(val);
    }
    Node* temp = head;
    while (temp->next != nullptr) {
        temp = temp->next;
    }
    Node* newNode = new Node(val);
    temp->next = newNode;
    return head;
}

Problem 7: Inserting at the $K^{\text{th}}$ Position

We traverse the list while maintaining a counter until we reach position $K-1$. We then splice the new node in between temp and temp->next.

Splicing Workflow:

C++ Implementation:

Node* insertAtPosition(Node* head, int val, int k) {
    if (head == nullptr) {
        if (k == 1) return new Node(val);
        return nullptr;
    }

    if (k == 1) {
        return new Node(val, head);
    }

    Node* temp = head;
    int count = 0;

    while (temp != nullptr) {
        count++;
        if (count == k - 1) {
            Node* newNode = new Node(val, temp->next);
            temp->next = newNode;
            break;
        }
        temp = temp->next;
    }
    return head;
}

Problem 8: Inserting Before a Given Value

We traverse the list checking if temp->next->data == val. When we find a match, we insert our new node right before it.

C++ Implementation:

Node* insertBeforeValue(Node* head, int val, int targetVal) {
    if (head == nullptr) return nullptr;

    // Case 1: Insert before Head
    if (head->data == targetVal) {
        return new Node(val, head);
    }

    Node* temp = head;
    while (temp->next != nullptr) {
        if (temp->next->data == targetVal) {
            Node* newNode = new Node(val, temp->next);
            temp->next = newNode;
            break;
        }
        temp = temp->next;
    }
    return head;
}

6. Language Differences: C++ vs. Java Memory Management

7. Complexity Analysis Summary

8. Summary and Key Takeaways

• Always Preserve the Head: Never alter or overwrite your initial head pointer directly during traversal; always copy it into a temporary pointer (Node* temp = head;).
• Check Edge Cases First: Always account for empty lists (head == nullptr) and single-node lists (head->next == nullptr) before writing traversal logic.
• Stop at $K-1$ for Insertions: When inserting at a specific position $K$, your pointer must stop one node short ($K-1$) so you can safely redirect pointers without breaking the chain.
• Stop at Second-to-Last for Tail Deletion: Deleting the tail requires stopping at the node before the tail (temp->next->next == nullptr) to detach and free the final node.
• C++ Memory Hygiene: Remember to call delete on nodes removed in C++ to prevent memory leaks; rely on Java's garbage collector when working in Java.
• Time Complexity Rule of Thumb: Linked list operations scale linearly $O(N)$ relative to the index or position being targeted, unlike arrays which allow $O(1)$ random access.