Insert at Beginning of Doubly Linked List in DSA C# - Execution Trace

Concept Flow - Insert at Beginning of Doubly Linked List

Create new node

↓

Set newNode.next = head

↓

If head != null

↓

Set head.prev = newNode

↓

Set head = newNode

↓

Done

This flow shows how a new node is created and inserted at the start of the doubly linked list by adjusting next and prev pointers.

Execution Sample

DSA C#

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

// Insert at beginning
void InsertAtBeginning(ref Node head, int data) {
  Node newNode = new Node(data);
  newNode.next = head;
  if (head != null) {
    head.prev = newNode;
  }
  head = newNode;
}

This code creates a new node and inserts it at the beginning of a doubly linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with empty list	∅	head = null	List is empty
2	Create new node with data=10	Node(10)	newNode.prev = null, newNode.next = null	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
3	Set newNode.next = head (null)	Node(10)	newNode.next = null	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
4	Since head is null, skip head.prev update	Node(10)	No change	┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
5	Set head = newNode	Node(10)	head → newNode	head ┌────────┐ │ data:10│ │ prev:∅ │ │ next:∅ │ └────────┘
6	Insert another node with data=20 at beginning	Node(20) → Node(10)	newNode.prev = null, newNode.next = head head.prev = newNode head = newNode	Before: head ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ prev:∅ │ │ prev:∅ │ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ Step 1: newNode.next = head Step 2: head.prev = newNode Step 3: head = newNode After: head ┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ prev:∅ │←── │ prev:20│ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘
7	Insert node with data=30 at beginning	Node(30) → Node(20) → Node(10)	newNode.prev = null, newNode.next = head head.prev = newNode head = newNode	Before: head ┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ data:30│ │ prev:∅ │←── │ prev:20│ │ prev:∅ │ │ next:──┼──→ │ next:∅ │ │ next:∅ │ └────────┘ └────────┘ └────────┘ Step 1: newNode.next = head Step 2: head.prev = newNode Step 3: head = newNode After: head ┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ prev:∅ │←── │ prev:30│←── │ prev:20│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘
8	End of insertions	Node(30) → Node(20) → Node(10)	head points to Node(30)	Final list: head ┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ prev:∅ │←── │ prev:30│←── │ prev:20│ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘

💡 No more nodes to insert; insertion at beginning complete.

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 7	Final
head	null	Node(10)	Node(20)	Node(30)	Node(30)
newNode	null	Node(10)	Node(20)	Node(30)	null (reset after insertion)
newNode.prev	null	null	null	null	null
newNode.next	null	null	Node(10)	Node(20)	Node(20)

Key Moments - 3 Insights

Why do we set newNode.next = head before changing head?

Because we need newNode to point to the current first node before head changes. See execution_table step 6 where newNode.next is set to old head before head is updated.

Why do we check if head is null before setting head.prev?

If head is null (empty list), there is no node to update prev pointer. This avoids errors. See execution_table step 4 where this check skips updating head.prev.

How do prev pointers help in a doubly linked list?

Prev pointers allow backward traversal. After insertion, newNode.prev is null (start), and old head.prev points back to newNode. See pointer changes in steps 6 and 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what does newNode.next point to after insertion?

A Node with data 10

B Node with data 20

C null

D Node with data 30

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 6 showing newNode.next = head which was Node(10)

At which step does the list first have two nodes linked?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look at 'Nodes in List' column to see when list length changes from 1 to 2

If head was not null, what pointer must be updated to maintain the doubly linked list?

A newNode.next

B head.prev

C newNode.prev

D newNode.data

💡 Hint

Refer to concept_flow and execution_table step 6 where head.prev is updated to newNode

Concept Snapshot

Insert at Beginning of Doubly Linked List:
- Create new node with data
- Set newNode.next to current head
- If head exists, set head.prev to newNode
- Update head to newNode
- newNode.prev is always null (start of list)
- Maintains forward and backward links

Full Transcript

To insert a node at the beginning of a doubly linked list, first create a new node with the given data. Then set the new node's next pointer to the current head of the list. If the list is not empty, update the current head's prev pointer to point back to the new node. Finally, update the head pointer to the new node. This ensures the new node is now the first node, with its prev pointer null and next pointing to the old first node. The doubly linked list maintains both forward and backward links after insertion.

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