Insert at Beginning of Circular Linked List in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting a node at the beginning

What is the printed state of the circular linked list after inserting 10 at the beginning of the list containing 20 -> 30 -> 40?

DSA C

/* Circular linked list node structure */
#include <stdio.h>
#include <stdlib.h>

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

/* Function to insert at beginning */
Node* insertAtBeginning(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    if (head == NULL) {
        newNode->next = newNode;
        return newNode;
    }
    Node* temp = head;
    while (temp->next != head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = head;
    return newNode;
}

/* Function to print circular linked list */
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 = (Node*)malloc(sizeof(Node));
    Node* second = (Node*)malloc(sizeof(Node));
    Node* third = (Node*)malloc(sizeof(Node));

    head->data = 20;
    second->data = 30;
    third->data = 40;

    head->next = second;
    second->next = third;
    third->next = head;

    head = insertAtBeginning(head, 10);
    printList(head);
    return 0;
}

A 10 -> 30 -> 40 -> 20 -> null

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

C 10 -> 20 -> 30 -> 40 -> null

D 20 -> 10 -> 30 -> 40 -> null

💡 Hint

Remember that in a circular linked list, the last node points back to the head. Inserting at the beginning means the new node becomes the new head.

The function inserts a new node before the current head and updates the last node's next pointer to the new node. Thus, the new node with data 10 becomes the head, followed by 20, 30, and 40.

🧠 Conceptual

intermediate

Understanding pointer updates in circular linked list insertion

Which pointer update is essential to maintain the circular nature of the list when inserting a new node at the beginning?

A Updating the new node's next pointer to point to the old head and the last node's next pointer to the new node

B Updating the new node's next pointer to NULL and the last node's next pointer to the new node

C Updating the last node's next pointer to NULL and the new node's next pointer to the old head

D Updating the old head's next pointer to the new node and the new node's next pointer to NULL

💡 Hint

Think about how the last node should point after insertion to keep the list circular.

To keep the list circular, the last node must point to the new head (new node), and the new node must point to the old head. This maintains the loop.

🔧 Debug

advanced

Identify the bug in this insertion code

What error will occur when running this code to insert at the beginning of a circular linked list?

DSA C

Node* insertAtBeginning(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = head;
    if (head == NULL) {
        head = newNode;
        return head;
    }
    Node* temp = head;
    while (temp->next != head) {
        temp = temp->next;
    }
    temp->next = newNode;
    return newNode;
}

A Infinite loop or segmentation fault due to incorrect loop condition

B No error, code runs correctly

C Memory leak due to missing free() calls

D Compilation error due to missing semicolon

💡 Hint

Check the loop condition for traversing the circular linked list.

The loop condition uses temp->next != NULL, but in a circular linked list, the last node points to head, not NULL. This causes an infinite loop or crash.

❓ Predict Output

advanced

Output after multiple insertions at beginning

What is the printed state of the circular linked list after inserting 50, then 40, then 30 at the beginning of an empty list?

DSA C

/* Insert multiple nodes at beginning */
#include <stdio.h>
#include <stdlib.h>

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

Node* insertAtBeginning(Node* head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    if (head == NULL) {
        newNode->next = newNode;
        return newNode;
    }
    Node* temp = head;
    while (temp->next != head) {
        temp = temp->next;
    }
    temp->next = newNode;
    newNode->next = head;
    return newNode;
}

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;
    head = insertAtBeginning(head, 50);
    head = insertAtBeginning(head, 40);
    head = insertAtBeginning(head, 30);
    printList(head);
    return 0;
}

A 50 -> 40 -> 30 -> null

B 30 -> 40 -> 50 -> null

C 40 -> 30 -> 50 -> null

D 30 -> 50 -> 40 -> null

💡 Hint

Each insertion at beginning makes the new node the head.

Inserting 50 first creates list: 50 -> null. Then inserting 40 at beginning: 40 -> 50 -> null. Then inserting 30 at beginning: 30 -> 40 -> 50 -> null.

🧠 Conceptual

expert

Time complexity of insertion at beginning in circular linked list

What is the time complexity of inserting a node at the beginning of a circular linked list when you only have a pointer to the head node?

A O(n^2) because of nested traversal

B O(1) because you can insert immediately at the head without traversal

C O(log n) because of binary search on nodes

D O(n) because you must traverse to the last node to update its next pointer

💡 Hint

Think about what pointer updates are needed and if you can access the last node directly.

To insert at beginning, you must update the last node's next pointer to the new node. Without a direct pointer to the last node, you must traverse the list, which takes O(n) time.