Create a Circular Singly Linked List in DSA C# - Time & Space Complexity

Time Complexity: Create a Circular Singly Linked List

O(1)

Understanding Time Complexity

We want to understand how long it takes to build a circular singly linked list as we add more items.

How does the time needed 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) {
        Data = data;
        Next = null;
    }
}

public class CircularSinglyLinkedList {
    public Node Tail;

    public void Add(int data) {
        Node newNode = new Node(data);
        if (Tail == null) {
            Tail = newNode;
            Tail.Next = Tail; // points to itself
        } else {
            newNode.Next = Tail.Next;
            Tail.Next = newNode;
            Tail = newNode;
        }
    }
}

This code adds a new node to a circular singly linked list, updating pointers to keep the list circular.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding a node involves only a few pointer changes, no loops or recursion.
• How many times: Each Add call does a fixed number of steps regardless of list size.

How Execution Grows With Input

Each time we add a node, the steps stay the same, no matter how big the list is.

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

Pattern observation: The work to add one node stays constant as the list grows.

Final Time Complexity

Time Complexity: O(1)

This means adding a node takes the same small amount of time no matter how many nodes are already in the list.

Common Mistake

[X] Wrong: "Adding a node takes longer as the list grows because we have to find the end."

[OK] Correct: We keep a reference to the tail node, so we don't search the list; adding is always quick.

Interview Connect

Knowing how to build and add to circular linked lists quickly shows you understand pointers and efficient data structure updates.

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 is the key difference between a circular singly linked list and a regular singly linked list?

easy

A. The last node points to null in a circular singly linked list.

B. Nodes have two pointers in a circular singly linked list.

C. The last node points back to the first node in a circular singly linked list.

D. Nodes are stored in an array in a circular singly linked list.

Solution

1. Step 1: Understand the node connection in a regular singly linked list

   In a regular singly linked list, the last node's next pointer is null, marking the end.

2. Step 2: Understand the node connection in a circular singly linked list

   In a circular singly linked list, the last node's next pointer points back to the first node, forming a circle.

3. Final Answer:

   The last node points back to the first node in a circular singly linked list. -> Option C

4. Quick Check:

   Last node next = first node in circular list [OK]

Hint: Remember: circular means last node loops to first [OK]

Common Mistakes:

• Thinking last node points to null in circular list
• Confusing circular with doubly linked list
• Assuming nodes have two pointers in circular singly linked list

2. Which of the following is the correct way to initialize a circular singly linked list with one node in C#?

easy

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

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

C. Node head = null; head.next = head;

D. Node head = new Node(5); head = null;

Solution

1. Step 1: Create a new node with value 5

   Node head = new Node(5); creates a node with data 5.

2. Step 2: Point the node's next to itself to form a circular link

   head.next = head; makes the list circular with one node.

3. Final Answer:

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

4. Quick Check:

   Single node next points to itself [OK]

Hint: Single node circular list points next to itself [OK]

Common Mistakes:

• Setting next to null instead of self
• Assigning null to head after creation
• Trying to set next on a null head

3. What will be the output of the following code snippet that creates a circular singly linked list with nodes 1, 2, 3 and prints them once?

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

Node head = new Node(1);
Node second = new Node(2);
Node third = new Node(3);
head.next = second;
second.next = third;
third.next = head; // circular link

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

medium

A. 1 -> 2 -> null

B. 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> null

C. 1 -> 2 -> 3 -> 3 -> null

D. 1 -> 2 -> 3 -> null

Solution

1. Step 1: Create nodes and link them circularly

   Nodes 1, 2, 3 are linked so that third.next points back to head, forming a circle.

2. Step 2: Traverse and print nodes once using do-while loop

   The loop prints data starting at head and stops when temp returns to head, printing 1, 2, 3 once.

3. Final Answer:

   1 -> 2 -> 3 -> null -> Option D

4. Quick Check:

   Loop prints each node once before stopping [OK]

Hint: do-while stops after one full circle [OK]

Common Mistakes:

• Using while loop without do causes skipping first node
• Printing nodes infinitely without stop condition
• Confusing circular list with linear list output

4. Identify the error in this code snippet that tries to insert a new node with value 4 at the end of a circular singly linked list:

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

medium

A. newNode.next should be null, not head.

B. The while loop condition should check for temp.next != head, not null.

C. temp should be initialized to null before the loop.

D. The newNode should be created after the loop.

Solution

1. Step 1: Understand circular list's last node pointer

   In a circular singly linked list, the last node's next points to head, never null.

2. Step 2: Correct the loop condition to find last node

   The loop should check temp.next != head to stop at the last node, not temp.next != null.

3. Final Answer:

   The while loop condition should check for temp.next != head, not null. -> Option B

4. Quick Check:

   Last node next = head, not null [OK]

Hint: In circular list, last node points to head, not null [OK]

Common Mistakes:

• Using null check in circular list traversal
• Setting newNode.next to null breaking circularity
• Initializing temp incorrectly

5. You want to create a circular singly linked list from an array of integers [10, 20, 30, 40]. Which approach correctly creates the circular list and returns the head node?

public Node CreateCircularList(int[] arr) {
  if (arr.Length == 0) return null;
  Node head = new Node(arr[0]);
  Node current = head;
  for (int i = 1; i < arr.Length; i++) {
    current.next = new Node(arr[i]);
    current = current.next;
  }
  // What should be here?
}

hard

A. current.next = head; return head;

B. current.next = null; return head;

C. head.next = current; return current;

D. return current;

Solution

1. Step 1: Create nodes from array and link linearly

   Loop creates nodes for each array element and links them in order.

2. Step 2: Make the list circular by linking last node to head

   Setting current.next = head closes the loop, making the list circular.

3. Step 3: Return the head node

   Return head to provide access to the circular list.

4. Final Answer:

   current.next = head; return head; -> Option A

5. Quick Check:

   Last node points to head to form circle [OK]

Hint: Close circle by linking last node to head [OK]

Common Mistakes:

• Leaving last node next as null
• Returning last node instead of head
• Linking head.next to last node instead of last.next to head