Create a Circular Singly Linked List in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Circular Singly Linked List after Insertions

What is the printed output of the circular singly linked list after inserting nodes with values 10, 20, and 30 in that order?

DSA Java

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

class CircularSinglyLinkedList {
    Node head = null;

    void insert(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;
        }
    }

    void printList() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("null");
    }
}

public class Main {
    public static void main(String[] args) {
        CircularSinglyLinkedList list = new CircularSinglyLinkedList();
        list.insert(10);
        list.insert(20);
        list.insert(30);
        list.printList();
    }
}

A 10 -> 20 -> 30 -> null

B 10 -> 20 -> 30 -> 10 -> null

C 30 -> 20 -> 10 -> null

D List is empty

💡 Hint

Remember that in a circular singly linked list, the last node points back to the head, but printList stops after one full cycle.

The insert method adds nodes at the end, and the printList method prints nodes starting from head until it reaches head again, printing each node once. So the output is the sequence of inserted nodes followed by null.

🧠 Conceptual

intermediate

Understanding Circular Singly Linked List Structure

Which statement correctly describes the structure of a circular singly linked list?

A The head node points to the last node, and the last node points to null.

B The last node points back to the head node, forming a circle.

C Each node has two pointers, one to the next and one to the previous node.

D The last node points to null, and the list has a clear end.

💡 Hint

Think about what makes the list circular.

In a circular singly linked list, the last node's next pointer points back to the head node, creating a loop with no null at the end.

🔧 Debug

advanced

Identify the Bug in Circular List Insertion

What error will occur when running this insertion code for a circular singly linked list?

DSA Java

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

A The list will become linear and lose circularity after first insertion.

B Infinite loop when printing the list.

C No error; code works correctly.

D NullPointerException when inserting second node.

💡 Hint

Check what happens to newNode.next when inserting the first node.

When inserting the first node, newNode.next is set to null instead of head. When inserting the second node, the while loop condition (temp.next != head) evaluates to true (null != head), sets temp to null, and the next condition evaluation causes NullPointerException.

❓ Predict Output

advanced

Output After Deleting a Node in Circular Singly Linked List

What is the output after deleting the node with value 20 from the circular singly linked list containing 10 -> 20 -> 30 -> null?

DSA Java

class CircularSinglyLinkedList {
    Node head = null;

    void insert(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;
        }
    }

    void delete(int data) {
        if (head == null) return;
        Node curr = head, prev = null;
        do {
            if (curr.data == data) {
                if (prev != null) {
                    prev.next = curr.next;
                } else {
                    // Deleting head node
                    Node temp = head;
                    while (temp.next != head) {
                        temp = temp.next;
                    }
                    if (head == head.next) {
                        head = null;
                    } else {
                        temp.next = head.next;
                        head = head.next;
                    }
                }
                return;
            }
            prev = curr;
            curr = curr.next;
        } while (curr != head);
    }

    void printList() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("null");
    }
}

public class Main {
    public static void main(String[] args) {
        CircularSinglyLinkedList list = new CircularSinglyLinkedList();
        list.insert(10);
        list.insert(20);
        list.insert(30);
        list.delete(20);
        list.printList();
    }
}

A 10 -> 30 -> null

B 10 -> 20 -> 30 -> null

C 30 -> 10 -> null

D List is empty

💡 Hint

Deleting node 20 should remove it and maintain circularity.

After deleting node 20, the list contains nodes 10 and 30 linked circularly. The printList method prints 10 -> 30 -> null.

🧠 Conceptual

expert

Time Complexity of Searching in Circular Singly Linked List

What is the time complexity of searching for a value in a circular singly linked list with n nodes?

A O(1) - Constant time because of circularity

B O(log n) - Logarithmic time due to circular structure

C O(n) - Linear time as each node may need to be checked

D O(n^2) - Quadratic time because of repeated traversal

💡 Hint

Consider how many nodes you might check in the worst case.

Searching requires checking each node until the value is found or the list loops back to the head, so it takes linear time O(n). Circularity does not reduce search time.

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