Operations on Doubly Linked List

A doubly linked list is a data structure where each node contains three parts:

Data (the stored value)
Next pointer (points to the next node)
Prev pointer (points to the previous node)

This bidirectional structure allows traversal in both forward and backward directions and simplifies some operations like deletion.

1. Traversal in a Doubly Linked List

Traversal in a doubly linked list means visiting each node in sequence. We can traverse in two ways:

Forward Traversal: Start from the head and follow the next pointers until reaching the end.
Reverse Traversal: Start from the tail (last node) and follow the prev pointers until reaching the beginning.

Step-by-Step Algorithm for Forward Traversal

Step 1: Initialize a pointer current to the head node.
Step 2: While current is not NULL:
- Print or process the value stored in current.
- Move current to current.next.
Step 3: End when current becomes NULL.

Step-by-Step Algorithm for Reverse Traversal

Step 1: Initialize a pointer current to the head and traverse to the last node (where current.next is NULL).
Step 2: While current is not NULL:
- Print or process the value stored in current.
- Move current to current.prev.
Step 3: End when current becomes NULL.

Code

java

// class DLNode {
//     int val;
//     DLNode prev;
//     DLNode next;

//     // Constructor to initialize a DLNode with a given value.
//     DLNode(int d) {
//         val = d;
//         prev = next = null;  // Initialize previous and next pointers to null.
//     }
// }

class Solution {

  DLNode head; // Head pointer of the list

  // Forward traversal method
  void traverseForward() {
    DLNode current = head; // Start from head
    while (current != null) {
      System.out.print(current.val + " ⇄ ");
      current = current.next; // Move to next node
    }
    System.out.println("NULL");
  }

  // Reverse traversal method
  void traverseBackward() {
    if (head == null) {
      System.out.println("List is empty!");
      return;
    }
    // Move to the tail
    DLNode current = head;
    while (current.next != null) {
      current = current.next;
    }
    // Traverse backward from tail to head
    while (current != null) {
      System.out.print(current.val + " ⇄ ");
      current = current.prev; // Move to previous node
    }
    System.out.println("NULL");
  }

  public static void main(String[] args) {
    Solution list = new Solution();

    // Creating initial doubly linked list: 10 ⇄ 20 ⇄ 30 ⇄ NULL
    list.head = new DLNode(10);
    list.head.next = new DLNode(20);
    list.head.next.prev = list.head;
    list.head.next.next = new DLNode(30);
    list.head.next.next.prev = list.head.next;

    System.out.println("Forward Traversal:");
    list.traverseForward();

    System.out.println("Reverse Traversal:");
    list.traverseBackward();
  }
}

✅ Time Complexity: for both forward and reverse traversals (each node is visited once).
✅ Space Complexity: (Only a pointer is used for traversal).

2. Insertion in a Doubly Linked List

Insertion in a doubly linked list involves adding a new node at a specified position. Due to the bidirectional pointers, updating the list requires adjusting both next and prev pointers. This operation can be done at the beginning, end, or any middle position.

Step-by-Step Algorithm for Insertion at a Specific Position

Create a new node with the given value.
If inserting at position 0 (beginning):
- Set newNode.next to point to the current head.
- If the list isn’t empty, update head.prev to point back to newNode.
- Update head to point to newNode.
- This makes the new node the first element.
Otherwise:
- Traverse the list to find the node at position (position - 1).
  - Start from head and move forward until the desired node is reached.
  - Here, we need the node after which the new node will be inserted.
- If the target position is invalid (beyond the list length), print an error and exit.
Insert the new node:
- Link the New Node Forward: Make the new node point to the node that comes after the previous node (i.e., set newNode.next to previous.next).
- Link the Previous Node to the New Node: Change the previous node so that it now points to the new node (i.e., set previous.next to newNode).
- Link the New Node Backward: If there is a node after the new node, update its prev pointer to point to the new node (i.e., set previous.next.prev to newNode).
- Set the New Node’s Backward Link: Finally, set the new node’s prev pointer to the previous node.

Code

java

// Class to define a Node in a Doubly Linked List
// class DLNode {
//     int val;
//     DLNode next;
//     DLNode prev;

//     DLNode(int val) {
//         this.val = val;
//         this.next = null;
//         this.prev = null;
//     }
// }

class Solution {

  DLNode head; // Head pointer of the list

  // Method to insert a node at a specific position
  void insertAtPosition(int val, int position) {
    DLNode newNode = new DLNode(val);

    // Insertion at the beginning
    if (position == 0) {
      newNode.next = head; // Link new node to current head
      if (head != null) {
        head.prev = newNode; // Update previous head's prev pointer
      }
      head = newNode; // Update head to new node
      return;
    }

    // Find the node at position - 1
    DLNode prev = head;
    for (int i = 0; i < position - 1 && prev != null; i++) {
      prev = prev.next;
    }

    // Check for invalid position
    if (prev == null) {
      System.out.println("Invalid Position!");
      return;
    }

    // Insert newNode between prev and prev.next
    newNode.next = prev.next; // New node points to next node
    if (prev.next != null) {
      // If not inserting at end
      prev.next.prev = newNode; // Update next node's prev pointer
    }
    prev.next = newNode; // Previous node now points to new node
    newNode.prev = prev; // New node's prev pointer points to previous node
  }

  public static void main(String[] args) {
    Solution list = new Solution();

    // Creating initial doubly linked list: 10 ⇄ 20 ⇄ 30 ⇄ NULL
    list.head = new DLNode(10);
    list.head.next = new DLNode(20);
    list.head.next.prev = list.head;
    list.head.next.next = new DLNode(30);
    list.head.next.next.prev = list.head.next;

    System.out.println("Original Doubly Linked List (Forward):");
    list.traverseForward();

    // Insert at different positions
    list.insertAtPosition(5, 0); // Insert at beginning
    list.insertAtPosition(25, 2); // Insert in middle
    list.insertAtPosition(40, 5); // Insert at end

    System.out.println("\nDoubly Linked List after Insertions (Forward):");
    list.traverseForward();
  }

  // Forward traversal method for the doubly linked list
  void traverseForward() {
    DLNode current = head;
    while (current != null) {
      System.out.print(current.val + " ⇄ ");
      current = current.next;
    }
    System.out.println("NULL");
  }
}

✅ Time Complexity: due to traversal (worst-case for middle or end insertion).
✅ Space Complexity: as no extra space is used.

3. Deletion in a Doubly Linked List

Deletion in a doubly linked list involves removing a node while ensuring that both next and prev pointers of neighboring nodes are correctly updated. Deletion can occur at the beginning, at the end, or in the middle.

Step-by-Step Algorithm for Deletion

Check if the list is empty:
- If head is NULL, print an error and exit.
If deleting the first node (position 0):
- Update head to head.next.
- If the new head is not NULL, set its prev pointer to NULL.
- Deletion is complete.
Otherwise, traverse to the node just before the target node (position - 1):
- Start at head and move forward until reaching the node before the one to delete.
- If this node or its next pointer is NULL, the position is invalid; print an error and exit.
Delete the target node:
- Identify the Node to Delete: Let target be the node immediately after the previous node (i.e., target = previous.next).
- Skip the Target Node: Update previous.next so that it points to the node after the target (i.e., previous.next = target.next). This removes the target from the forward chain.
- Fix Backward Link: If there is a node after the target (i.e., target.next is not NULL), update its prev pointer to point back to the previous node. This removes the target from the backward chain.
Deletion is complete.

Code

java

// Class to define a Node in a Doubly Linked List
// class DLNode {
//     int val;
//     DLNode next;
//     DLNode prev;

//     DLNode(int val) {
//         this.val = val;
//         this.next = null;
//         this.prev = null;
//     }
// }

class Solution {

  DLNode head; // Head pointer of the list

  // Method to delete a node at a specific position
  void deleteAtPosition(int position) {
    // If list is empty
    if (head == null) {
      System.out.println("List is empty!");
      return;
    }

    // If deleting the first node
    if (position == 0) {
      head = head.next; // Update head to next node
      if (head != null) {
        head.prev = null; // Set new head's prev pointer to NULL
      }
      return;
    }

    // Find the node at position - 1
    DLNode prev = head;
    for (int i = 0; i < position - 1 && prev != null; i++) {
      prev = prev.next;
    }

    // If position is invalid
    if (prev == null || prev.next == null) {
      System.out.println("Invalid Position!");
      return;
    }

    // Delete the target node
    DLNode target = prev.next; // Node to be deleted
    prev.next = target.next; // Link previous node to target's next
    if (target.next != null) {
      // If target is not the last node
      target.next.prev = prev; // Update next node's prev pointer
    }
  }

  // Method to traverse forward and print the doubly linked list
  void traverseForward() {
    DLNode current = head;
    while (current != null) {
      System.out.print(current.val + " ⇄ ");
      current = current.next;
    }
    System.out.println("NULL");
  }

  public static void main(String[] args) {
    Solution list = new Solution();

    // Creating initial doubly linked list: 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ NULL
    list.head = new DLNode(10);
    list.head.next = new DLNode(20);
    list.head.next.prev = list.head;
    list.head.next.next = new DLNode(30);
    list.head.next.next.prev = list.head.next;
    list.head.next.next.next = new DLNode(40);
    list.head.next.next.next.prev = list.head.next.next;

    System.out.println("Original Doubly Linked List (Forward):");
    list.traverseForward();

    // Delete at different positions
    list.deleteAtPosition(0); // Delete node at position 0 (beginning)
    list.deleteAtPosition(2); // Delete node at position 2 (middle)
    list.deleteAtPosition(2); // Delete node at position 2 (end)

    System.out.println("\nDoubly Linked List after Deletions (Forward):");
    list.traverseForward();
  }
}

✅ Time Complexity: (Traversal required to locate node for deletion).
✅ Space Complexity: (No extra space used).

Let's start solving problems on Linkedlist.

🤖 Don't fully get this? Learn it with Claude

Stuck on Operations on Doubly Linked List? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Operations on Doubly Linked List** (DSA) and want to truly understand it. Explain Operations on Doubly Linked List from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Operations on Doubly Linked List** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Operations on Doubly Linked List** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Operations on Doubly Linked List** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Operations on Singly Linked List Introduction to LinkedList →