Create a Circular Singly Linked List in DSA C++ - 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 C++

#include <iostream>
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class CircularSinglyLinkedList {
public:
    Node* tail;
    CircularSinglyLinkedList() : tail(nullptr) {}

    void insert(int val) {
        Node* newNode = new Node(val);
        if (!tail) {
            tail = newNode;
            tail->next = tail;
        } else {
            newNode->next = tail->next;
            tail->next = newNode;
            tail = newNode;
        }
    }

    void print() {
        if (!tail) return;
        Node* temp = tail->next;
        do {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        } while (temp != tail->next);
        std::cout << "null" << std::endl;
    }
};

int main() {
    CircularSinglyLinkedList list;
    list.insert(10);
    list.insert(20);
    list.insert(30);
    list.print();
    return 0;
}

A 30 -> 20 -> 10 -> null

B 10 -> 30 -> 20 -> null

C 20 -> 30 -> 10 -> null

D 10 -> 20 -> 30 -> null

💡 Hint

Remember that insertion adds the new node after the tail and updates the tail to the new node.

The insert function adds new nodes after the tail and moves the tail pointer to the new node. The print starts from tail->next, which is the head. So the order is 10 -> 20 -> 30 -> null.

❓ Predict Output

intermediate

Output after Deleting Head Node in Circular Singly Linked List

Given the circular singly linked list with nodes 5 -> 15 -> 25 -> null, what is the output after deleting the head node (node with value 5)?

DSA C++

#include <iostream>
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class CircularSinglyLinkedList {
public:
    Node* tail;
    CircularSinglyLinkedList() : tail(nullptr) {}

    void insert(int val) {
        Node* newNode = new Node(val);
        if (!tail) {
            tail = newNode;
            tail->next = tail;
        } else {
            newNode->next = tail->next;
            tail->next = newNode;
            tail = newNode;
        }
    }

    void deleteHead() {
        if (!tail) return;
        Node* head = tail->next;
        if (head == tail) {
            delete head;
            tail = nullptr;
        } else {
            tail->next = head->next;
            delete head;
        }
    }

    void print() {
        if (!tail) return;
        Node* temp = tail->next;
        do {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        } while (temp != tail->next);
        std::cout << "null" << std::endl;
    }
};

int main() {
    CircularSinglyLinkedList list;
    list.insert(5);
    list.insert(15);
    list.insert(25);
    list.deleteHead();
    list.print();
    return 0;
}

A 15 -> 25 -> null

B 5 -> 15 -> 25 -> null

C 25 -> 15 -> null

D 15 -> 25 -> 5 -> null

💡 Hint

Deleting head means removing the node tail->next points to and updating tail->next.

After deleting the head node (5), the new head is 15, and the list becomes 15 -> 25 -> null.

🔧 Debug

advanced

Identify the Bug in Circular Singly Linked List Insertion

What is the bug in the following insert function for a circular singly linked list?

DSA C++

void insert(int val) {
    Node* newNode = new Node(val);
    if (!tail) {
        tail = newNode;
        newNode->next = nullptr;
    } else {
        newNode->next = tail->next;
        tail->next = newNode;
        tail = newNode;
    }
}

A newNode should be deleted after insertion to avoid memory leak

B tail pointer should not be updated after insertion

C newNode->next should point to tail, not nullptr, when list is empty

D The function should not create a new node inside insert

💡 Hint

In a circular list with one node, that node's next must point to itself.

When the list is empty, the new node's next must point to itself to maintain circularity. Setting it to nullptr breaks the circular link.

❓ Predict Output

advanced

Output after Traversing Circular Singly Linked List with One Node

What is the output of the print function when the circular singly linked list contains only one node with value 42?

DSA C++

#include <iostream>
struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class CircularSinglyLinkedList {
public:
    Node* tail;
    CircularSinglyLinkedList() : tail(nullptr) {}

    void insert(int val) {
        Node* newNode = new Node(val);
        if (!tail) {
            tail = newNode;
            tail->next = tail;
        } else {
            newNode->next = tail->next;
            tail->next = newNode;
            tail = newNode;
        }
    }

    void print() {
        if (!tail) return;
        Node* temp = tail->next;
        do {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        } while (temp != tail->next);
        std::cout << "null" << std::endl;
    }
};

int main() {
    CircularSinglyLinkedList list;
    list.insert(42);
    list.print();
    return 0;
}

A 42 -> 42 -> null

B 42 -> null

C null

D 42

💡 Hint

The print function prints nodes until it reaches the start node again, printing each node once.

With one node, the print function prints its data once followed by '-> null'.

🧠 Conceptual

expert

Why Use Circular Singly Linked List Instead of Singly Linked List?

Which of the following is the main advantage of using a circular singly linked list over a regular singly linked list?

A It allows traversal from any node back to itself without null checks

B It uses less memory per node than a singly linked list

C It automatically sorts the elements in ascending order

D It prevents duplicate values from being inserted

💡 Hint

Think about what happens when you reach the end of the list in both types.

In a circular singly linked list, the last node points back to the first node, allowing continuous traversal without encountering null, unlike a regular singly linked list.

Practice

1. What is a key characteristic of a circular singly linked list compared to a regular singly linked list?

easy

A. It uses an array internally to store nodes.

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

C. It cannot be traversed starting from the head node.

D. The last node points back to the first node, forming a circle.

Solution

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

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

2. Step 2: Compare with other linked lists

   Unlike doubly linked lists (which have two pointers) or arrays, circular singly linked lists have a single pointer per node and form a circle.

3. Final Answer:

   The last node points back to the first node, forming a circle. -> Option D

4. Quick Check:

   Circular list = last node points to first node [OK]

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

Common Mistakes:

• Thinking circular means two pointers per node
• Confusing with doubly linked list
• Assuming it uses arrays internally

2. Which of the following is the correct way to declare a node structure for a circular singly linked list in C++?

easy

A. struct Node { int data; int next; }; // Incorrect pointer type

B. struct Node { int data; Node* prev; Node* next; }; // Doubly linked list node

C. struct Node { int data; Node* next; }; // Correct declaration

D. struct Node { int data; Node next; }; // Incorrect pointer usage

Solution

1. Step 1: Identify the correct node structure for singly linked list

   A singly linked list node has data and a pointer to the next node. The pointer type must be Node*.

2. Step 2: Check each option

   struct Node { int data; Node* next; }; // Correct declaration correctly declares Node* next. struct Node { int data; Node* prev; Node* next; }; // Doubly linked list node has an extra prev pointer (doubly linked list). struct Node { int data; int next; }; // Incorrect pointer type uses int next which is wrong type. struct Node { int data; Node next; }; // Incorrect pointer usage uses Node next which is not a pointer.

3. Final Answer:

   struct Node { int data; Node* next; }; -> Option C

4. Quick Check:

   Single pointer to next node = correct node structure [OK]

Hint: Node must have pointer to next node only [OK]

Common Mistakes:

• Using non-pointer type for next
• Adding prev pointer for singly linked list
• Declaring next as object instead of pointer

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

struct Node {
    int data;
    Node* next;
};

int main() {
    Node* head = new Node{1, nullptr};
    Node* second = new Node{2, nullptr};
    Node* third = new Node{3, nullptr};

    head->next = second;
    second->next = third;
    third->next = head; // circular link

    Node* temp = head;
    for (int i = 0; i < 5; i++) {
        std::cout << temp->data << " ";
        temp = temp->next;
    }
    return 0;
}

medium

A. 1 2 3 1 2

B. 1 2 3 3 3

C. 1 2 3 4 5

D. 1 2 3 1 1

Solution

1. Step 1: Understand the circular link setup

   The last node (third) points back to head, so the list loops: 1 -> 2 -> 3 -> 1 -> ...

2. Step 2: Trace the print loop for 5 iterations

   Starting at head (1), print 1, move to 2, print 2, move to 3, print 3, move to 1, print 1, move to 2, print 2.

3. Final Answer:

   1 2 3 1 2 -> Option A

4. Quick Check:

   Loop prints nodes in circle: 1 2 3 1 2 [OK]

Hint: Circular list repeats nodes after last one [OK]

Common Mistakes:

• Assuming list ends after 3 nodes
• Printing wrong data due to pointer errors
• Confusing circular with linear list output

4. Identify the error in the following code that attempts to create a circular singly linked list with one node:

struct Node {
    int data;
    Node* next;
};

int main() {
    Node* head = new Node{10, nullptr};
    head->next = nullptr; // Intended to make circular
    return 0;
}

medium

A. Memory leak due to missing delete statement.

B. head->next should point to head, not nullptr, to form a circular list.

C. Using nullptr for next is correct for circular list.

D. Node declaration is missing a constructor.

Solution

1. Step 1: Check how circular link is formed

   For a circular singly linked list with one node, the node's next pointer must point to itself.

2. Step 2: Identify the mistake in the code

   The code sets head->next = nullptr, which breaks the circular property.

3. Final Answer:

   head->next should point to head, not nullptr, to form a circular list. -> Option B

4. Quick Check:

   One node circular list: next points to itself [OK]

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

Common Mistakes:

• Setting next to nullptr instead of self
• Confusing circular with linear list
• Ignoring memory management issues (not relevant here)

5. You want to insert a new node with value 4 at the end of an existing circular singly linked list with nodes 1 -> 2 -> 3 -> back to 1. Which of the following code snippets correctly performs this insertion?

hard

A. Node* newNode = new Node{4, head};
Node* temp = head;
while (temp->next != head) temp = temp->next;
temp->next = newNode;

B. Node* newNode = new Node{4, nullptr};
Node* temp = head;
while (temp->next != nullptr) temp = temp->next;
temp->next = newNode;
newNode->next = head;

C. Node* newNode = new Node{4, head};
head->next = newNode;

D. Node* newNode = new Node{4, nullptr};
newNode->next = head;
head = newNode;

Solution

1. Step 1: Understand insertion at end in circular singly linked list

   To insert at end, find last node (whose next points to head), then link new node to head and last node to new node.

2. Step 2: Analyze each option

   Node* newNode = new Node{4, head}; Node* temp = head; while (temp->next != head) temp = temp->next; temp->next = newNode; correctly creates new node pointing to head, finds last node by looping until temp->next == head, then sets last node's next to new node. Node* newNode = new Node{4, nullptr}; Node* temp = head; while (temp->next != nullptr) temp = temp->next; temp->next = newNode; newNode->next = head; incorrectly checks for nullptr which does not exist in circular list. Node* newNode = new Node{4, head}; head->next = newNode; incorrectly sets head->next to new node, breaking list. Node* newNode = new Node{4, nullptr}; newNode->next = head; head = newNode; changes head pointer incorrectly and does not update last node's next.

3. Final Answer:

   Node* newNode = new Node{4, head}; Node* temp = head; while (temp->next != head) temp = temp->next; temp->next = newNode; -> Option A

4. Quick Check:

   Find last node by next == head, link new node to head, last node to new node [OK]

Hint: Loop until next points to head to find last node [OK]

Common Mistakes:

• Checking for nullptr in circular list
• Not updating last node's next pointer
• Incorrectly changing head pointer