Insert at Specific Position in Doubly Linked List in DSA C#

Mental Model

We add a new item exactly where we want by changing the links before and after that spot.

Analogy: Imagine a train with cars linked front and back. To add a new car in the middle, you disconnect the two cars where you want to insert, then connect the new car between them.

null ← 1 ↔ 2 ↔ 3 -> null
          ↑

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 4 at position 2

Goal: Insert the value 4 between nodes 1 and 2

Step 1: start at head node 1

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

Why: We begin from the start to find the correct position

Step 2: current remains at node 1 (position 1 = position - 1)

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

Why: Traverse (or stay) at the node before the insertion position

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

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

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

Result:

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

Annotated Code

DSA C#

using System;

public class DoublyLinkedListNode
{
    public int Data;
    public DoublyLinkedListNode Prev;
    public DoublyLinkedListNode Next;

    public DoublyLinkedListNode(int data)
    {
        Data = data;
        Prev = null;
        Next = null;
    }
}

public class DoublyLinkedList
{
    public DoublyLinkedListNode Head;

    public DoublyLinkedList()
    {
        Head = null;
    }

    public void InsertAtPosition(int data, int position)
    {
        var newNode = new DoublyLinkedListNode(data);
        if (position == 1)
        {
            newNode.Next = Head; // link new node to current head
            if (Head != null)
                Head.Prev = newNode; // link current head back to new node
            Head = newNode; // update head to new node
            return;
        }

        var current = Head;
        int currentPosition = 1;

        // move to node before insertion point
        while (current != null && currentPosition < position - 1)
        {
            current = current.Next; // advance current
            currentPosition++;
        }

        if (current == null)
        {
            Console.WriteLine("Position out of bounds");
            return;
        }

        newNode.Next = current.Next; // new node points to next node
        if (current.Next != null)
            current.Next.Prev = newNode; // next node points back to new node
        current.Next = newNode; // current node points forward to new node
        newNode.Prev = current; // new node points back to current
    }

    public void PrintList()
    {
        var current = Head;
        while (current != null)
        {
            Console.Write(current.Data);
            if (current.Next != null)
                Console.Write(" ↔ ");
            current = current.Next;
        }
        Console.WriteLine();
    }
}

public class Program
{
    public static void Main()
    {
        var list = new DoublyLinkedList();
        list.InsertAtPosition(1, 1);
        list.InsertAtPosition(2, 2);
        list.InsertAtPosition(3, 3);

        list.InsertAtPosition(4, 2); // insert 4 at position 2

        list.PrintList();
    }
}

if (position == 1) { newNode.Next = Head; // link new node to current head if (Head != null) Head.Prev = newNode; // link current head back to new node Head = newNode; // update head to new node return; }

handle insertion at the start by adjusting head and links

while (current != null && currentPosition < position - 1) { current = current.Next; // advance current currentPosition++; }

move to node before insertion position

if (current == null) { Console.WriteLine("Position out of bounds"); return; }

check if position is valid

newNode.Next = current.Next; // new node points to next node if (current.Next != null) current.Next.Prev = newNode; // next node points back to new node current.Next = newNode; // current node points forward to new node newNode.Prev = current; // new node points back to current

link new node between current and current.Next

Output

1 ↔ 4 ↔ 2 ↔ 3

Complexity Analysis

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

Space: O(1) because we only create one new node and use a few pointers

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 1 (start)

new node becomes the new head, links adjusted accordingly

DSA C#

if (position == 1)

inserting at position greater than list length + 1

prints 'Position out of bounds' and does not insert

DSA C#

if (current == null)

inserting into empty list at position 1

new node becomes head with no next or prev

DSA C#

if (position == 1)

When to Use This Pattern

When a problem asks to add an element at a certain place in a doubly linked list, use this insertion pattern to adjust both forward and backward links carefully.

Common Mistakes

Mistake: Not updating the Prev pointer of the node after the inserted node
Fix: Always set current.Next.Prev = newNode if current.Next is not null

Mistake: Not handling insertion at the head separately
Fix: Check if position is 1 and update head and links 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 start or end.

The key is to carefully link the new node between its neighbors without breaking the chain.

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