Posted inDSA

🔗 Doubly Linked List in Java – A Complete Beginner’s Guide (Part 3)

🗑️ Deletion Operations in Doubly Linked List (Beginning, End, Specific Position & By Value)

Welcome to Part 3 of our Doubly Linked List in Java series.

In the previous parts, we learned:

✅ Part 1A

  • Introduction to Doubly Linked List
  • Node Structure
  • Memory Representation
  • Head and Tail

✅ Part 1B

  • Creating a Doubly Linked List
  • Forward Traversal
  • Backward Traversal

✅ Part 2

  • Insertion at Beginning
  • Insertion at End
  • Insertion at Specific Position

Now we’ll learn another important operation:

🗑️ Deletion

Deletion means removing a node from the linked list.

Unlike a Singly Linked List, a Doubly Linked List allows deletion more easily because every node already knows both its previous and next nodes.

In this tutorial, you’ll learn:

  • 🗑️ Delete from Beginning
  • 🗑️ Delete from End
  • 🗑️ Delete at a Specific Position
  • 🗑️ Delete by Value
  • 💻 Complete Java Programs
  • 🔍 Dry Runs
  • 📈 Time Complexity
  • ❓ Interview Questions

Let’s begin!

📚 Table of Contents

  1. What is Deletion?
  2. Types of Deletion
  3. Delete from Beginning
  4. Delete from End
  5. Delete at Specific Position
  6. Delete by Value
  7. Java Programs
  8. Dry Runs
  9. Time Complexity
  10. Common Mistakes
  11. FAQs
  12. Conclusion

🗑️ What is Deletion?

Deletion means removing an existing node from the linked list.

Example

Before deletion

NULL ← 10 ⇄ 20 ⇄ 30 ⇄ 40 → NULL

Delete

20

Result

NULL ← 10 ⇄ 30 ⇄ 40 → NULL

Notice that the node containing 20 is removed, and the links are updated so that 10 connects directly to 30.

📌 Types of Deletion

There are four common deletion operations.

1️⃣ Delete from Beginning

Before

10 ⇄ 20 ⇄ 30

After

20 ⇄ 30

2️⃣ Delete from End

10 ⇄ 20 ⇄ 30

After

10 ⇄ 20

3️⃣ Delete at Specific Position

10 ⇄ 20 ⇄ 30 ⇄ 40

Delete Position 3

10 ⇄ 20 ⇄ 40

4️⃣ Delete by Value

10 ⇄ 20 ⇄ 30 ⇄ 40

Delete

30

Result

10 ⇄ 20 ⇄ 40

🚀 Delete from Beginning

Suppose

Head

↓

NULL ← 10 ⇄ 20 ⇄ 30 → NULL

Delete

10

Result

Head

↓

NULL ← 20 ⇄ 30 → NULL

📝 Algorithm

  1. Check whether the list is empty.
  2. Move Head to the second node.
  3. Set the new Head’s previous reference to NULL.

🎨 Visual Explanation

Current

NULL ← 10 ⇄ 20 ⇄ 30

Update

head = head.next

Update

head.prev = null

Done.

💻 Java Program – Delete from Beginning

public void deleteFromBeginning() {

    if (head == null) {

        System.out.println("List is Empty.");
        return;

    }

    if (head.next == null) {

        head = null;
        return;

    }

    head = head.next;

    head.prev = null;

}

Output

20 ⇄ 30 ⇄ NULL

📈 Time Complexity

O(1)

🚀 Delete from End

Suppose

10 ⇄ 20 ⇄ 30 ⇄ 40

Delete

40

Result

10 ⇄ 20 ⇄ 30

📝 Algorithm

  1. Traverse to the last node.
  2. Move to the previous node.
  3. Set its next reference to NULL.

🎨 Visual Explanation

Current

10 ⇄ 20 ⇄ 30 ⇄ 40

Update

30.next = null

Update

40.prev = null

The node containing 40 becomes unreachable.

💻 Java Program – Delete from End

public void deleteFromEnd() {

    if (head == null) {

        System.out.println("List is Empty.");
        return;

    }

    if (head.next == null) {

        head = null;
        return;

    }

    Node temp = head;

    while (temp.next != null) {

        temp = temp.next;

    }

    temp.prev.next = null;

    temp.prev = null;

}

Output

10 ⇄ 20 ⇄ 30 ⇄ NULL

📈 Time Complexity

Traversal required.

O(n)

🚀 Delete at a Specific Position

Suppose

10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50

Delete Position

3

Result

10 ⇄ 20 ⇄ 40 ⇄ 50

📝 Algorithm

  1. Traverse to the required node.
  2. Update the previous node’s next reference.
  3. Update the next node’s previous reference.
  4. Disconnect the deleted node.

🎨 Visual Explanation

Current

20 ⇄ 30 ⇄ 40

Update

20.next = 40

Update

40.prev = 20

Done.

💻 Java Program – Delete at Position

public void deleteAtPosition(int position) {

    if (head == null) {

        System.out.println("List is Empty.");
        return;

    }

    if (position == 1) {

        deleteFromBeginning();
        return;

    }

    Node temp = head;

    for (int i = 1; i < position && temp != null; i++) {

        temp = temp.next;

    }

    if (temp == null) {

        System.out.println("Invalid Position");
        return;

    }

    if (temp.next == null) {

        deleteFromEnd();
        return;

    }

    temp.prev.next = temp.next;

    temp.next.prev = temp.prev;

    temp.prev = null;

    temp.next = null;

}

Output

10 ⇄ 20 ⇄ 40 ⇄ 50

🚀 Delete by Value

Suppose

10 ⇄ 20 ⇄ 30 ⇄ 40

Delete

30

Result

10 ⇄ 20 ⇄ 40

📝 Algorithm

  1. Search for the node.
  2. Update its previous node.
  3. Update its next node.
  4. Disconnect the deleted node.

💻 Java Program – Delete by Value

public void deleteByValue(int value) {

    if (head == null) {

        System.out.println("List is Empty.");
        return;

    }

    Node temp = head;

    while (temp != null && temp.data != value) {

        temp = temp.next;

    }

    if (temp == null) {

        System.out.println("Value Not Found");
        return;

    }

    if (temp == head) {

        deleteFromBeginning();
        return;

    }

    if (temp.next == null) {

        deleteFromEnd();
        return;

    }

    temp.prev.next = temp.next;

    temp.next.prev = temp.prev;

    temp.prev = null;

    temp.next = null;

}

Output

10 ⇄ 20 ⇄ 40

🔍 Dry Run

Current

10 ⇄ 20 ⇄ 30 ⇄ 40

Delete

30

Update

20.next = 40

Update

40.prev = 20

Final

10 ⇄ 20 ⇄ 40

💻 Complete Java Program

class Node {

    int data;
    Node prev;
    Node next;

    Node(int data) {

        this.data = data;
        prev = null;
        next = null;

    }

}

public class DoublyLinkedList {

    Node head;

    public void insertAtEnd(int data) {

        Node newNode = new Node(data);

        if (head == null) {

            head = newNode;
            return;

        }

        Node temp = head;

        while (temp.next != null)

            temp = temp.next;

        temp.next = newNode;

        newNode.prev = temp;

    }

    public void deleteFromBeginning() {

        if (head == null)
            return;

        if (head.next == null) {

            head = null;
            return;

        }

        head = head.next;

        head.prev = null;

    }

    public void deleteFromEnd() {

        if (head == null)
            return;

        if (head.next == null) {

            head = null;
            return;

        }

        Node temp = head;

        while (temp.next != null)

            temp = temp.next;

        temp.prev.next = null;

    }

    public void deleteAtPosition(int position) {

        if (position == 1) {

            deleteFromBeginning();
            return;

        }

        Node temp = head;

        for (int i = 1; i < position && temp != null; i++)

            temp = temp.next;

        if (temp == null)
            return;

        if (temp.next == null) {

            deleteFromEnd();
            return;

        }

        temp.prev.next = temp.next;

        temp.next.prev = temp.prev;

    }

    public void deleteByValue(int value) {

        Node temp = head;

        while (temp != null && temp.data != value)

            temp = temp.next;

        if (temp == null)
            return;

        if (temp == head) {

            deleteFromBeginning();
            return;

        }

        if (temp.next == null) {

            deleteFromEnd();
            return;

        }

        temp.prev.next = temp.next;

        temp.next.prev = temp.prev;

    }

    public void display() {

        Node temp = head;

        while (temp != null) {

            System.out.print(temp.data + " ⇄ ");

            temp = temp.next;

        }

        System.out.println("NULL");

    }

    public static void main(String[] args) {

        DoublyLinkedList list = new DoublyLinkedList();

        list.insertAtEnd(10);
        list.insertAtEnd(20);
        list.insertAtEnd(30);
        list.insertAtEnd(40);
        list.insertAtEnd(50);

        list.display();

        list.deleteFromBeginning();
        list.display();

        list.deleteFromEnd();
        list.display();

        list.deleteAtPosition(2);
        list.display();

        list.deleteByValue(40);
        list.display();

    }

}

📊 Time Complexity

OperationTime Complexity
Delete from BeginningO(1)
Delete from EndO(n)*
Delete at PositionO(n)
Delete by ValueO(n)

Note: If a Tail pointer is maintained, deletion from the end can be performed in O(1) time.

⚠️ Common Mistakes

❌ Forgetting to update prev

temp.prev.next = temp.next;

but forgetting

temp.next.prev = temp.prev;

This breaks backward traversal.

❌ Not checking for an empty list

Always check:

if(head == null)

before accessing node references.

❌ Forgetting to handle a single-node list

A list containing only one node is a special case and should be handled separately.

❓ Frequently Asked Questions

Q1. Why is deletion easier in a Doubly Linked List?

Because each node already knows its previous node, making it easy to update links in both directions.

Q2. Why is deletion from the beginning O(1)?

Only the head reference and the new head’s prev reference need to be updated.

Q3. Can deletion from the end be O(1)?

Yes, if the list maintains a Tail pointer.

Q4. Why do we disconnect the deleted node?

Disconnecting the node removes unnecessary references, making it eligible for Java’s Garbage Collector.

Q5. Which references are updated during deletion from the middle?

Typically two main references:

  • Previous node’s next
  • Next node’s prev

🎯 Key Takeaways

  • 🗑️ Deletion removes a node by updating surrounding references.
  • 🚀 Deletion from the beginning takes O(1) time.
  • 🚶 Deletion from the end takes O(n) without a Tail pointer.
  • 🔗 Both prev and next references must be updated correctly.
  • 💾 Deleted nodes are automatically reclaimed by Java’s Garbage Collector when no references remain.

🎉 Conclusion

Deletion in a Doubly Linked List is more convenient than in a Singly Linked List because every node has access to both its previous and next neighbors. This makes updating links simpler and allows efficient bidirectional navigation.

In this part, you learned how to delete nodes from the beginning, end, a specific position, and by value, along with complete Java implementations, dry runs, complexity analysis, and common pitfalls.

👉 In Part 4, we’ll explore:

  • 🔍 Searching in a Doubly Linked List
  • ✏️ Updating Node Data
  • 🔢 Counting the Number of Nodes
  • 🔄 Reversing a Doubly Linked List
  • 🚶 Forward and Backward Traversal Revisited
  • 💻 Complete Java Programs
  • 📈 Time Complexity Analysis
  • 🎯 Interview Questions

Comments

No comments yet. Why don’t you start the discussion?

Leave a Reply

Your email address will not be published. Required fields are marked *