L3: Introduction to Doubly Linked List | Insertions and Deletions

This comprehensive study note explores the transition from singly linked lists to Doubly Linked Lists (DLL), covering node representations in C++ and Java, array-to-DLL conversion, and the complete spectrum of insertion and deletion operations (head, tail, $K^{\text{th}}$ index, and specified node).

1. Why Do We Need a Doubly Linked List? (The Singly Linked List Limitation)

In a Singly Linked List, each node contains a value (data) and a single directional forward pointer (next) pointing to the subsequent node. The final node points to null.

Core Limitation

• Forward-Only Traversal: If you are standing at an arbitrary node in a singly linked list, you cannot look backward because no previous reference exists.
• Finding the previous node requires restarting your search entirely from the head pointer, resulting in $O(N)$ time complexity for backward steps.

2. Core Mental Model: The Doubly Linked List Analogy

Real-Life Analogy: Web Browser History

Real-Life Analogy: Think of a Web Browser History. When you browse from Page A -> Page B -> Page C, you want the ability to click the Forward button to move ahead, but crucially, you also need the Back button to return to your previous page. A Doubly Linked List provides bidirectional movement natively by maintaining two pointers per node: one pointing forward (next) and one pointing backward (back / prev).

3. Node Class Representation in C++ and Java

To support bidirectional travel, our node structure must be upgraded to hold an additional reference to the previous node.

C++ Struct/Class Representation

class Node {
public:
    int data;
    Node* next;
    Node* back; // Pointer to the previous node

    // Constructor with data, next, and back
    Node(int val1, Node* next1, Node* back1) {
        data = val1;
        next = next1;
        back = back1;
    }

    // Constructor with only data (defaults pointers to nullptr)
    Node(int val1) {
        data = val1;
        next = nullptr;
        back = nullptr;
    }
};

Java Class Representation

class Node {
    int data;
    Node next;
    Node back;

    // Constructor with data, next, and back
    Node(int data1, Node next1, Node back1) {
        this.data = data1;
        this.next = next1;
        this.back = back1;
    }

    // Constructor with only data
    Node(int data1) {
        this.data = data1;
        this.next = null;
        this.back = null;
    }
}

4. Converting an Array into a Doubly Linked List

To convert an array into a DLL:

1. Initialize the head node using the first array element (array[0]). Its back pointer is null.
2. Maintain a previous reference pointer initially pointing to head.
3. Iterate from index 1 to N-1, instantiating new nodes where back points to the current previous node.
4. Update the previous node's next pointer to link to the new node, then shift the previous pointer forward.

C++ Implementation

Node* convertArr2DLL(vector<int>& arr) {
    if (arr.empty()) return nullptr;
    
    // Create head using the first element
    Node* head = new Node(arr[0]);
    Node* prev = head;

    for (int i = 1; i < arr.size(); i++) {
        // Create temp node: next = nullptr, back = prev
        Node* temp = new Node(arr[i], nullptr, prev);
        prev->next = temp; // Link previous node forward
        prev = temp;       // Shift prev forward
    }
    return head;
}

Java Implementation

private static Node convertArr2DLL(int[] arr) {
    if (arr.length == 0) return null;

    Node head = new Node(arr[0]);
    Node prev = head;

    for (int i = 1; i < arr.length; i++) {
        Node temp = new Node(arr[i], null, prev);
        prev.next = temp;
        prev = temp;
    }
    return head;
}

5. Deletion Operations in Doubly Linked List

A. Deleting the Head Node

Edge Cases:

1. Empty List (head == nullptr): Cannot delete; return null.
2. Single Element (head->next == nullptr): Delete the single node and return null.

Standard Steps (Multiple Elements):

1. Preserve the current head in a prev pointer.
2. Advance head = head->next.
3. Disconnect the new head's backward link (head->back = nullptr).
4. Disconnect the old node's forward link (prev->next = nullptr).
5. Free/Delete the old node (in C++).

Node* deleteHead(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        delete head;
        return nullptr;
    }

    Node* prev = head;
    head = head->next;

    head->back = nullptr;
    prev->next = nullptr;

    delete prev;
    return head;
}

B. Deleting the Tail Node

Standard Steps:

1. Traverse to the last node using a tail pointer (while (tail->next != nullptr) tail = tail->next;).
2. Capture the new tail (the node preceding the current tail): Node* newTail = tail->back;.
3. Sever connections: Set newTail->next = nullptr and tail->back = nullptr.
4. Delete the old tail node.

Node* deleteTail(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        delete head;
        return nullptr;
    }

    Node* tail = head;
    while (tail->next != nullptr) {
        tail = tail->next;
    }

    Node* newTail = tail->back;
    newTail->next = nullptr;
    tail->back = nullptr;

    delete tail;
    return head;
}

C. Deleting the $K^{\text{th}}$ Element

Strategy:

1. Traverse the list while keeping a running count until count == K.
2. Evaluate structural edge cases:
   • If $K = 1$, invoke deleteHead().
   • If $K = \text{Length}$, invoke deleteTail().
3. For intermediate nodes, bridge the surrounding pointers:
   • prevNode = KthNode->back
   • frontNode = KthNode->next
   • prevNode->next = frontNode
   • frontNode->back = prevNode
4. Isolate and delete KthNode.

Node* removeKthElement(Node* head, int k) {
    if (head == nullptr) return nullptr;

    int count = 0;
    Node* kNode = head;
    while (kNode != nullptr) {
        count++;
        if (count == k) break;
        kNode = kNode->next;
    }

    // If k exceeds list length
    if (kNode == nullptr) return head;

    Node* prevNode = kNode->back;
    Node* frontNode = kNode->next;

    if (prevNode == nullptr && frontNode == nullptr) {
        delete kNode;
        return nullptr;
    }
    else if (prevNode == nullptr) {
        return deleteHead(head);
    }
    else if (frontNode == nullptr) {
        return deleteTail(head);
    }

    prevNode->next = frontNode;
    frontNode->back = prevNode;

    kNode->next = nullptr;
    kNode->back = nullptr;
    delete kNode;

    return head;
}

D. Deleting a Specified Node (Given Node Reference)

Constraint Note: You are guaranteed that the node provided to you will never be the head node, preventing accidental head pointer corruption without extra handling.

void deleteNode(Node* temp) {
    Node* prevNode = temp->back;
    Node* frontNode = temp->next;

    // If temp is the tail node
    if (frontNode == nullptr) {
        prevNode->next = nullptr;
        temp->back = nullptr;
        delete temp;
        return;
    }

    // Intermediate node bridging
    prevNode->next = frontNode;
    frontNode->back = prevNode;

    temp->next = nullptr;
    temp->back = nullptr;
    delete temp;
}

6. Insertion Operations in Doubly Linked List

A. Inserting Before the Head

1. Create a newNode whose next points to the current head and whose back is nullptr.
2. Update the current head's back pointer to point to newNode.
3. Return newNode as the new head of the list.

Node* insertBeforeHead(Node* head, int val) {
    Node* newHead = new Node(val, head, nullptr);
    if (head != nullptr) {
        head->back = newHead;
    }
    return newHead;
}

B. Inserting Before the Tail

1. Traverse to the final node (tail).
2. If the list has only 1 element, delegate to insertBeforeHead().
3. Identify the node preceding the tail (prev = tail->back).
4. Instantiate newNode with next = tail and back = prev.
5. Update pointers: prev->next = newNode and tail->back = newNode.

Node* insertBeforeTail(Node* head, int val) {
    if (head->next == nullptr) {
        return insertBeforeHead(head, val);
    }

    Node* tail = head;
    while (tail->next != nullptr) {
        tail = tail->next;
    }

    Node* prev = tail->back;
    Node* newNode = new Node(val, tail, prev);
    
    prev->next = newNode;
    tail->back = newNode;

    return head;
}

C. Inserting Before the $K^{\text{th}}$ Element

1. If $K = 1$, insert before head via insertBeforeHead().
2. Traverse to find the $K^{\text{th}}$ node (temp).
3. Extract prev = temp->back.
4. Create newNode with next = temp and back = prev.
5. Re-route surrounding references: prev->next = newNode and temp->back = newNode.

Node* insertBeforeKthElement(Node* head, int k, int val) {
    if (k == 1) {
        return insertBeforeHead(head, val);
    }

    Node* temp = head;
    int count = 0;
    while (temp != nullptr) {
        count++;
        if (count == k) break;
        temp = temp->next;
    }

    if (temp == nullptr) return head; // K out of bounds

    Node* prev = temp->back;
    Node* newNode = new Node(val, temp, prev);

    prev->next = newNode;
    temp->back = newNode;

    return head;
}

D. Inserting Before a Given Node Reference

void insertBeforeNode(Node* node, int val) {
    Node* prev = node->back;
    Node* newNode = new Node(val, node, prev);
    
    prev->next = newNode;
    node->back = newNode;
}

7. Comparative Operations Matrix

8. Summary and Key Takeaways

• Bidirectional Advantage: Doubly Linked Lists support two-way traversal (next and back pointers) at the cost of additional memory overhead per node.
• Head Protection: Operations modifying the beginning of the list (e.g., insertBeforeHead) must return the newly updated head reference.
• Pointer Precision: In doubly linked list pointer manipulations, always update both directions (forward and backward links) simultaneously to prevent broken chains.
• Garbage Collection: In languages like Java, unreferenced nodes are automatically cleaned up by the garbage collector, whereas C++ requires explicit delete calls to prevent memory leaks.
• Real-World Utility: DLL mechanics form the foundational data structure behind browser navigation history caches, LRU Caches, and undo-redo functionality in software editors.