Posted inDSA

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

➕ Insertion Operations in Doubly Linked List (Beginning, End & Specific Position)

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

In Part 1A, we learned:

  • ✅ What is a Doubly Linked List?
  • ✅ Why do we need it?
  • ✅ Structure of a Node
  • ✅ Head and Tail
  • ✅ Memory Representation
  • ✅ Creating Nodes

In Part 1B, we learned:

  • ✅ Creating a Doubly Linked List
  • ✅ Connecting Nodes
  • ✅ Forward Traversal
  • ✅ Backward Traversal

Now it’s time to learn the most important operation of a Doubly Linked List—Insertion.

Unlike a Singly Linked List, a Doubly Linked List stores both previous and next references. Therefore, whenever a new node is inserted, both references must be updated correctly.

In this tutorial, you’ll learn:

  • ➕ Insertion at the Beginning
  • ➕ Insertion at the End
  • ➕ Insertion at a Specific Position
  • 💻 Complete Java Programs
  • 🔍 Dry Runs
  • 📈 Time Complexity
  • 🎯 Interview Questions

Let’s begin!

📚 Table of Contents

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

➕ What is Insertion?

Insertion means adding a new node into a Doubly Linked List.

Example

Before insertion

NULL ← 10 ⇄ 20 ⇄ 30 → NULL

Insert

40

After insertion

NULL ← 10 ⇄ 20 ⇄ 30 ⇄ 40 → NULL

The new node becomes part of the linked list.

📌 Types of Insertion

There are three common insertion operations.

1️⃣ Insert at Beginning

Before

10 ⇄ 20 ⇄ 30

After inserting 5

5 ⇄ 10 ⇄ 20 ⇄ 30

2️⃣ Insert at End

10 ⇄ 20 ⇄ 30

After

10 ⇄ 20 ⇄ 30 ⇄ 40

3️⃣ Insert at Specific Position

10 ⇄ 20 ⇄ 40

Insert 30

10 ⇄ 20 ⇄ 30 ⇄ 40

🚀 Insertion at the Beginning

Suppose we have

Head

↓

NULL ← 10 ⇄ 20 ⇄ 30 → NULL

Insert

5

Step 1

Create a new node.

5

Step 2

Point the new node to the current head.

5 ⇄ 10

This requires two updates.

newNode.next = head

head.prev = newNode

Step 3

Move Head.

Head

↓

NULL ← 5 ⇄ 10 ⇄ 20 ⇄ 30

Done!

🎨 Visual Explanation

Before

NULL ← 10 ⇄ 20 ⇄ 30 → NULL

After

NULL ← 5 ⇄ 10 ⇄ 20 ⇄ 30 → NULL

Notice

Only three references change.

💻 Java Program – Insert at Beginning

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 insertAtBeginning(int data) {

        Node newNode = new Node(data);

        if(head == null){

            head = newNode;
            return;

        }

        newNode.next = head;

        head.prev = newNode;

        head = newNode;

    }

    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.insertAtBeginning(30);
        list.insertAtBeginning(20);
        list.insertAtBeginning(10);

        list.display();

    }

}

Output

10 ⇄ 20 ⇄ 30 ⇄ NULL

📈 Time Complexity

O(1)

🚀 Insertion at the End

Suppose

10 ⇄ 20 ⇄ 30

Insert

40

Result

10 ⇄ 20 ⇄ 30 ⇄ 40

Algorithm

  1. Create new node.
  2. Traverse to last node.
  3. Last node points to new node.
  4. New node points back to last node.

🎨 Visual Explanation

Current

10 ⇄ 20 ⇄ 30

New Node

40

Update

30.next = 40

40.prev = 30

Done.

💻 Java Program – Insert at End

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;

}

Output

10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ NULL

🔍 Dry Run

Current

10 ⇄ 20 ⇄ 30

Traverse

10

↓

20

↓

30

Update

30.next = 40

40.prev = 30

Result

10 ⇄ 20 ⇄ 30 ⇄ 40

📈 Time Complexity

Traversal required.

O(n)

🚀 Insertion at a Specific Position

Suppose

10 ⇄ 20 ⇄ 40 ⇄ 50

Insert

30

at Position 3.

Result

10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50

📝 Algorithm

  1. Traverse to the node before the required position.
  2. Store the next node.
  3. Connect the new node with both neighbors.
  4. Update all references.

🎨 Visual Explanation

Current

20 ⇄ 40

Insert

30

Step 1

30.next = 40

Step 2

30.prev = 20

Step 3

20.next = 30

Step 4

40.prev = 30

Result

20 ⇄ 30 ⇄ 40

Notice

We updated four references.

💻 Java Program – Insert at Position

public void insertAtPosition(int position, int data){

    Node newNode = new Node(data);

    if(position == 1){

        insertAtBeginning(data);

        return;

    }

    Node temp = head;

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

        temp = temp.next;

    }

    if(temp == null){

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

    }

    if(temp.next == null){

        temp.next = newNode;

        newNode.prev = temp;

        return;

    }

    newNode.next = temp.next;

    newNode.prev = temp;

    temp.next.prev = newNode;

    temp.next = newNode;

}

Output

10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50

🔍 Dry Run

Current

10 ⇄ 20 ⇄ 40 ⇄ 50

Move to

20

Update

30.next = 40

Update

30.prev = 20

Update

20.next = 30

Update

40.prev = 30

Final

10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50

💻 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 insertAtBeginning(int data){

        Node newNode = new Node(data);

        if(head == null){

            head = newNode;
            return;

        }

        newNode.next = head;
        head.prev = newNode;
        head = newNode;

    }

    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 insertAtPosition(int position,int data){

        if(position == 1){

            insertAtBeginning(data);
            return;

        }

        Node newNode = new Node(data);

        Node temp = head;

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

            temp = temp.next;

        if(temp == null){

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

        }

        if(temp.next == null){

            temp.next = newNode;

            newNode.prev = temp;

            return;

        }

        newNode.next = temp.next;

        newNode.prev = temp;

        temp.next.prev = newNode;

        temp.next = newNode;

    }

    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(40);

        list.insertAtPosition(3,30);

        list.insertAtBeginning(5);

        list.display();

    }

}

Output

5 ⇄ 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ NULL

📊 Time Complexity

OperationTime Complexity
Insert at BeginningO(1)
Insert at EndO(n)*
Insert at PositionO(n)

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

⚠️ Common Mistakes

❌ Forgetting to update prev

newNode.next = temp.next;

But forgetting

temp.next.prev = newNode;

This breaks backward traversal.

❌ Forgetting to update Head

head = newNode;

Without updating the head during insertion at the beginning, the new node will not become the first node.

❌ Not handling an empty list

Always check:

if(head == null)

before accessing head.next or head.prev.

❓ Frequently Asked Questions

Q1. Why are more references updated than in a Singly Linked List?

Because every node stores both a previous and a next reference, both directions must remain consistent.

Q2. Which insertion is the fastest?

Insertion at the beginning, because it only updates a few references and takes O(1) time.

Q3. Can insertion at the end be O(1)?

Yes. If the list maintains a Tail pointer, the last node can be accessed directly.

Q4. How many references are updated when inserting in the middle?

Typically four references are updated:

  • newNode.next
  • newNode.prev
  • previous.next
  • next.prev

Q5. Why is insertion at a specific position O(n)?

Because the list must first be traversed to reach the required position.

🎯 Key Takeaways

  • ➕ Insertion adds a new node by updating both next and prev references.
  • 🚀 Insertion at the beginning takes O(1) time.
  • 🚶 Insertion at the end takes O(n) without a Tail pointer.
  • 📍 Insertion at a specific position requires updating four references.
  • 🔗 Correctly maintaining both forward and backward links is essential for a valid Doubly Linked List.

🎉 Conclusion

Insertion in a Doubly Linked List is slightly more complex than in a Singly Linked List because every new node must be connected in both directions. However, this extra work provides the major benefit of bidirectional traversal, making many operations more efficient and flexible.

In this part, you learned how to insert nodes at the beginning, end, and any valid position, along with complete Java implementations, dry runs, complexity analysis, and common mistakes to avoid.

👉 In Part 3, we’ll explore Deletion Operations in a Doubly Linked List, including:

  • 🗑️ Deletion from the Beginning
  • 🗑️ Deletion from the End
  • 🗑️ Deletion at a Specific Position
  • 🗑️ Deletion by Value
  • 💻 Complete Java programs
  • 🔍 Detailed dry runs
  • 📈 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 *