Insert at Beginning of Circular Linked List in DSA C# - Time & Space Complexity

Time Complexity: Insert at Beginning of Circular Linked List

O(1)

Understanding Time Complexity

We want to understand how the time needed to insert a node at the start of a circular linked list changes as the list grows.

How does the number of steps grow when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

public Node InsertAtBeginning(Node tail, int value) {
    Node newNode = new Node(value);
    if (tail == null) {
        newNode.next = newNode;
        return newNode;
    }
    newNode.next = tail.next;
    tail.next = newNode;
    return tail;
}
    

This code inserts a new node at the start of a circular linked list by adjusting pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Pointer updates to insert the new node.
• How many times: These pointer changes happen only once per insertion, no loops or recursion.

How Execution Grows With Input

Each insertion requires the same fixed number of steps, no matter how big the list is.

Input Size (n)	Approx. Operations
10	3 pointer changes
100	3 pointer changes
1000	3 pointer changes

Pattern observation: The number of steps stays the same regardless of list size.

Final Time Complexity

Time Complexity: O(1)

This means inserting at the beginning takes a constant amount of time no matter how large the list is.

Common Mistake

[X] Wrong: "We must traverse the whole list to insert at the beginning."

[OK] Correct: Because we keep a reference to the tail node, we can insert at the start by changing just a few pointers without walking through the list.

Interview Connect

Knowing how to insert efficiently in circular linked lists shows you understand pointer manipulation and can optimize operations to constant time.

Self-Check

"What if we did not keep a tail pointer and only had a head pointer? How would the time complexity change?"

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