Insert at Specific Position in Doubly Linked List in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a doubly linked list?

A doubly linked list is a chain of nodes where each node has three parts: data, a pointer to the next node, and a pointer to the previous node. This allows moving forward and backward through the list.

beginner

What does inserting at a specific position in a doubly linked list mean?

It means adding a new node at a chosen place in the list, not just at the start or end. We adjust the pointers of nearby nodes to include the new node.

intermediate

What pointers need to be updated when inserting a node at position 3 in a doubly linked list?

You update the new node's next to point to the old node at position 3, its previous to point to node at position 2, then update node 2's next to new node, and node 3's previous to new node.

beginner

Why do we need to check if the position is valid before insertion?

Because inserting at a position outside the list length can cause errors or crashes. Validating ensures the position exists or is at the end.

beginner

What happens if you insert at position 1 in a doubly linked list?

The new node becomes the new head. Its next points to the old head, and the old head's previous points back to the new node.

In a doubly linked list, what does each node contain?

A Data, next pointer, previous pointer

B Data only

C Data and next pointer only

D Data and previous pointer only

Each node has data, a pointer to the next node, and a pointer to the previous node.

When inserting at position 1, what pointer of the old head node must be updated?

A Its previous pointer

B Its next pointer

C Its data

D No pointer needs updating

The old head's previous pointer must point to the new node inserted at position 1.

What should you do if the position to insert is greater than the list length + 1?

A Insert at the end

B Return an error or do nothing

C Insert at the start

D Insert at position 1

Positions beyond list length + 1 are invalid; insertion should be prevented or handled as an error.

Which pointers are updated when inserting a node between two existing nodes?

A Only the new node's pointers

B Only the previous node's pointer

C New node's pointers and the adjacent nodes' pointers

D Only the next node's pointer

You update the new node's next and previous pointers, and also the adjacent nodes' pointers to include the new node.

What is the time complexity of inserting at a specific position in a doubly linked list?

A O(1)

B O(n^2)

C O(log n)

D O(n)

You may need to traverse up to the position, which takes O(n) time.

Explain step-by-step how to insert a new node at position 3 in a doubly linked list.

Think about how pointers connect nodes before and after the new node.

What checks should you perform before inserting a node at a specific position in a doubly linked list?

Consider list boundaries and valid positions.

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