Insert at Beginning of Circular Linked List in DSA C++ - Execution Trace

Concept Flow - Insert at Beginning of Circular Linked List

Create new node

↓

Is list empty?

Yes→new_node.next = new_node

↓

head = new_node

↓

Find last node

↓

last_node.next = new_node

↓

new_node.next = head

↓

head = new_node

↓

Done

Create a new node, if list is empty point it to itself. Otherwise, find last node, update pointers to insert new node before head, then update head.

Execution Sample

DSA C++

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

// Insert at beginning
void insertBegin(Node*& head, int val) {
  Node* new_node = new Node{val, nullptr};
  if (!head) {
    new_node->next = new_node;
    head = new_node;
    return;
  }
  Node* last = head;
  while (last->next != head) last = last->next;
  last->next = new_node;
  new_node->next = head;
  head = new_node;
}

This code inserts a new node at the beginning of a circular linked list, updating pointers to keep the circle intact.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	empty	new_node created, next=nullptr	∅
2	Check if list empty	empty	head is nullptr, so list empty	∅
3	Set new_node->next = new_node	1 node	new_node.next → new_node (self-loop)	┌────────┐ │ data:10│ │ next:─┐│ └───────┘│ ↑─────┘ (head)
4	Set head = new_node	1 node	head → new_node	┌────────┐ │ data:10│ │ next:─┐│ └───────┘│ ↑─────┘ (head)
5	Insert 20 at beginning: create new_node with data=20	1 node	new_node created, next=nullptr	┌────────┐ │ data:10│ │ next:─┐│ └───────┘│ ↑─────┘ (head)
6	List not empty, find last node	1 node	last starts at head (10), last->next == head (10), stop	┌────────┐ │ data:10│ │ next:─┐│ └───────┘│ ↑─────┘ (head, last)
7	Set last->next = new_node	2 nodes	10.next → 20	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ next:─┐│ │ next:? │ └───────┘│ └───────┘ ↑─────┘ (head)
8	Set new_node->next = head	2 nodes	20.next → 10	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ next:─┐│ │ next:─┐│ └───────┘│ └───────┘│ ↑─────┘ ↑───┘ (head) (new_node)
9	Set head = new_node	2 nodes	head → 20	┌────────┐ ┌────────┐ │ data:20│───→│ data:10│ │ next:─┐│ │ next:─┐│ └───────┘│ └───────┘│ ↑─────┘ ↑───┘ (head) (last)
10	Insert 30 at beginning: create new_node with data=30	2 nodes	new_node created, next=nullptr	┌────────┐ ┌────────┐ │ data:20│───→│ data:10│ │ next:─┐│ │ next:─┐│ └───────┘│ └───────┘│ ↑─────┘ ↑───┘ (head) (last)
11	Find last node starting at head (20)	2 nodes	last=10, last->next=20 (head), stop	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ next:? │ │ next:? │ │ next:? │ └────────┘ └────────┘ └────────┘ new_node head last
12	Set last->next = new_node	3 nodes	10.next → 30	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ next:? │ │ next:? │ │ next:─┐│ └────────┘ └────────┘ └───────┘│ ↑───┘
13	Set new_node->next = head	3 nodes	30.next → 20	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│───→│ data:20│───→│ data:10│ │ next:─┐│ │ next:─┐│ │ next:─┐│ └───────┘│ └───────┘│ └───────┘│ ↑──────────────┘ (new_node)
14	Set head = new_node	3 nodes	head → 30	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│───→│ data:20│───→│ data:10│ │ next:─┐│ │ next:─┐│ │ next:─┐│ └───────┘│ └───────┘│ └───────┘│ ↑─────┘ ↑ ↑ (head) (middle) (last)
15	End of insertions	3 nodes	Pointers updated, circular list intact	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│───→│ data:20│───→│ data:10│ │ next:─┐│ │ next:─┐│ │ next:─┐│ └───────┘│ └───────┘│ └───────┘│ ↑─────┘ ↑ ↑ (head) (middle) (last)

💡 Insertion ends after updating head and last node pointers to maintain circular link.

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 9	After Step 12	After Step 14	Final
head	nullptr	10	10	20	20	30	30
new_node	nullptr	10	20	20	30	30	30
last	nullptr	nullptr	10	10	10	10	10
List Size	0	1	2	2	3	3	3

Key Moments - 3 Insights

Why do we need to find the last node before inserting at the beginning?

Because the last node's next pointer must point to the new head to keep the list circular, as shown in steps 6-7 and 11-12 in the execution_table.

What happens if the list is empty when inserting the first node?

The new node points to itself (self-loop) and becomes the head, as shown in steps 2-4 where new_node.next = new_node and head = new_node.

Why do we update head only after fixing last node's next pointer?

Updating head first would lose reference to the original list needed to find the last node. The execution_table shows we find last node first, update its next, then update head (steps 6-9 and 11-14).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, which pointer is changed?

A new_node's next pointer is set to nullptr

B head pointer is updated to new_node

C last node's next pointer is updated to new_node

D head pointer is set to nullptr

💡 Hint

Check the 'Pointer Changes' column at step 7 in execution_table.

At which step does the list first become circular with one node pointing to itself?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Visual State' and 'Pointer Changes' columns at step 3.

If we skip finding the last node before insertion, what will happen?

A The list will remain circular and correct

B The last node's next pointer will not point to new head, breaking circularity

C The new node will point to nullptr

D The head pointer will not change

💡 Hint

Refer to key_moments about why last node pointer update is necessary.

Concept Snapshot

Insert at Beginning of Circular Linked List:
- Create new node
- If empty: new_node.next = new_node, head = new_node
- Else: find last node
- last_node.next = new_node
- new_node.next = head
- head = new_node
Maintains circular link with new node as head.

Full Transcript

To insert at the beginning of a circular linked list, first create a new node. If the list is empty, point the new node's next to itself and set head to this node. If not empty, find the last node by traversing until its next points to head. Update last node's next to the new node, set new node's next to the current head, then update head to the new node. This keeps the list circular with the new node at the start. The execution steps show pointer changes and the list's visual state after each operation, ensuring the circular structure is maintained.

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