Insert at Specific Position in Doubly Linked List in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting at position 3

What is the printed state of the doubly linked list after inserting the value 25 at position 3?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
    Node head;

    void insertAtPosition(int data, int position) {
        Node newNode = new Node(data);
        if (position == 1) {
            newNode.next = head;
            if (head != null) head.prev = newNode;
            head = newNode;
            return;
        }
        Node temp = head;
        for (int i = 1; i < position - 1 && temp != null; i++) {
            temp = temp.next;
        }
        if (temp == null) return;
        newNode.next = temp.next;
        if (temp.next != null) temp.next.prev = newNode;
        temp.next = newNode;
        newNode.prev = temp;
    }

    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data);
            if (temp.next != null) System.out.print(" <-> ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.insertAtPosition(10, 1);
        dll.insertAtPosition(20, 2);
        dll.insertAtPosition(30, 3);
        dll.insertAtPosition(25, 3);
        dll.printList();
    }
}

A 10 <-> 20 <-> 25 <-> 30

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

C 25 <-> 10 <-> 20 <-> 30

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

💡 Hint

Remember that inserting at position 3 means the new node should be placed between nodes at positions 2 and 3.

The list starts as 10 <-> 20 <-> 30. Inserting 25 at position 3 places it between 20 and 30, resulting in 10 <-> 20 <-> 25 <-> 30.

❓ Predict Output

intermediate

Output after inserting at head position

What is the printed state of the doubly linked list after inserting the value 5 at position 1?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
    Node head;

    void insertAtPosition(int data, int position) {
        Node newNode = new Node(data);
        if (position == 1) {
            newNode.next = head;
            if (head != null) head.prev = newNode;
            head = newNode;
            return;
        }
        Node temp = head;
        for (int i = 1; i < position - 1 && temp != null; i++) {
            temp = temp.next;
        }
        if (temp == null) return;
        newNode.next = temp.next;
        if (temp.next != null) temp.next.prev = newNode;
        temp.next = newNode;
        newNode.prev = temp;
    }

    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data);
            if (temp.next != null) System.out.print(" <-> ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.insertAtPosition(10, 1);
        dll.insertAtPosition(20, 2);
        dll.insertAtPosition(30, 3);
        dll.insertAtPosition(5, 1);
        dll.printList();
    }
}

A 10 <-> 20 <-> 30 <-> 5

B 10 <-> 5 <-> 20 <-> 30

C 5 <-> 10 <-> 20 <-> 30

D 5 <-> 20 <-> 10 <-> 30

💡 Hint

Inserting at position 1 means the new node becomes the new head.

The new node with value 5 is inserted at the head, pushing the existing nodes forward.

🔧 Debug

advanced

Identify the bug causing NullPointerException

Why does the following code cause a NullPointerException when inserting at position 4 in a list of size 3?

DSA Java

void insertAtPosition(int data, int position) {
    Node newNode = new Node(data);
    if (position == 1) {
        newNode.next = head;
        if (head != null) head.prev = newNode;
        head = newNode;
        return;
    }
    Node temp = head;
    for (int i = 1; i < position - 1; i++) {
        temp = temp.next;
    }
    newNode.next = temp.next;
    if (temp.next != null) temp.next.prev = newNode;
    temp.next = newNode;
    newNode.prev = temp;
}

A The newNode.next is assigned after temp.next is set, causing a conflict.

B The newNode.prev is not set correctly before insertion.

C The head pointer is not updated when inserting at position 4.

D The loop does not check if temp is null before accessing temp.next, causing NullPointerException.

💡 Hint

Check the loop condition and what happens if position is greater than list size + 1.

If position is beyond the list size + 1, temp becomes null in the loop, and accessing temp.next causes NullPointerException.

❓ Predict Output

advanced

Output after inserting at tail position

What is the printed state of the doubly linked list after inserting the value 40 at position 5 in the list 10 <-> 20 <-> 30 <-> 25?

DSA Java

class Node {
    int data;
    Node prev, next;
    Node(int d) { data = d; prev = next = null; }
}

class DoublyLinkedList {
    Node head;

    void insertAtPosition(int data, int position) {
        Node newNode = new Node(data);
        if (position == 1) {
            newNode.next = head;
            if (head != null) head.prev = newNode;
            head = newNode;
            return;
        }
        Node temp = head;
        for (int i = 1; i < position - 1 && temp != null; i++) {
            temp = temp.next;
        }
        if (temp == null) return;
        newNode.next = temp.next;
        if (temp.next != null) temp.next.prev = newNode;
        temp.next = newNode;
        newNode.prev = temp;
    }

    void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data);
            if (temp.next != null) System.out.print(" <-> ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoublyLinkedList dll = new DoublyLinkedList();
        dll.insertAtPosition(10, 1);
        dll.insertAtPosition(20, 2);
        dll.insertAtPosition(30, 3);
        dll.insertAtPosition(25, 4);
        dll.insertAtPosition(40, 5);
        dll.printList();
    }
}

A 10 <-> 20 <-> 30 <-> 25 <-> 40

B 40 <-> 10 <-> 20 <-> 30 <-> 25

C 10 <-> 20 <-> 30 <-> 40 <-> 25

D 10 <-> 20 <-> 25 <-> 30 <-> 40

💡 Hint

Inserting at position 5 means adding after the current last node (position 4).

The new node 40 is added after node 25, which is at position 4, so it becomes the new tail.

🧠 Conceptual

expert

Time complexity of insertion at specific position

What is the time complexity of inserting a node at a specific position in a doubly linked list of size n, assuming you have only the head pointer?

A O(log n), because you can use binary search to find the position.

B O(n), because you may need to traverse up to position - 1 nodes to insert.

C O(1), because insertion is always at the head or tail.

D O(n^2), because each insertion requires traversing the entire list multiple times.

💡 Hint

Think about how you find the node before the insertion point.

Without direct access to the position, you must traverse nodes from the head, which takes linear time.

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