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

Concept Flow - Insert at Beginning of Circular Linked List

Create new node

↓

Is list empty?

Yes→new_node.next = new_node

↓

head = new_node

↓

Find last node

↓

new_node.next = head

↓

last_node.next = new_node

↓

head = new_node

↓

Done

Create a new node, if list is empty point it to itself. Otherwise, find last node, link new node before head, update last node's next, and move head to new node.

Execution Sample

DSA C#

Node newNode = new Node(5);
if (head == null) {
  newNode.next = newNode;
  head = newNode;
} else {
  Node last = head;
  while (last.next != head) last = last.next;
  newNode.next = head;
  last.next = newNode;
  head = newNode;
}

Insert a new node with value 5 at the beginning of a circular linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=5	Empty	newNode created, no links yet	∅
2	Check if list is empty (head == null)	Empty	Condition true	∅
3	Set newNode.next = newNode (self-loop)	One node	newNode.next → newNode	┌────────┐ │ data:5 │ │ next:─┐│ └───────┘│ ↑ └─ (points to itself) newNode
4	Set head = newNode	One node	head → newNode	┌────────┐ │ data:5 │ │ next:─┐│ └───────┘│ ↑ └─ (points to itself) head/newNode
5	Insert complete, list has one node pointing to itself	One node	No pointer changes	┌────────┐ │ data:5 │ │ next:─┐│ └───────┘│ ↑ └─ (points to itself) head/newNode
6	Start with list: 10 → 20 → 30 → (back to 10)	Three nodes	head → 10	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ next:─┐│ → │ next:─┐│ → │ next:─┐│ └───────┘│ └───────┘│ └───────┘│ ↑ └──────────────┘ └─→ (back to head 10) head
7	Create new node with data=5	Three nodes	newNode created	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:5 │ │ next:─┐│ → │ next:─┐│ → │ next:─┐│ │ next:∅ │ └───────┘│ └───────┘│ └───────┘│ └───────┘ ↑ └──────────────┘ └─→ head
8	Find last node (node with next == head)	Three nodes	Traverse: 10 → 20 → 30 (last)	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ next:─┐│ → │ next:─┐│ → │ next:─┐│ └───────┘│ └───────┘│ └───────┘│ ↑ └──────────────┘ └─→ (back to head 10) head
9	Set newNode.next = head	Three nodes + newNode	newNode.next → head (10)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:5 │ │ next:─┐│ → │ next:─┐│ → │ next:─┐│ │ next:─┐│ └───────┘│ └───────┘│ └───────┘│ └───────┘ ↑ └──────────────┘ └─→ ↑ head newNode.next
10	Set last.next = newNode	Four nodes	30.next → newNode	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:5 │ │ next:─┐│ → │ next:─┐│ → │ next:─┐│ → │ next:─┐│ └───────┘│ └───────┘│ └───────┘│ └───────┘ ↑ └──────────────┘ ↑ head newNode
11	Update head = newNode	Four nodes	head → newNode	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:5 │ │ data:10│ │ data:20│ │ data:30│ │ next:─┐│ → │ next:─┐│ → │ next:─┐│ → │ next:─┐│ └───────┘│ └───────┘│ └───────┘│ └───────┘ ↑ └──────────────┘ └──────────────┘ head
12	Insertion complete, circular list updated	Four nodes	No pointer changes	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:5 │ │ data:10│ │ data:20│ │ data:30│ │ next:─┐│ → │ next:─┐│ → │ next:─┐│ → │ next:─┐│ └───────┘│ └───────┘│ └───────┘│ └───────┘ ↑ └──────────────┘ └──────────────┘ head

💡 Insertion stops after head is updated to new node, list remains circular.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 9	After Step 10	After Step 11	Final
head	head(10)	head(10)	head(10)	head(10)	head(10)	newNode(5)	newNode(5)
newNode.next	null	newNode(5)	newNode(5)	head(10)	head(10)	head(10)	head(10)
last	null	null	null	head(10)	node(30)	node(30)	node(30)

Key Moments - 3 Insights

Why do we set newNode.next = newNode when the list is empty?

Because in a circular linked list with one node, that node points to itself to maintain the circular structure. See execution_table step 3.

Why do we need to find the last node before inserting at the beginning?

Because the last node's next pointer must be updated to point to the new head to keep the list circular. See execution_table steps 8-10.

Why do we update head to newNode at the end?

Because the new node is inserted at the beginning, so head must point to it. See execution_table step 11.

Visual Quiz - 3 Questions

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

A head node

B newNode itself

C null

D last node

💡 Hint

Check the Pointer Changes column at step 3 in execution_table.

At which step does the last node's next pointer get updated to the new node?

A Step 10

B Step 11

C Step 9

D Step 4

💡 Hint

Look at Pointer Changes column for last.next update in execution_table.

If the list was initially empty, what would be the visual state after insertion?

A Two nodes linked circularly

B Empty list

C One node pointing to itself

D One node pointing to null

💡 Hint

Refer to Visual State column at step 5 in execution_table.

Concept Snapshot

Insert at Beginning of Circular Linked List:
- Create new node
- If list empty: newNode.next = newNode, head = newNode
- Else find last node (node.next == head)
- newNode.next = head
- last.next = newNode
- head = newNode
- List remains circular with new node as head

Full Transcript

To insert a node at the beginning of a circular linked list, first create the new node. If the list is empty, point the new node's next to itself and set head to this new node. If not empty, find the last node by traversing until a node's next points to head. Then set newNode.next to head, update last node's next to newNode, and finally update head to newNode. This keeps the list circular and places the new node at the start.

Practice

1. What happens when you insert a new node at the beginning of a circular linked list?

easy

A. The list becomes linear instead of circular.

B. The new node is added at the end, breaking the circular link.

C. The new node replaces the last node in the list.

D. The new node becomes the head and points to the old head, maintaining the circular link.

Solution

1. Step 1: Understand the circular linked list structure

   A circular linked list has its last node pointing back to the head node, forming a circle.

2. Step 2: Insert new node at beginning

   The new node is linked to the current head, and the last node's next pointer is updated to this new node, making it the new head.

3. Final Answer:

   The new node becomes the head and points to the old head, maintaining the circular link. -> Option D

4. Quick Check:

   New head points to old head, circle intact = A [OK]

Hint: New head points to old head, last node points to new head [OK]

Common Mistakes:

• Forgetting to update last node's next pointer
• Breaking the circular link by not linking last node
• Replacing the last node instead of adding new head

2. Which of the following is the correct syntax to create a new node and insert it at the beginning of a circular linked list in C#?

easy

A. Node newNode = new Node(data); newNode.next = head; head = newNode;

B. Node newNode = new Node(data); newNode.next = null; head = newNode;

C. Node newNode = new Node(data); head.next = newNode; newNode.next = head;

D. Node newNode = new Node(data); newNode.next = head.next; head = newNode;

Solution

1. Step 1: Create new node with data

   Use 'new Node(data)' to create a new node with the given data.

2. Step 2: Link new node to current head and update head

   Set newNode.next to current head, then update head to newNode to insert at beginning.

3. Final Answer:

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

4. Quick Check:

   New node points to old head, head updated = C [OK]

Hint: New node next points to head, then head updated [OK]

Common Mistakes:

• Setting newNode.next to null breaks circular link
• Not updating head to newNode
• Incorrectly linking nodes causing broken list

3. Given the following circular linked list with nodes 10 -> 20 -> 30 -> back to 10, what will be the list after inserting 5 at the beginning?

Node newNode = new Node(5);
newNode.next = head;
Node temp = head;
while(temp.next != head) {
  temp = temp.next;
}
temp.next = newNode;
head = newNode;

medium

A. 5 -> 10 -> 20 -> 30 -> back to 5

B. 10 -> 20 -> 30 -> 5 -> back to 10

C. 5 -> 10 -> 20 -> 30 -> back to 10

D. 10 -> 20 -> 30 -> back to 5

Solution

1. Step 1: Link new node to current head

   newNode.next points to head (10), so newNode links to 10.

2. Step 2: Find last node and update its next pointer

   Traverse to last node (30), update its next to newNode (5), maintaining circular link.

3. Step 3: Update head to newNode

   Head now points to newNode (5), making it the first node.

4. Final Answer:

   5 -> 10 -> 20 -> 30 -> back to 5 -> Option A

5. Quick Check:

   New head 5, last node points to 5 = D [OK]

Hint: Last node must point to new head after insertion [OK]

Common Mistakes:

• Not updating last node's next pointer to new head
• Head not updated to new node
• Breaking circular link by wrong pointer assignment

4. Identify the error in the following code snippet that inserts a node at the beginning of a circular linked list:

Node newNode = new Node(data);
newNode.next = head;
head = newNode;
Node temp = head;
while(temp.next != head) {
  temp = temp.next;
}
temp.next = newNode;

medium

A. The newNode.next should be set to null.

B. The last node's next pointer is not updated correctly.

C. The head is updated before fixing the last node's next pointer, causing an infinite loop.

D. The while loop condition should be temp.next != null.

Solution

1. Step 1: Analyze head update timing

   Head is updated to newNode before finding last node, so temp starts at newNode.

2. Step 2: Check while loop condition

   temp.next (old head) != head (newNode) is true, so loop enters but traverses the old cycle indefinitely since old last.next points to old head != new head, causing infinite loop.

3. Step 3: Consequence of error

   Last node's next pointer is not updated correctly, breaking circular link or causing infinite loop.

4. Final Answer:

   The head is updated before fixing the last node's next pointer, causing an infinite loop. -> Option C

5. Quick Check:

   Update last node after head change causes loop error = A [OK]

Hint: Update last node's next before changing head [OK]

Common Mistakes:

• Changing head before fixing last node's pointer
• Incorrect loop condition for circular list
• Setting newNode.next to null breaks circle

5. You have a circular linked list with only one node (data = 10). You want to insert a new node with data = 5 at the beginning. Which of the following code snippets correctly updates the list to maintain circularity?

hard

A. Node newNode = new Node(5);
newNode.next = null;
head.next = newNode;
head = newNode;

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

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

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

Solution

1. Step 1: Link new node to current head

   newNode.next = head links new node to existing node (10).

2. Step 2: Update old node's next to new node

   head.next = newNode ensures the old node points back to new node, maintaining circularity.

3. Step 3: Update head to new node

   head = newNode makes new node the first node in the list.

4. Final Answer:

   Node newNode = new Node(5); newNode.next = head; head.next = newNode; head = newNode; -> Option B

5. Quick Check:

   Single node circle updated with new head and links = B [OK]

Hint: For single node, update old node's next to new node [OK]

Common Mistakes:

• Setting newNode.next to null breaks circle
• Not updating old node's next pointer
• Not updating head to new node