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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after inserting nodes at the beginning

What is the printed state of the circular linked list after inserting 10, then 20, then 30 at the beginning?

DSA C++

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

Node* insertAtBeginning(Node* head, int data) {
    Node* newNode = new Node{data, nullptr};
    if (!head) {
        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) return;
    Node* temp = head;
    do {
        std::cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != head);
    std::cout << "null" << std::endl;
}

int main() {
    Node* head = nullptr;
    head = insertAtBeginning(head, 10);
    head = insertAtBeginning(head, 20);
    head = insertAtBeginning(head, 30);
    printList(head);
    return 0;
}

A 30 -> 10 -> 20 -> null

B 20 -> 30 -> 10 -> null

C 30 -> 20 -> 10 -> null

D 10 -> 20 -> 30 -> null

💡 Hint

Remember that inserting at the beginning means the new node becomes the new head.

Each insertion at the beginning adds a new node before the current head and updates the head pointer. The last inserted node is the head, so the list prints starting from 30, then 20, then 10, then loops back.

❓ Predict Output

intermediate

Output after inserting a single node in an empty list

What is the printed state of the circular linked list after inserting only one node with value 5 at the beginning?

DSA C++

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

Node* insertAtBeginning(Node* head, int data) {
    Node* newNode = new Node{data, nullptr};
    if (!head) {
        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) return;
    Node* temp = head;
    do {
        std::cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != head);
    std::cout << "null" << std::endl;
}

int main() {
    Node* head = nullptr;
    head = insertAtBeginning(head, 5);
    printList(head);
    return 0;
}

A 5 -> null

B 5 -> 5 -> null

C null

D Error: Null pointer dereference

💡 Hint

A single node in a circular linked list points to itself.

When the list is empty, the new node points to itself, so printing starts and ends at that node, showing just one value.

🔧 Debug

advanced

Identify the error in the insertion code

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

DSA C++

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

A Segmentation fault due to null pointer dereference.

B Compilation error due to missing semicolon.

C No error, code works correctly.

D The list will become linear, not circular, causing infinite loop in traversal.

💡 Hint

Check what happens when the list is empty and how the new node's next pointer is set.

When the list is empty, newNode->next is set to nullptr instead of pointing to itself, breaking the circular property. Traversing the list will not loop back, causing infinite loops or crashes.

❓ Predict Output

advanced

Output after multiple insertions and one deletion

Given the code inserts 1, 2, 3 at beginning and then deletes the node with value 2, what is the printed list?

DSA C++

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

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

Node* deleteNode(Node* head, int key) {
    if (!head) return nullptr;
    if (head->data == key && head->next == head) {
        delete head;
        return nullptr;
    }
    Node* curr = head;
    Node* prev = nullptr;
    while (curr->data != key) {
        prev = curr;
        curr = curr->next;
        if (curr == head) return head;
    }
    if (curr == head) {
        prev = head;
        while (prev->next != head) prev = prev->next;
        head = curr->next;
        prev->next = head;
        delete curr;
    } else {
        prev->next = curr->next;
        delete curr;
    }
    return head;
}

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

int main() {
    Node* head = nullptr;
    head = insertAtBeginning(head, 1);
    head = insertAtBeginning(head, 2);
    head = insertAtBeginning(head, 3);
    head = deleteNode(head, 2);
    printList(head);
    return 0;
}

A 1 -> 3 -> null

B 3 -> 1 -> null

C 3 -> 2 -> 1 -> null

D 2 -> 3 -> 1 -> null

💡 Hint

After deletion, the node with value 2 is removed, and the list remains circular.

Insertion order makes list: 3 -> 2 -> 1 -> null. Deleting 2 removes that node, so list is 3 -> 1 -> null.

🧠 Conceptual

expert

Why is updating the last node's next pointer necessary when inserting at beginning?

In a circular linked list, when inserting a new node at the beginning, why must we update the last node's next pointer to the new node?

A To maintain the circular link so the last node points to the new head, preserving the loop.

B To free the memory of the old head node.

C To sort the list in ascending order automatically.

D To prevent the new node from pointing to itself.

💡 Hint

Think about what keeps the list circular.

The last node must point to the new head to keep the circular structure intact. Without this, the list breaks and is no longer circular.

Practice

1. What happens when you insert a new node at the beginning of a circular linked list?

easy

A. The new node replaces the last node in the list.

B. The new node is added at the end of the list, breaking the circular link.

C. The new node becomes the head and points to the old head, maintaining the circular link.

D. The list becomes linear instead of circular.

Solution

1. Step 1: Understand the circular linked list structure

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

2. Step 2: Insert new node at beginning

   The new node is linked to the current head, and the last node's next pointer is updated to this new node, making it the new head.

3. Final Answer:

   The new node becomes the head and points to the old head, maintaining the circular link. -> Option C

4. Quick Check:

   New head points to old head, circle intact = A [OK]

Hint: New head points to old head; last node links to new head [OK]

Common Mistakes:

• Forgetting to update last node's next pointer
• Breaking the circular link by not linking last node
• Replacing last node instead of adding new head

2. Which of the following is the correct syntax to create a new node and insert it at the beginning of a circular linked list in C++?

easy

A. Node* newNode = new Node(data); newNode->next = head; last->next = newNode; head = newNode;

B. Node newNode(data); newNode.next = head; head = &newNode;

C. Node* newNode = new Node(data); newNode->next = head; head = newNode;

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

Solution

1. Step 1: Create new node dynamically

   Use 'new' keyword to allocate memory for new node: Node* newNode = new Node(data);

2. Step 2: Link new node and update pointers

   Set newNode->next to current head, update last node's next to newNode, then update head to newNode.

3. Final Answer:

   Node* newNode = new Node(data); newNode->next = head; last->next = newNode; head = newNode; -> Option A

4. Quick Check:

   Dynamic node + last->next update + head change = C [OK]

Hint: Update last node's next before changing head [OK]

Common Mistakes:

• Not updating last node's next pointer
• Using stack allocation for node causing scope issues
• Assigning head before updating last->next

3. What will be the output of the following code snippet after inserting 10 at the beginning of the circular linked list?

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

Node* head = new Node{20, nullptr};
head->next = head;

// Insert 10 at beginning
Node* newNode = new Node{10, nullptr};
Node* temp = head;
while(temp->next != head) {
  temp = temp->next;
}
newNode->next = head;
temp->next = newNode;
head = newNode;

// Print list
Node* curr = head;
do {
  std::cout << curr->data << " -> ";
  curr = curr->next;
} while(curr != head);
std::cout << "null";

medium

A. 20 -> null

B. 20 -> 10 -> null

C. 10 -> null

D. 10 -> 20 -> null

Solution

1. Step 1: Initial list and insertion

   Initially, list has one node with data 20 pointing to itself. New node 10 is inserted before 20, updating last node's next to new node and head to new node.

2. Step 2: Print traversal

   Traversal starts at head (10), prints 10, moves to 20, prints 20, then back to head stops loop.

3. Final Answer:

   10 -> 20 -> null -> Option D

4. Quick Check:

   New head 10 followed by 20 = A [OK]

Hint: Head changes to new node; print starts from new head [OK]

Common Mistakes:

• Not updating last node's next pointer
• Printing stops too early or infinite loop
• Confusing order of nodes after insertion

4. Identify the error in the following code that attempts to insert a node at the beginning of a circular linked list:

void insertAtBeginning(Node*& head, int data) {
  Node* newNode = new Node{data, nullptr};
  newNode->next = head;
  head = newNode;
  Node* temp = head;
  while(temp->next != head) {
    temp = temp->next;
  }
  temp->next = head;
}

medium

A. The last node's next pointer is updated after changing head, causing infinite loop.

B. The new node is not linked to the old head.

C. The while loop condition is incorrect and never executes.

D. The new node is created on stack instead of heap.

Solution

1. Step 1: Analyze pointer updates order

   The code updates head to newNode before finding the last node, so temp starts at newNode, causing the while loop to never find the last node correctly.

2. Step 2: Consequence of wrong order

   Because last node is not found properly, temp->next = head may not update the correct node, breaking the circular link or causing infinite loops.

3. Final Answer:

   The last node's next pointer is updated after changing head, causing infinite loop. -> Option A

4. Quick Check:

   Update last node before changing head to avoid loop [OK]

Hint: Update last node's next before changing head [OK]

Common Mistakes:

• Changing head before updating last node's next
• Not handling empty list case
• Incorrect while loop condition

5. You have a circular linked list with nodes: 5 -> 15 -> 25 -> (back to 5). You want to insert 1 at the beginning. Which sequence of pointer updates correctly inserts the new node and maintains the circular structure?

hard

A. Create new node with data 1; set newNode->next = head; update head = newNode; find last node and set last->next = newNode;

B. Create new node with data 1; find last node; set last->next = newNode; set newNode->next = head; update head = newNode;

C. Create new node with data 1; update head = newNode; set newNode->next = head; find last node and set last->next = newNode;

D. Create new node with data 1; set newNode->next = nullptr; update head = newNode; find last node and set last->next = newNode;

Solution

1. Step 1: Create new node and find last node

   Create new node with data 1. Traverse list to find last node (node pointing back to head).

2. Step 2: Update pointers in correct order

   Set last->next to newNode, newNode->next to head, then update head to newNode to maintain circular link.

3. Final Answer:

   Create new node with data 1; find last node; set last->next = newNode; set newNode->next = head; update head = newNode; -> Option B

4. Quick Check:

   Last node updated before head change = B [OK]

Hint: Update last node's next before changing head [OK]

Common Mistakes:

• Changing head before updating last node's next
• Setting newNode->next to nullptr breaks circular link
• Incorrect order of pointer updates