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

Time Complexity: Create a Circular Singly Linked List

O(n)

Understanding Time Complexity

When creating a circular singly linked list, we want to know how the time to build it grows as we add more nodes.

We ask: How does the work increase when the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

class CircularLinkedList {
    Node head = null;

    void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            newNode.next = head;
        } else {
            Node temp = head;
            while (temp.next != head) {
                temp = temp.next;
            }
            temp.next = newNode;
            newNode.next = head;
        }
    }
}
    

This code adds nodes to a circular singly linked list, linking the last node back to the head.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that finds the last node before adding a new node.
• How many times: It runs once for each existing node in the list before the new node is added.

How Execution Grows With Input

Each time we add a node, we walk through the list to find the last node.

Input Size (n)	Approx. Operations
10	About 10 steps to add the last node
100	About 100 steps to add the last node
1000	About 1000 steps to add the last node

Pattern observation: The work to add each new node grows linearly with the list size.

Final Time Complexity

Time Complexity: O(n)

This means adding a node takes longer as the list grows, roughly proportional to the number of nodes already in the list.

Common Mistake

[X] Wrong: "Adding a node always takes the same time, no matter how big the list is."

[OK] Correct: Because the code searches through all existing nodes to find the last one, the time grows with the list size.

Interview Connect

Understanding how adding nodes scales helps you explain trade-offs in linked list designs and shows you can analyze code efficiency clearly.

Self-Check

"What if we kept a reference to the last node (tail) in the list? How would the time complexity of adding a node change?"

Practice

1. What is the main difference between a circular singly linked list and a regular singly linked list?

easy

A. In a circular singly linked list, nodes have two pointers instead of one.

B. In a circular singly linked list, nodes are stored in an array.

C. In a circular singly linked list, the last node points back to the first node.

D. In a circular singly linked list, the first node points to null.

Solution

1. Step 1: Understand the structure of a regular singly linked list

   A regular singly linked list has nodes where each node points to the next node, and the last node points to null.

2. Step 2: Understand the structure of a circular singly linked list

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

3. Final Answer:

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

4. Quick Check:

   Last node points to first node = B [OK]

Hint: Remember: circular means last node links back to start [OK]

Common Mistakes:

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

2. Which of the following is the correct way to create a new node in Java for a circular singly linked list?

easy

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

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

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

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

Solution

1. Step 1: Understand node creation for circular singly linked list

   When creating a single node in a circular singly linked list, its next pointer should point to itself to form a circle.

2. Step 2: Check each option

   Node newNode = new Node(data); newNode.next = newNode; sets newNode.next = newNode, which correctly points the node to itself. Other options set next to null or do not initialize properly.

3. Final Answer:

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

4. Quick Check:

   Node points to itself when alone = A [OK]

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

Common Mistakes:

• Setting next to null for single node
• Not initializing next pointer
• Confusing syntax for node creation

3. What will be the output of the following code snippet that creates a circular singly linked list with two nodes and prints their data?

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

public class Test {
  public static void main(String[] args) {
    Node head = new Node(10);
    Node second = new Node(20);
    head.next = second;
    second.next = head;

    System.out.print(head.data + " -> " + head.next.data + " -> " + head.next.next.data);
  }
}

medium

A. 10 -> 20 -> 10

B. 10 -> 20 -> null

C. 10 -> 20 -> 20

D. Compilation error

Solution

1. Step 1: Trace the node connections

   head.data = 10, head.next = second (data 20), second.next = head (data 10), forming a circle.

2. Step 2: Evaluate the print statement

   head.data = 10, head.next.data = 20, head.next.next.data = second.next.data = head.data = 10.

3. Final Answer:

   10 -> 20 -> 10 -> Option A

4. Quick Check:

   Circle repeats first node data = 10 -> 20 -> 10 [OK]

Hint: Follow next pointers carefully to see the cycle [OK]

Common Mistakes:

• Assuming next.next is null
• Confusing node data values
• Expecting compilation error

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

public void insertEnd(Node head, int data) {
  Node newNode = new Node(data);
  if (head == null) {
    head = newNode;
    newNode.next = head;
  } else {
    Node temp = head;
    while (temp.next != null) {
      temp = temp.next;
    }
    temp.next = newNode;
    newNode.next = head;
  }
}

medium

A. The while loop condition should check for temp.next != head instead of null.

B. The newNode.next should be set to null instead of head.

C. The head should be updated to newNode after insertion.

D. The method should return the new head node.

Solution

1. Step 1: Understand circular list traversal

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

2. Step 2: Analyze the while loop condition

   The loop checks temp.next != null, which never happens in circular list; it should check temp.next != head to find the last node.

3. Final Answer:

   The while loop condition should check for temp.next != head instead of null. -> Option A

4. Quick Check:

   Loop must stop at last node pointing to head = A [OK]

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

Common Mistakes:

• Using null to detect end in circular list
• Not updating newNode.next correctly
• Ignoring head update when list is empty

5. You want to create a circular singly linked list from an array of integers {5, 10, 15} by inserting nodes at the end. Which sequence of next pointers correctly represents the final circular list?

hard

A. 15 -> 10 -> 5 -> 15

B. 5 -> 10 -> 15 -> 5

C. 5 -> 10 -> 15 -> null

D. 5 -> 15 -> 10 -> 5

Solution

1. Step 1: Insert nodes at end in given order

   Insert 5 first, then 10 at end, then 15 at end, preserving order: 5, 10, 15.

2. Step 2: Set last node's next to head

   After insertion, last node (15) points back to head (5), making the list circular.

3. Final Answer:

   5 -> 10 -> 15 -> 5 -> Option B

4. Quick Check:

   Order preserved, last points to first = C [OK]

Hint: Insert at end keeps order; last node points to first [OK]

Common Mistakes:

• Assuming last node points to null
• Reversing insertion order
• Mixing node data order