Insert at Specific Position in Doubly Linked List in DSA C# - 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 'insert at specific position' mean in a doubly linked list?

It means adding a new node at a given place in the list, not just at the start or end. The position is counted from the start, usually beginning at 1.

intermediate

What pointers need to be updated when inserting a node in the middle of a doubly linked list?

You must update the new node's next and previous pointers, the previous node's next pointer, and the next node's previous pointer to keep the list connected correctly.

beginner

Why do we check if the position is 1 when inserting in a doubly linked list?

Because inserting at position 1 means adding at the start. We must update the head pointer to the new node and adjust the old head's previous pointer.

intermediate

What happens if the position to insert is greater than the length of the doubly linked list?

Usually, the insertion is not done or an error is shown because the position is invalid. Some implementations may insert at the end if position is beyond the list length.

In a doubly linked list, what pointers does a new node have when inserted at position 3?

A Next and Previous both point to node 3

B Next points to node 2, Previous points to node 4

C Next points to node 4, Previous points to node 2

D Next and Previous are null

When inserting at position 3, the new node's next pointer should point to the node currently at position 3 (which becomes position 4), and previous pointer should point to node 2.

What must be updated in the old head node when inserting a new node at position 1?

A Its next pointer

B Its previous pointer

C Both next and previous pointers

D No pointers need updating

The old head's previous pointer must be updated to point to the new node inserted at the start.

If you want to insert at position 1 in an empty doubly linked list, what happens?

A The new node becomes the head with next and previous as null

B Insertion fails because list is empty

C The new node points to itself

D The new node is ignored

Inserting at position 1 in an empty list makes the new node the head, with both next and previous pointers set to null.

Which of these is NOT a valid step when inserting a node at a specific position in a doubly linked list?

A Update the previous node's next pointer

B Update the new node's next and previous pointers

C Traverse to the node before the insertion point

D Update the head pointer if inserting at the end

The head pointer is updated only when inserting at the start, not at the end.

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

A O(n)

B O(log n)

C O(1)

D O(n^2)

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

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 changes are needed to insert a node at the start of a doubly linked list?

Focus on how the head pointer and the old first node are updated.

Practice

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

easy

A. The new node is ignored because position 1 is invalid.

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

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

D. The list is reversed before insertion.

Solution

1. Step 1: Understand position 1 in doubly linked list

   Position 1 means the start of the list, so the new node should be the first element.

2. Step 2: Insert new node at head

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

3. Final Answer:

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

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 of list
• Ignoring previous pointer update
• Assuming position 1 is invalid

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

easy

A. InsertAtPosition(newNode, 3);

B. InsertAtPosition(3, newNode);

C. InsertNodeAt(3, newNode);

D. AddNodeAtPosition(newNode, 3);

Solution

1. Step 1: Check method parameter order

   The common pattern is to pass the node first, then the position.

2. Step 2: Match method name and parameters

   InsertAtPosition(newNode, 3) matches the expected syntax for inserting at position 3.

3. Final Answer:

   InsertAtPosition(newNode, 3); -> Option A

4. Quick Check:

   Node first, position second = InsertAtPosition(newNode, 3); [OK]

Hint: Node comes before position in method call [OK]

Common Mistakes:

• Swapping parameter order
• Using incorrect method names
• Passing position before node

3. Given the doubly linked list: 10 <-> 20 <-> 30 <-> null, what is the list after inserting 15 at position 2?

medium

A. 10 <-> 15 <-> 20 <-> 30 <-> null

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

C. 10 <-> 20 <-> 15 <-> 30 <-> null

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

Solution

1. Step 1: Identify position 2 in the list

   Position 2 means after the first node (10), so new node goes between 10 and 20.

2. Step 2: Insert 15 between 10 and 20

   Update pointers: 10's next to 15, 15's previous to 10, 15's next to 20, 20's previous to 15.

3. Final Answer:

   10 <-> 15 <-> 20 <-> 30 <-> null -> Option A

4. Quick Check:

   Insert at position 2 = between first and second nodes [OK]

Hint: Position 2 means insert after first node [OK]

Common Mistakes:

• Inserting before first node
• Inserting at wrong position
• Not updating previous pointers

4. What is the error in the following code snippet for inserting at position 3 in a doubly linked list?

Node newNode = new Node(25);
Node temp = head;
for (int i = 1; i < 2; i++) {
    temp = temp.next;
}
newNode.next = temp.next;
newNode.prev = temp;
temp.next.prev = newNode;
temp.next = newNode;

medium

A. The loop should run until i < 2, not i < 3.

B. temp.next.prev = newNode; causes null reference if temp.next is null.

C. newNode.prev should be set to temp.prev instead of temp.

D. The newNode.next assignment is missing.

Solution

1. Step 1: Analyze loop and temp position

   The loop moves temp to the node at position 2, so temp.next might be null if list ends there.

2. Step 2: Check pointer updates for null safety

   Accessing temp.next.prev without checking if temp.next is null can cause a runtime error.

3. Final Answer:

   temp.next.prev = newNode; causes null reference if temp.next is null. -> Option B

4. Quick Check:

   Check for null before accessing temp.next.prev [OK]

Hint: Always check temp.next for null before accessing prev [OK]

Common Mistakes:

• Ignoring null pointer checks
• Wrong loop range causing off-by-one
• Incorrect pointer assignments

5. You have a doubly linked list: 5 <-> 10 <-> 15 <-> 20 <-> null. You want to insert a node with value 12 at position 3. After insertion, what will be the correct order of nodes?

medium

A. 5 <-> 10 <-> 15 <-> 20 <-> 12 <-> null

B. 5 <-> 12 <-> 10 <-> 15 <-> 20 <-> null

C. 12 <-> 5 <-> 10 <-> 15 <-> 20 <-> null

D. 5 <-> 10 <-> 12 <-> 15 <-> 20 <-> null

Solution

1. Step 1: Identify position 3 in the list

   Position 3 means the new node should be placed after the second node (10) and before the third node (15).

2. Step 2: Insert node with value 12 between 10 and 15

   Update pointers: 10's next to 12, 12's previous to 10, 12's next to 15, 15's previous to 12.

3. Final Answer:

   5 <-> 10 <-> 12 <-> 15 <-> 20 <-> null -> Option D

4. Quick Check:

   Insert at position 3 places node between second and third nodes [OK]

Hint: Insert at position n means between nodes n-1 and n [OK]

Common Mistakes:

• Inserting at wrong position
• Not updating both next and prev pointers
• Confusing position numbering