Insert at Specific Position in Doubly Linked List in DSA Java

Mental Model

A doubly linked list lets you move forward and backward through nodes. To insert at a specific spot, you find that spot and adjust the nearby nodes to include the new one.

Analogy: Imagine a train with cars linked front and back. To add a new car in the middle, you disconnect the link between two cars and connect the new car between them, so the train stays connected both ways.

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

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 4 at position 2 (0-based index)

Goal: Insert the value 4 between nodes 2 and 3, so the list becomes 1 ↔ 2 ↔ 4 ↔ 3

Step 1: start at head node 1, position 0

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

Why: We begin traversal from the head to find the insertion point

Step 2: move to node 2, position 1

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

Why: We move forward to reach the node before the insertion position

Step 3: create new node 4 and link it between 2 and 3

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

Why: Adjust pointers to insert new node without breaking the list

Step 4: update next of 2 to 4 and prev of 3 to 4

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

Why: Final pointer updates complete the insertion

Result:

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

Annotated Code

DSA Java

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

    Node head;

    // Insert at specific position (0-based index)
    public void insertAtPosition(int data, int position) {
        Node newNode = new Node(data);
        if (position == 0) {
            // Insert at head
            newNode.next = head;
            if (head != null) {
                head.prev = newNode;
            }
            head = newNode;
            return;
        }

        Node curr = head;
        int index = 0;
        // Traverse to node before insertion point
        while (curr != null && index < position - 1) {
            curr = curr.next;
            index++;
        }

        // If curr is null, position is out of bounds
        if (curr == null) {
            System.out.println("Position out of bounds");
            return;
        }

        // Insert newNode after curr
        newNode.next = curr.next;
        newNode.prev = curr;
        if (curr.next != null) {
            curr.next.prev = newNode;
        }
        curr.next = newNode;
    }

    // Print list forward
    public 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();
        // Create initial list 1 ↔ 2 ↔ 3
        dll.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        dll.head.next = second;
        second.prev = dll.head;
        second.next = third;
        third.prev = second;

        // Insert 4 at position 2
        dll.insertAtPosition(4, 2);

        // Print final list
        dll.printList();
    }
}

if (position == 0) { ... }

handle insertion at the head of the list

while (curr != null && index < position - 1) { curr = curr.next; index++; }

traverse to node before insertion position

if (curr == null) { System.out.println("Position out of bounds"); return; }

check for invalid position beyond list length

newNode.next = curr.next; newNode.prev = curr;

link new node's next and prev pointers

if (curr.next != null) { curr.next.prev = newNode; }

update next node's prev pointer if it exists

curr.next = newNode;

link current node's next pointer to new node

Output

1 ↔ 2 ↔ 4 ↔ 3

Complexity Analysis

Time: O(n) because we may need to traverse up to n nodes to reach the insertion point

Space: O(1) because insertion uses a fixed amount of extra space for the new node

vs Alternative: Compared to inserting at head or tail which is O(1), inserting at a specific position requires traversal, making it O(n)

Edge Cases

inserting at position 0 (head)

new node becomes the new head, previous head's prev pointer updated

DSA Java

if (position == 0) { ... }

inserting at position greater than list length

prints "Position out of bounds" and does not insert

DSA Java

if (curr == null) { System.out.println("Position out of bounds"); return; }

inserting at the end (position equals list length)

new node is appended at the tail, prev pointer set correctly

DSA Java

newNode.next = curr.next; newNode.prev = curr;

When to Use This Pattern

When a problem asks to insert an element at a specific position in a doubly linked list, use traversal to that position and pointer adjustments to insert the node.

Common Mistakes

Mistake: Not updating the prev pointer of the node after the inserted node
Fix: Always update curr.next.prev to newNode if curr.next is not null

Mistake: Not handling insertion at head separately
Fix: Check if position is 0 and update head and pointers accordingly

Summary

Inserts a new node at a given position in a doubly linked list by adjusting next and prev pointers.

Use when you need to add an element anywhere in the list, not just at the ends.

The key is to find the node before the insertion point and carefully update four pointers to keep the list connected both ways.

Practice

1. What happens when you insert a new node at position 1 in a doubly linked list?

easy

A. The new node becomes the new head of the list.

B. The new node is added at the end of the list.

C. The new node replaces the last node.

D. The list remains unchanged.

Solution

1. Step 1: Understand position 1 insertion

   Inserting at position 1 means adding the node at the start of the list.

2. Step 2: Effect on the list head

   The new node becomes the head, and its next points to the old head.

3. Final Answer:

   The new node becomes the new head of the list. -> Option A

4. Quick Check:

   Insert at position 1 = new head [OK]

Hint: Position 1 means new head insertion [OK]

Common Mistakes:

• Thinking position 1 means end insertion
• Not updating previous head's previous pointer
• Ignoring head pointer update

2. Which of the following is the correct syntax to insert a new node at position pos in a doubly linked list in Java?

easy

A. newNode.next = current; newNode.prev = current.next; current.next = newNode; current.prev = newNode;

B. newNode.prev = current.next; newNode.next = current; current.prev.next = newNode; current.prev = newNode;

C. newNode.next = current.prev; newNode.prev = current.next; current.next = newNode; current.prev = newNode;

D. newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode;

Solution

1. Step 1: Identify correct pointer updates

   For insertion, newNode's next points to current's next, and prev points to current.

2. Step 2: Update surrounding nodes

   current.next's prev must point to newNode, and current's next must point to newNode.

3. Final Answer:

   newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode; -> Option D

4. Quick Check:

   Correct pointer updates = newNode.next = current.next; newNode.prev = current; current.next.prev = newNode; current.next = newNode; [OK]

Hint: Remember to update both next and prev pointers [OK]

Common Mistakes:

• Swapping next and prev pointers
• Not updating current.next.prev
• Incorrect order of pointer assignments

3. Given the doubly linked list: 1 <-> 2 <-> 4 <-> null, what will be the list after inserting node with value 3 at position 3?

medium

A. 1 <-> 2 <-> 3 <-> 4 <-> null

B. 1 <-> 3 <-> 2 <-> 4 <-> null

C. 3 <-> 1 <-> 2 <-> 4 <-> null

D. 1 <-> 2 <-> 4 <-> 3 <-> null

Solution

1. Step 1: Locate position 3 in the list

   Positions: 1=1, 2=2, 3=4 currently. Insert before node with value 4.

2. Step 2: Insert new node with value 3 at position 3

   New node's next points to node with value 4, prev points to node with value 2. Update pointers accordingly.

3. Final Answer:

   1 <-> 2 <-> 3 <-> 4 <-> null -> Option A

4. Quick Check:

   Insert at position 3 places 3 before 4 [OK]

Hint: Insert before node currently at position [OK]

Common Mistakes:

• Inserting after position instead of at position
• Not updating prev pointer of next node
• Confusing node values and positions

4. Consider this code snippet to insert at position 2 in a doubly linked list:

Node newNode = new Node(5);
Node current = head;
current = current.next;
newNode.next = current.next;
newNode.prev = current;
current.next = newNode;
newNode.next.prev = newNode;

What is the error in this code?

medium

A. It does not handle insertion at head correctly.

B. It may cause NullPointerException if current.next is null.

C. It forgets to update newNode.prev pointer.

D. It inserts the node at the end always.

Solution

1. Step 1: Analyze newNode.next assignment

   newNode.next = current.next; If current.next is null (inserting at end), newNode.next.prev causes error.

2. Step 2: Identify NullPointerException risk

   Accessing newNode.next.prev without checking null causes NullPointerException.

3. Final Answer:

   It may cause NullPointerException if current.next is null. -> Option B

4. Quick Check:

   Check for null before newNode.next.prev update [OK]

Hint: Always check if next node is null before accessing its prev [OK]

Common Mistakes:

• Not checking for null before pointer updates
• Assuming list has more nodes without validation
• Forgetting to update head or tail pointers

5. You have a doubly linked list: 10 <-> 20 <-> 30 <-> 40 <-> null. You want to insert a node with value 25 at position 3. After insertion, you also want to delete the node at position 4. What will be the final list?

hard

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

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

C. 10 <-> 20 <-> 25 <-> 40 <-> null

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

Solution

1. Step 1: Insert 25 at position 3

   Positions before insertion: 1=10, 2=20, 3=30, 4=40. Insert 25 before 30, so list becomes 10 <-> 20 <-> 25 <-> 30 <-> 40.

2. Step 2: Delete node at position 4

   After insertion, position 4 is node with value 30. Remove it by updating pointers: 25's next points to 40, 40's prev points to 25.

3. Final Answer:

   10 <-> 20 <-> 25 <-> 40 <-> null -> Option C

4. Quick Check:

   Insert then delete correct nodes = 10 <-> 20 <-> 25 <-> 40 <-> null [OK]

Hint: Insert first, then delete at updated position [OK]

Common Mistakes:

• Deleting wrong node after insertion
• Not updating pointers after deletion
• Confusing positions before and after insertion