Delete by Value in Doubly Linked List in DSA Java

Mental Model

We find the node with the given value and remove it by linking its previous and next nodes directly.

Analogy: Imagine a train with cars linked together. To remove one car, you disconnect it and connect the car before it directly to the car after it.

null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null
↑head

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3 ↔ 4, delete value 3

Goal: Remove the node with value 3 and keep the list connected

Step 1: start at head node with value 1

null ← [1↑] ↔ 2 ↔ 3 ↔ 4 -> null

Why: We begin searching from the start to find the node to delete

Step 2: move to next node with value 2

null ← 1 ↔ [2↑] ↔ 3 ↔ 4 -> null

Why: Value 2 is not the target, continue searching

Step 3: move to next node with value 3 (target found)

null ← 1 ↔ 2 ↔ [3↑] ↔ 4 -> null

Why: Found the node to delete

Step 4: link node with value 2 directly to node with value 4, bypassing 3

null ← 1 ↔ 2 ↔ 4 -> null

Why: Removing node 3 by connecting its previous and next nodes

Result:

null ← 1 ↔ 2 ↔ 4 -> null

Annotated Code

DSA Java

class DoublyLinkedList {
    static class Node {
        int data;
        Node prev, next;
        Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }
    }

    Node head;

    void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = newNode;
        newNode.prev = curr;
    }

    void deleteByValue(int value) {
        Node curr = head;
        while (curr != null && curr.data != value) {
            curr = curr.next; // advance curr to find target
        }
        if (curr == null) {
            return; // value not found, nothing to delete
        }
        if (curr.prev != null) {
            curr.prev.next = curr.next; // link previous node to next
        } else {
            head = curr.next; // deleting head node
        }
        if (curr.next != null) {
            curr.next.prev = curr.prev; // link next node to previous
        }
    }

    void printList() {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data);
            if (curr.next != null) {
                System.out.print(" ↔ ");
            }
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.append(1);
        dll.append(2);
        dll.append(3);
        dll.append(4);
        dll.deleteByValue(3);
        dll.printList();
    }
}

while (curr != null && curr.data != value) { curr = curr.next; // advance curr to find target }

search for node with target value

if (curr == null) { return; // value not found, nothing to delete }

handle case when value is not found

if (curr.prev != null) { curr.prev.next = curr.next; // link previous node to next } else { head = curr.next; // deleting head node }

unlink current node from previous node or update head if deleting first node

if (curr.next != null) { curr.next.prev = curr.prev; // link next node to previous }

unlink current node from next node

Output

1 ↔ 2 ↔ 4

Complexity Analysis

Time: O(n) because we may need to traverse all nodes to find the value

Space: O(1) because we only use a few pointers, no extra space proportional to input

vs Alternative: Compared to singly linked list deletion, doubly linked list allows direct access to previous node, making unlinking easier without extra traversal

Edge Cases

empty list

nothing happens, no deletion

DSA Java

if (curr == null) {
    return; // value not found, nothing to delete
}

delete head node

head pointer updates to next node

DSA Java

else {
    head = curr.next; // deleting head node
}

delete last node

previous node's next pointer set to null

DSA Java

if (curr.next != null) {
    curr.next.prev = curr.prev; // link next node to previous
}

value not found

list remains unchanged

DSA Java

if (curr == null) {
    return; // value not found, nothing to delete
}

When to Use This Pattern

When you need to remove a specific value from a doubly linked list, use the delete by value pattern to unlink the node by adjusting its neighbors' pointers.

Common Mistakes

Mistake: Not updating the head when deleting the first node
Fix: Set head to curr.next when curr.prev is null

Mistake: Not checking if curr is null before deletion
Fix: Return immediately if curr is null after search

Mistake: Not updating the prev pointer of the next node
Fix: Set curr.next.prev to curr.prev if curr.next is not null

Summary

Deletes a node with a given value from a doubly linked list by reconnecting its neighbors.

Use when you want to remove a specific value from a doubly linked list efficiently.

The key is to link the previous and next nodes directly, bypassing the node to delete.

Practice

1. What happens when you delete a node by value in a doubly linked list?

easy

A. The node with the matching value is removed and links are updated

B. All nodes are deleted regardless of value

C. Only the first node is deleted no matter the value

D. The list is reversed instead of deleting

Solution

1. Step 1: Locate the node with the given value

   Traverse the list from head to tail to find the node whose data matches the value to delete.

2. Step 2: Update links to remove the node

   Adjust the previous node's next pointer and the next node's previous pointer to bypass the node to be deleted.

3. Final Answer:

   The node with the matching value is removed and links are updated -> Option A

4. Quick Check:

   Deleting by value removes matching node [OK]

Hint: Find node by value, then update previous and next links [OK]

Common Mistakes:

• Not updating both previous and next pointers
• Deleting all nodes instead of one
• Ignoring the case when node is head or tail

2. Which of the following is the correct Java syntax to delete a node by value in a doubly linked list?

easy

A. int deleteByValue(int value) { /* code */ }

B. void deleteByValue(int value) { /* code */ }

C. deleteByValue(int value) { /* code */ }

D. void deleteByValue() { /* code */ }

Solution

1. Step 1: Check method return type and parameters

   The method should accept an integer value to delete and return nothing, so void return type is correct.

2. Step 2: Verify method signature syntax

   Java requires return type before method name and parameter types inside parentheses.

3. Final Answer:

   void deleteByValue(int value) { /* code */ } -> Option B

4. Quick Check:

   Method with void return and int parameter is correct [OK]

Hint: Method must specify return type and parameter types in Java [OK]

Common Mistakes:

• Omitting return type
• Missing parameter type
• Using wrong return type for delete method

3. Given the doubly linked list: 10 <-> 20 <-> 30 <-> 40 <-> null, what is the list after deleting the node with value 30?

medium

A. 10 <-> 20 <-> 40 <-> null

B. 10 <-> 20 <-> 30 <-> 40 <-> null

C. 20 <-> 30 <-> 40 <-> null

D. 10 <-> 40 <-> null

Solution

1. Step 1: Identify node with value 30

   Traverse the list and find the node containing 30 between 20 and 40.

2. Step 2: Remove node 30 and update links

   Set 20's next pointer to 40 and 40's previous pointer to 20, removing 30 from the chain.

3. Final Answer:

   10 <-> 20 <-> 40 <-> null -> Option A

4. Quick Check:

   Node 30 removed, links updated correctly [OK]

Hint: Remove node and link previous to next nodes directly [OK]

Common Mistakes:

• Not updating previous pointer of next node
• Leaving deleted node linked
• Deleting wrong node

4. What is the error in this code snippet for deleting a node by value in a doubly linked list?

void deleteByValue(int value) {
  Node current = head;
  while (current != null && current.data != value) {
    current = current.next;
  }
  if (current == null) return;
  current.prev.next = current.next;
  current.next.prev = current.prev;
}

medium

A. It reverses the list instead of deleting

B. It does not check if current is null before accessing pointers

C. It deletes all nodes with the value instead of one

D. It does not handle deletion when current is head

Solution

1. Step 1: Analyze deletion at head node

   If current is head, current.prev is null, so current.prev.next causes NullPointerException.

2. Step 2: Identify missing condition for head deletion

   Code must check if current.prev is null and update head pointer accordingly.

3. Final Answer:

   It does not handle deletion when current is head -> Option D

4. Quick Check:

   Head deletion needs special handling [OK]

Hint: Check if node is head before updating previous pointer [OK]

Common Mistakes:

• Not handling head or tail nodes separately
• Accessing null pointers without checks
• Assuming node always has previous and next

5. You have a doubly linked list: 5 <-> 10 <-> 15 <-> 20 <-> 25 <-> null. You want to delete the node with value 5, then delete the node with value 25. What is the final list?

hard

A. null

B. 5 <-> 10 <-> 15 <-> 20 <-> null

C. 10 <-> 15 <-> 20 <-> null

D. 10 <-> 15 <-> 20 <-> 25 <-> null

Solution

1. Step 1: Delete node with value 5 (head)

   Since 5 is head, update head to 10 and set 10's prev to null.

2. Step 2: Delete node with value 25 (tail)

   Since 25 is tail, update 20's next to null, removing 25.

3. Final Answer:

   10 <-> 15 <-> 20 <-> null -> Option C

4. Quick Check:

   Head and tail deletions handled correctly [OK]

Hint: Update head or tail pointers when deleting first or last node [OK]

Common Mistakes:

• Not updating head when deleting first node
• Not updating tail when deleting last node
• Breaking links causing list corruption