Insert at Beginning of Doubly Linked List in DSA C#

Mental Model

Add a new node at the start by linking it before the current first node and updating the head pointer.

Analogy: Imagine adding a new book at the front of a shelf where each book is connected to the next and previous one. You place the new book first and link it to the old first book.

null ← 1 ↔ 2 ↔ 3 -> null
↑head

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3, insert value 0 at beginning

Goal: Add a new node with value 0 at the start so it becomes the new head

Step 1: Create new node with value 0

null ← 1 ↔ 2 ↔ 3 -> null
newNode(0)
↑head

Why: We need a new node to insert at the beginning

Step 2: Set newNode.next to current head (node 1)

null ← 1 ↔ 2 ↔ 3 -> null
0 -> [next->1]
↑head

Why: Link new node forward to old first node

Step 3: Set current head.prev to newNode

null ← 1 ↔ 2 ↔ 3 -> null
0 ↔ 1 ↔ 2 ↔ 3 -> null
↑head

Why: Link old first node back to new node

Step 4: Update head pointer to newNode

null ← 0 ↔ 1 ↔ 2 ↔ 3 -> null
↑head

Why: New node is now the first node in the list

Result:

null ← 0 ↔ 1 ↔ 2 ↔ 3 -> null
↑head

Annotated Code

DSA C#

using System;

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

    public DoublyLinkedListNode(int value)
    {
        Value = value;
        Prev = null;
        Next = null;
    }
}

public class DoublyLinkedList
{
    public DoublyLinkedListNode Head;

    public DoublyLinkedList()
    {
        Head = null;
    }

    public void InsertAtBeginning(int value)
    {
        DoublyLinkedListNode newNode = new DoublyLinkedListNode(value);
        // Link newNode.next to current head
        newNode.Next = Head;
        // If list not empty, link current head.prev to newNode
        if (Head != null)
        {
            Head.Prev = newNode;
        }
        // Update head to newNode
        Head = newNode;
    }

    public void PrintList()
    {
        DoublyLinkedListNode curr = Head;
        while (curr != null)
        {
            Console.Write(curr.Value);
            if (curr.Next != null) Console.Write(" ↔ ");
            curr = curr.Next;
        }
        Console.WriteLine(" -> null");
    }
}

public class Program
{
    public static void Main()
    {
        DoublyLinkedList list = new DoublyLinkedList();
        // Setup initial list 1 ↔ 2 ↔ 3
        list.InsertAtBeginning(3);
        list.InsertAtBeginning(2);
        list.InsertAtBeginning(1);

        // Insert 0 at beginning
        list.InsertAtBeginning(0);

        list.PrintList();
    }
}

newNode.Next = Head;

link new node forward to current head

if (Head != null) { Head.Prev = newNode; }

if list not empty, link current head back to new node

Head = newNode;

update head pointer to new node

Output

0 ↔ 1 ↔ 2 ↔ 3 -> null

Complexity Analysis

Time: O(1) because insertion at beginning only changes a few pointers without traversal

Space: O(1) because only one new node is created regardless of list size

vs Alternative: Compared to inserting at end which may require traversal O(n), this is faster and simpler

Edge Cases

empty list

new node becomes head with null next and prev

DSA C#

if (Head != null)
        {
            Head.Prev = newNode;
        }

single element list

new node links before the single node, updating head

DSA C#

newNode.Next = Head;

When to Use This Pattern

When you need to add an element quickly at the start of a doubly linked list, use insert at beginning to update head and pointers efficiently.

Common Mistakes

Mistake: Forgetting to update the old head's Prev pointer to the new node
Fix: Add a check and set Head.Prev = newNode if Head is not null

Mistake: Not updating the head pointer to the new node
Fix: Assign Head = newNode after linking pointers

Summary

Adds a new node at the start of a doubly linked list by updating pointers and head.

Use when you want to quickly insert an element at the front without traversing the list.

The key is to link the new node before the current head and then update the head pointer.

Practice

1. What is the main purpose of inserting a node at the beginning of a doubly linked list?

easy

A. To add a new node as the first element of the list

B. To remove the last node from the list

C. To search for a node in the list

D. To reverse the entire list

Solution

1. Step 1: Understand the operation

   Inserting at the beginning means adding a new node before the current first node.

2. Step 2: Identify the effect on the list

   The new node becomes the head (first node), shifting others to the right.

3. Final Answer:

   To add a new node as the first element of the list -> Option A

4. Quick Check:

   Insert at beginning = Add first node [OK]

Hint: Insert at beginning means new node becomes the first [OK]

Common Mistakes:

• Confusing insertion with deletion
• Thinking insertion adds at the end
• Mixing up search with insertion

2. Which of the following is the correct syntax to create a new node in C# for a doubly linked list?

easy

A. Node newNode = new Node(data);

B. newNode = Node(data);

C. Node newNode = Node(data);

D. Node newNode = new Node[];

Solution

1. Step 1: Recall C# object creation syntax

   In C#, objects are created using the 'new' keyword followed by the constructor call.

2. Step 2: Match syntax with node creation

   Correct syntax is 'Node newNode = new Node(data);' to create a new node with data.

3. Final Answer:

   Node newNode = new Node(data); -> Option A

4. Quick Check:

   C# new object = new ClassName() [OK]

Hint: Use 'new' keyword to create objects in C# [OK]

Common Mistakes:

• Omitting 'new' keyword
• Using array syntax for single node
• Missing type declaration

3. Consider this code snippet inserting a node with value 10 at the beginning of a doubly linked list:

Node newNode = new Node(10);
newNode.next = head;
if (head != null) {
    head.prev = newNode;
}
head = newNode;

What will be the printed list after insertion if the original list was: 20 <-> 30 <-> null?

medium

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

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

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

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

Solution

1. Step 1: Insert new node at beginning

   New node with 10 points next to old head (20). Old head's prev points back to new node.

2. Step 2: Update head pointer

   Head now points to new node (10), so list starts with 10.

3. Final Answer:

   10 <-> 20 <-> 30 <-> null -> Option D

4. Quick Check:

   New node at front = 10 first [OK]

Hint: New node points to old head; update old head's prev [OK]

Common Mistakes:

• Not updating old head's prev pointer
• Appending new node at end instead of beginning
• Not updating head to new node

4. Identify the error in this code snippet for inserting at the beginning of a doubly linked list:

Node newNode = new Node(5);
newNode.next = head;
head.prev = newNode;
head = newNode;

medium

A. Incorrect assignment of newNode.next

B. Missing check if head is null before accessing head.prev

C. head should be assigned before setting newNode.next

D. newNode.prev should be set to head

Solution

1. Step 1: Analyze head.prev assignment

   Code sets head.prev = newNode without checking if head is null, causing error if list is empty.

2. Step 2: Identify missing null check

   Must check if head != null before setting head.prev to avoid null reference error.

3. Final Answer:

   Missing check if head is null before accessing head.prev -> Option B

4. Quick Check:

   Check head != null before head.prev [OK]

Hint: Always check head != null before accessing head.prev [OK]

Common Mistakes:

• Ignoring null check on head
• Setting pointers in wrong order
• Confusing prev and next pointers

5. You have a doubly linked list with nodes: 5 <-> 15 <-> 25 <-> null. You want to insert a new node with value 1 at the beginning. After insertion, which of the following correctly represents the list and the pointers of the new node?

hard

A. 5 <-> 15 <-> 25 <-> 1 <-> null, newNode.prev = 25, newNode.next = null

B. 1 <-> 5 <-> 15 <-> 25 <-> null, newNode.prev = 5, newNode.next = null

C. 1 <-> 5 <-> 15 <-> 25 <-> null, newNode.prev = null, newNode.next = 5

D. 5 <-> 15 <-> 25 <-> 1 <-> null, newNode.prev = null, newNode.next = 5

Solution

1. Step 1: Insert new node at beginning

   New node with value 1 becomes head, points next to old head (5), prev is null.

2. Step 2: Confirm pointers and list order

   List order is 1 <-> 5 <-> 15 <-> 25 <-> null, newNode.prev = null, newNode.next = 5.

3. Final Answer:

   1 <-> 5 <-> 15 <-> 25 <-> null, newNode.prev = null, newNode.next = 5 -> Option C

4. Quick Check:

   New head prev=null, next=old head [OK]

Hint: New head prev=null, next=old head node [OK]

Common Mistakes:

• Setting newNode.prev to old head
• Appending new node at end instead of beginning
• Not updating head pointer