Insert at Beginning of Circular Linked List in DSA C#

Mental Model

A circular linked list connects the last node back to the first, forming a loop. Inserting at the beginning means adding a new node before the current first node and updating the last node to point to this new node.

Analogy: Imagine people sitting in a circle holding hands. To add a new person at the start, you place them before the first person and make sure the last person now holds the new person's hand, keeping the circle unbroken.

head -> 1 -> 2 -> 3 ->
↑                   ↓
←←←←←←←←←←←←←←←←←←←←

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 (circular), insert value 0 at beginning

Goal: Add a new node with value 0 at the start and keep the list circular

Step 1: Create new node with value 0

newNode(0), list: 1 -> 2 -> 3 -> (back to 1)

Why: We need a new node to insert

Step 2: Find last node (node with value 3)

lastNode -> 3, list: 1 -> 2 -> 3 -> (back to 1)

Why: Last node must point to new first node to keep circular

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

newNode(0) -> 1 -> 2 -> 3 -> (back to 1)

Why: New node points to old first node

Step 4: Set lastNode.next to newNode

1 -> 2 -> 3 -> newNode(0) -> 1 -> ... circular

Why: Last node now points to new first node

Step 5: Update head to newNode

head -> newNode(0) -> 1 -> 2 -> 3 -> (back to newNode)

Why: Head must point to new first node

Result:

head -> 0 -> 1 -> 2 -> 3 -> (back to head)

Annotated Code

DSA C#

using System;

public class Node
{
    public int data;
    public Node next;
    public Node(int data)
    {
        this.data = data;
        this.next = null;
    }
}

public class CircularLinkedList
{
    public Node head = null;

    public void InsertAtBeginning(int value)
    {
        Node newNode = new Node(value); // create new node

        if (head == null)
        {
            newNode.next = newNode; // points to itself
            head = newNode; // head is new node
            return;
        }

        Node last = head;
        while (last.next != head) // find last node
        {
            last = last.next;
        }

        newNode.next = head; // new node points to old head
        last.next = newNode; // last node points to new node
        head = newNode; // update head to new node
    }

    public void PrintList()
    {
        if (head == null)
        {
            Console.WriteLine("List is empty");
            return;
        }

        Node temp = head;
        do
        {
            Console.Write(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        Console.WriteLine("(back to head)");
    }
}

public class Program
{
    public static void Main()
    {
        CircularLinkedList cll = new CircularLinkedList();
        cll.InsertAtBeginning(1);
        cll.InsertAtBeginning(2);
        cll.InsertAtBeginning(3);
        // List is now 3 -> 2 -> 1 -> (back to head)

        cll.InsertAtBeginning(0); // insert 0 at beginning
        cll.PrintList();
    }
}

Node newNode = new Node(value); // create new node

create new node with given value

if (head == null) { newNode.next = newNode; // points to itself head = newNode; // head is new node return; }

handle empty list by pointing new node to itself and setting head

Node last = head; while (last.next != head) // find last node { last = last.next; }

find last node which points back to head

newNode.next = head; // new node points to old head

link new node to current head

last.next = newNode; // last node points to new node

update last node to point to new node

head = newNode; // update head to new node

move head pointer to new node

Output

0 -> 3 -> 2 -> 1 -> (back to head)

Complexity Analysis

Time: O(n) because we must traverse the list to find the last node before insertion

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

vs Alternative: Compared to a singly linked list insertion at beginning which is O(1), circular list insertion requires O(n) to update the last node's pointer

Edge Cases

empty list

new node points to itself and becomes head, forming a single-node circular list

DSA C#

if (head == null)
        {
            newNode.next = newNode; // points to itself
            head = newNode; // head is new node
            return;
        }

single node list

last node is the head itself; new node inserted before head and last node updated to point to new node

DSA C#

while (last.next != head) // find last node

When to Use This Pattern

When you see a problem asking to insert at the start of a circular linked list, reach for this pattern because you must update the last node's pointer to maintain the circle.

Common Mistakes

Mistake: Not updating the last node's next pointer to the new head, breaking the circular link
Fix: Always find the last node and set its next pointer to the new node before updating head

Mistake: Not handling empty list case, causing null reference errors
Fix: Check if head is null and initialize the list properly by pointing new node to itself

Summary

Inserts a new node at the start of a circular linked list and updates pointers to keep the circle intact.

Use when you need to add elements quickly at the beginning of a circular linked list.

Remember to update the last node's next pointer to the new node to maintain the circular structure.

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