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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting nodes in a circular singly linked list?

Consider the following C code that creates a circular singly linked list by inserting nodes at the end. What will be the printed output?

DSA C

#include <stdio.h>
#include <stdlib.h>

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head;
}

void printList(Node* head) {
    if (head == NULL) return;
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("null\n");
}

int main() {
    Node* head = NULL;
    insertEnd(&head, 10);
    insertEnd(&head, 20);
    insertEnd(&head, 30);
    printList(head);
    return 0;
}

A 20 -> 30 -> 10 -> null

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

C 10 -> 20 -> 30 -> null

D 10 -> 20 -> null

💡 Hint

Remember that in a circular singly linked list, the last node points back to the head, but printing stops when we reach the head again.

The printList function prints nodes starting from head and stops when it reaches head again. So it prints 10, 20, 30 and then stops, showing '10 -> 20 -> 30 -> null'.

🧠 Conceptual

intermediate

What is the key difference between a circular singly linked list and a normal singly linked list?

Choose the correct statement that best describes the difference between a circular singly linked list and a normal singly linked list.

A In a circular singly linked list, nodes have two pointers; in a normal singly linked list, nodes have one pointer.

B In a circular singly linked list, the last node points back to the head; in a normal singly linked list, the last node points to NULL.

C A circular singly linked list can only store integers; a normal singly linked list can store any data type.

D A circular singly linked list is always sorted; a normal singly linked list is not.

💡 Hint

Think about where the last node points in each list type.

The main difference is that in a circular singly linked list, the last node's next pointer points back to the head node, forming a circle. In a normal singly linked list, the last node points to NULL.

🔧 Debug

advanced

Why does this circular singly linked list insertion code cause an infinite loop?

Examine the code below. It tries to insert a node at the end of a circular singly linked list but causes an infinite loop. What is the bug?

DSA C

#include <stdio.h>
#include <stdlib.h>

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head;
}

void printList(Node* head) {
    if (head == NULL) return;
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("null\n");
}

int main() {
    Node* head = NULL;
    insertEnd(&head, 5);
    insertEnd(&head, 15);
    insertEnd(&head, 25);
    printList(head);
    return 0;
}

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

B The newNode->next should be set to NULL instead of *head.

C The createNode function does not allocate memory correctly.

D The printList function should use a while loop instead of do-while.

💡 Hint

In a circular list, the last node's next is not NULL.

The bug is in the while loop condition inside insertEnd. It checks for temp->next != NULL, but in a circular list, the last node points back to head, not NULL. So the loop never ends, causing an infinite loop.

❓ Predict Output

advanced

What is the output after deleting a node from a circular singly linked list?

Given the code below that deletes the node with value 20 from a circular singly linked list, what will be the printed output?

DSA C

#include <stdio.h>
#include <stdlib.h>

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        newNode->next = newNode;
        return;
    }
    Node* temp = *head;
    while (temp->next != *head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = *head;
}

void deleteNode(Node** head, int key) {
    if (*head == NULL) return;
    Node *curr = *head, *prev = NULL;
    while (curr->data != key) {
        if (curr->next == *head) return; // key not found
        prev = curr;
        curr = curr->next;
    }
    if (curr == *head) {
        Node* temp = *head;
        while (temp->next != *head) {
            temp = temp->next;
        }
        if (curr->next == *head) {
            free(curr);
            *head = NULL;
        } else {
            temp->next = curr->next;
            *head = curr->next;
            free(curr);
        }
    } else {
        prev->next = curr->next;
        free(curr);
    }
}

void printList(Node* head) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("null\n");
}

int main() {
    Node* head = NULL;
    insertEnd(&head, 10);
    insertEnd(&head, 20);
    insertEnd(&head, 30);
    deleteNode(&head, 20);
    printList(head);
    return 0;
}

A 10 -> 30 -> null

B 10 -> 20 -> 30 -> null

C 20 -> 30 -> null

D List is empty

💡 Hint

After deleting 20, the list should contain the remaining nodes in order.

The node with data 20 is deleted. The list now contains 10 and 30 linked circularly. The printList prints '10 -> 30 -> null'.

🧠 Conceptual

expert

What is the time complexity of inserting a node at the end of a circular singly linked list without a tail pointer?

Consider a circular singly linked list with only a head pointer (no tail pointer). What is the time complexity of inserting a new node at the end of the list?

A O(log n), because the list is circular.

B O(1), because you can insert directly after the head.

C O(n^2), because each insertion requires traversing the entire list multiple times.

D O(n), because you must traverse the list to find the last node.

💡 Hint

Think about how to find the last node without a tail pointer.

Without a tail pointer, to insert at the end, you must traverse all nodes to find the last node, which takes O(n) time.