Insert at Beginning of Circular Linked List in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting at beginning in circular linked list

What is the printed state of the circular linked list after inserting 10 at the beginning when the list initially contains 20 -> 30 -> 40 -> back to 20?

DSA C#

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

class CircularLinkedList {
    public Node last;

    public void InsertAtBeginning(int data) {
        Node newNode = new Node(data);
        if (last == null) {
            last = newNode;
            last.next = last;
        } else {
            newNode.next = last.next;
            last.next = newNode;
        }
    }

    public string PrintList() {
        if (last == null) return "empty";
        Node temp = last.next;
        string result = "";
        do {
            result += temp.data + " -> ";
            temp = temp.next;
        } while (temp != last.next);
        result += "back to " + last.next.data;
        return result;
    }
}

var cll = new CircularLinkedList();
cll.last = new Node(40);
cll.last.next = new Node(20);
cll.last.next.next = new Node(30);
cll.last.next.next.next = cll.last;
cll.InsertAtBeginning(10);
System.Console.WriteLine(cll.PrintList());

A 10 -> 20 -> 30 -> 40 -> back to 10

B 20 -> 30 -> 40 -> 10 -> back to 20

C 10 -> 40 -> 20 -> 30 -> back to 10

D 40 -> 20 -> 30 -> 10 -> back to 40

💡 Hint

Remember that in a circular linked list, the last node points to the first node. Inserting at the beginning means changing the last node's next pointer.

The InsertAtBeginning method adds a new node after the last node and points it to the previous first node. The last node remains the same, so the list starts at the new node. Hence the order is 10 -> 20 -> 30 -> 40 -> back to 10.

🧠 Conceptual

intermediate

Understanding pointer changes when inserting at beginning

When inserting a new node at the beginning of a circular linked list, which pointer must be updated to maintain the circular structure?

A The last node's next pointer and the new node's previous pointer

B The new node's next pointer and the last node's next pointer

C Only the new node's next pointer

D Only the last node's next pointer

💡 Hint

Think about how the new node connects to the existing list and how the last node points to the first node.

The new node's next pointer must point to the old first node, and the last node's next pointer must point to the new node to keep the circular link intact.

🔧 Debug

advanced

Identify the bug in InsertAtBeginning method

What error will occur if the InsertAtBeginning method does not set last.next = last when the list is initially empty?

DSA C#

public void InsertAtBeginning(int data) {
    Node newNode = new Node(data);
    if (last == null) {
        last = newNode;
        // Missing last.next = last;
    } else {
        newNode.next = last.next;
        last.next = newNode;
    }
}

A The last node will be lost causing the list to become empty.

B The new node will point to itself causing a memory leak.

C The list will not be circular and may cause infinite loop or null reference errors when traversing.

D No error will occur; the list will work correctly.

💡 Hint

Think about what happens when traversing a circular linked list if the last node's next pointer is null.

If last.next is not set to last when the list is empty, the list is not circular. Traversing will reach a null pointer causing errors or infinite loops.

❓ Predict Output

advanced

Result after multiple insertions at beginning

Given an empty circular linked list, what is the printed state after inserting 5, then 15, then 25 at the beginning in that order?

DSA C#

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

class CircularLinkedList {
    public Node last;

    public void InsertAtBeginning(int data) {
        Node newNode = new Node(data);
        if (last == null) {
            last = newNode;
            last.next = last;
        } else {
            newNode.next = last.next;
            last.next = newNode;
        }
    }

    public string PrintList() {
        if (last == null) return "empty";
        Node temp = last.next;
        string result = "";
        do {
            result += temp.data + " -> ";
            temp = temp.next;
        } while (temp != last.next);
        result += "back to " + last.next.data;
        return result;
    }
}

var cll = new CircularLinkedList();
cll.InsertAtBeginning(5);
cll.InsertAtBeginning(15);
cll.InsertAtBeginning(25);
System.Console.WriteLine(cll.PrintList());

A 25 -> 15 -> 5 -> back to 25

B 5 -> 15 -> 25 -> back to 5

C 15 -> 25 -> 5 -> back to 15

D 25 -> 5 -> 15 -> back to 25

💡 Hint

Each insertion at beginning adds a new node after last and before the old first node.

After inserting 5, list is 5 -> back to 5. Then inserting 15 at beginning makes 15 -> 5 -> back to 15. Then inserting 25 at beginning makes 25 -> 15 -> 5 -> back to 25.

🧠 Conceptual

expert

Time complexity of inserting at beginning in circular linked list

What is the time complexity of inserting a node at the beginning of a circular linked list when you have a pointer to the last node?

A O(n^2) quadratic time

B O(n) linear time, where n is the number of nodes

C O(log n) logarithmic time

D O(1) constant time

💡 Hint

Consider how many nodes you need to visit to insert at the beginning if you have the last node pointer.

Since you have direct access to the last node, you can insert the new node after last in constant time without traversing the list.

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