Insert at Specific Position in Doubly Linked List in DSA Java - Execution Trace

Concept Flow - Insert at Specific Position in Doubly Linked List

Create new node with data

↓

Check if position is 1

↓

Insert at head

↓

Traverse to position-1 node

↓

Adjust pointers: new node prev and next

↓

Adjust adjacent nodes pointers

↓

Insertion done

Create a new node, then either insert at head if position is 1, or traverse to the node before the position and adjust pointers to insert the new node.

Execution Sample

DSA Java

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

// Insert 99 at position 3 in list 10 <-> 20 <-> 30

This code inserts a new node with value 99 at position 3 in a doubly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=99	10 <-> 20 <-> 30	newNode=null	10 <-> 20 <-> 30
2	Check if position == 1	10 <-> 20 <-> 30	No change	10 <-> 20 <-> 30
3	Start at head (node with 10)	10 <-> 20 <-> 30	current=head(10)	10 <-> 20 <-> 30
4	Traverse to position-1 (2) node	10 <-> 20 <-> 30	current moves to 20	10 <-> 20 <-> 30
5	Set newNode.prev = current (20)	10 <-> 20 <-> 30	newNode.prev=20	10 <-> 20 <-> 30
6	Set newNode.next = current.next (30)	10 <-> 20 <-> 30	newNode.next=30	10 <-> 20 <-> 30
7	Set current.next.prev = newNode	10 <-> 20 <-> 30	30.prev=99	10 <-> 20 <-> 30
8	Set current.next = newNode	10 <-> 20 <-> 30	20.next=99	10 <-> 20 <-> 99 <-> 30
9	Insertion complete	10 <-> 20 <-> 99 <-> 30	Pointers updated	10 <-> 20 <-> 99 <-> 30
10	Exit	10 <-> 20 <-> 99 <-> 30	No further changes	Final list: 10 <-> 20 <-> 99 <-> 30

💡 Insertion done at position 3, pointers updated to include new node.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
newNode.data	null	99	99	99	99	99	99	99
newNode.prev	null	null	null	20	20	20	20	20
newNode.next	null	null	null	null	30	30	30	30
current	null	10	20	20	20	20	20	20
head	10	10	10	10	10	10	10	10
List Size	3	3	3	3	3	3	4	4

Key Moments - 3 Insights

Why do we set newNode.prev to current and newNode.next to current.next?

Because the new node must link back to the node before it (current) and forward to the node after it (current.next). This is shown in steps 5 and 6 in the execution_table.

Why do we update current.next.prev to newNode after setting newNode.next?

To maintain the backward link from the node after the new node back to the new node. This keeps the doubly linked list consistent, as shown in step 7.

What happens if position is 1?

The new node is inserted at the head, adjusting head pointer and next/prev accordingly. This is checked in step 2 and handled separately (not shown in this example).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of current after step 4?

A Node with data 10

B Node with data 20

C Node with data 30

D null

💡 Hint

Check the 'current' variable in variable_tracker after step 4.

At which step is the new node linked to the node after it?

A Step 6

B Step 5

C Step 7

D Step 8

💡 Hint

Look at the pointer changes in execution_table rows for newNode.next assignment.

If we insert at position 1 instead, which step would change?

A Step 4 would move to position 1

B Step 7 would not update any pointers

C Step 2 would be Yes and insertion at head happens

D Step 9 would be skipped

💡 Hint

Refer to step 2 in execution_table where position == 1 is checked.

Concept Snapshot

Insert at Specific Position in Doubly Linked List:
- Create new node with data
- If position == 1, insert at head
- Else traverse to node at position-1
- Set newNode.prev = current
- Set newNode.next = current.next
- Update current.next.prev = newNode
- Update current.next = newNode
- List size increases by 1

Full Transcript

To insert a node at a specific position in a doubly linked list, first create the new node. If the position is 1, insert at the head by adjusting the head pointer and the new node's next and prev pointers. Otherwise, start at the head and move to the node just before the desired position. Then set the new node's prev pointer to this node and its next pointer to the next node. Adjust the next node's prev pointer to the new node and the current node's next pointer to the new node. This keeps the list connected in both directions. The list size increases by one after insertion.

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