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

Concept Flow - Insert at End of Circular Linked List

Create new node

↓

Is list empty?

Yes→new_node.next = new_node

↓

head = new_node

↓

Start at head

↓

Traverse until current.next == head

↓

Set current.next = new_node

↓

new_node.next = head

↓

Done

Create a new node, check if list is empty. If empty, point new node to itself. Otherwise, traverse to last node, link last node to new node, and new node back to head.

Execution Sample

DSA C++

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

// Insert at end of circular linked list
void insertEnd(Node*& head, int val) {
  Node* new_node = new Node{val, nullptr};
  if (!head) {
    new_node->next = new_node;
    head = new_node;
    return;
  }
  Node* current = head;
  while (current->next != head) {
    current = current->next;
  }
  current->next = new_node;
  new_node->next = head;
}

This code inserts a new node with value val at the end of a circular linked list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	empty	new_node->next = nullptr	List is empty
2	Check if head is null	empty	head == nullptr (True)	No nodes, head is null
3	Set new_node->next = new_node (self loop)	1 node	new_node->next = new_node	┌────────┐ │ data:10│ │ next:──┼──→ (points to itself) └────────┘ head → new_node
4	Set head = new_node	1 node	head points to new_node	┌────────┐ │ data:10│ │ next:──┼──→ (points to itself) └────────┘ head → new_node
5	Insert 20: Create new node with data=20	1 node	new_node->next = nullptr	┌────────┐ │ data:10│ │ next:──┼──→ (points to itself) └────────┘ head → node10
6	Traverse to last node (node with next=head)	1 node	current = node10	┌────────┐ │ data:10│ │ next:──┼──→ (points to itself) └────────┘ head → node10
7	Set current->next = new_node (node10.next = node20)	2 nodes	node10.next → node20	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:──┼──→ (to head) └────────┘ └────────┘ head → node10
8	Set new_node->next = head (node20.next = node10)	2 nodes	node20.next → node10	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ head → node10
9	Insert 30: Create new node with data=30	2 nodes	new_node->next = nullptr	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:──┼──→ (to head) └────────┘ └────────┘ head → node10
10	Traverse to last node (node20.next == head)	2 nodes	current moves: node10 → node20	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:──┼──→ (to head) └────────┘ └────────┘ head → node10
11	Set current->next = new_node (node20.next = node30)	3 nodes	node20.next → node30	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ (to head) └────────┘ └────────┘ └────────┘ head → node10
12	Set new_node->next = head (node30.next = node10)	3 nodes	node30.next → node10	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ └────────┘ └────────┘ └────────┘ head → node10
13	End of insertions	3 nodes	No pointer changes	Final circular list: ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ (to node10) └────────┘ └────────┘ └────────┘ head → node10

💡 Traversal stops when current->next == head, ensuring insertion at end.

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 11	Final
head	nullptr	node10	node10	node10	node10
new_node	nullptr	node10	node20	node30	node30
current	nullptr	nullptr	node10	node20	node20
List Size	0	1	2	3	3

Key Moments - 3 Insights

Why do we set new_node->next = new_node when the list is empty?

Because in a circular linked list with one node, the node points to itself to maintain the circular structure. See execution_table step 3.

Why does the traversal stop when current->next == head, not current == nullptr?

Because in circular lists, there is no nullptr at the end; the last node points back to head. Stopping at current->next == head means current is the last node. See execution_table step 6 and 10.

How do we maintain the circular link after inserting the new node?

We set current->next to new_node and new_node->next back to head, closing the circle. See execution_table steps 7-8 and 11-12.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what does new_node->next point to?

A It points to itself (new_node)

B It points to nullptr

C It points to head

D It points to the last node

💡 Hint

Check the Pointer Changes and Visual State columns at step 3.

At which step does the traversal pointer 'current' move from node10 to node20?

A Step 6

B Step 10

C Step 7

D Step 11

💡 Hint

Look at the Pointer Changes column where current moves nodes.

If the list was initially empty, what would be the list size after inserting one node?

A 2

B 0

C 1

D Undefined

💡 Hint

See variable_tracker for List Size after step 3.

Concept Snapshot

Insert at End of Circular Linked List:
- Create new node
- If list empty: new_node->next = new_node, head = new_node
- Else traverse to last node (current->next == head)
- Set current->next = new_node
- Set new_node->next = head
- Maintains circular structure

Full Transcript

To insert at the end 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 new node. If not empty, start at head and traverse until you find the last node whose next points back to head. Then, set this last node's next to the new node, and set the new node's next back to head. This keeps the circular structure intact. The traversal stops when current->next equals head, indicating the last node. The new node is linked at the end, and the circle is closed by pointing new_node->next to head.

Practice

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

easy

A. The new node points to itself, becoming the only node in the list.

B. The new node points to null, ending the list.

C. The new node is discarded because the list is empty.

D. The new node points to the head, but the list remains empty.

Solution

1. Step 1: Understand circular linked list empty state

   When the list is empty, there is no node, so the new node must point to itself to form a circle.

2. Step 2: Insert new node and update pointers

   The new node's next pointer is set to itself, making it the only node and the head of the list.

3. Final Answer:

   The new node points to itself, becoming the only node in the list. -> Option A

4. Quick Check:

   Empty list insertion creates a self-pointing node [OK]

Hint: New node points to itself if list is empty [OK]

Common Mistakes:

• Setting next pointer to null instead of itself
• Not updating the head pointer
• Assuming list remains empty after insertion

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

easy

A. newNode->next = head; tail->next = newNode; tail = newNode;

B. newNode->next = nullptr; tail->next = newNode; tail = newNode;

C. newNode->next = tail; head->next = newNode; tail = newNode;

D. newNode->next = head; head->next = newNode; tail = newNode;

Solution

1. Step 1: Set new node's next to head

   In a circular linked list, the last node points to the head, so newNode->next = head.

2. Step 2: Update current tail's next and tail pointer

   Set tail->next to newNode to link the last node to new node, then update tail to newNode.

3. Final Answer:

   newNode->next = head; tail->next = newNode; tail = newNode; -> Option A

4. Quick Check:

   New node points to head, tail updated [OK]

Hint: Tail's next must point to new node, new node points to head [OK]

Common Mistakes:

• Setting newNode->next to nullptr instead of head
• Updating head->next instead of tail->next
• Not updating tail pointer after insertion

3. Given the circular linked list with nodes 10 -> 20 -> 30 -> (back to 10), what will be the list after inserting 40 at the end?

medium

A. 40 -> 10 -> 20 -> 30 -> (back to 40)

B. 10 -> 20 -> 30 -> (back to 40)

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

D. 10 -> 20 -> 30 -> 40 -> (back to 10)

Solution

1. Step 1: Identify current circular list structure

   The list is 10 -> 20 -> 30, and 30 points back to 10 forming a circle.

2. Step 2: Insert 40 at end and update pointers

   New node 40 points to head (10), old tail (30) points to 40, making list 10 -> 20 -> 30 -> 40 -> back to 10.

3. Final Answer:

   10 -> 20 -> 30 -> 40 -> (back to 10) -> Option D

4. Quick Check:

   New node added at end, circle maintained [OK]

Hint: New node points to head, old tail points to new node [OK]

Common Mistakes:

• Breaking the circle by pointing last node to null
• Inserting new node at start instead of end
• Not updating tail pointer

4. What is wrong with this code snippet for inserting at the end of a circular linked list?

void insertEnd(Node*& tail, int data) {
  Node* newNode = new Node(data);
  newNode->next = tail->next;
  tail = newNode;
}

medium

A. It sets newNode->next to null instead of head.

B. It deletes the old tail node accidentally.

C. It does not update the old tail's next pointer to newNode.

D. It inserts the new node at the beginning instead of the end.

Solution

1. Step 1: Check pointer updates in code

   The code sets newNode->next to tail->next (head), but does not update tail->next to newNode.

2. Step 2: Identify missing link update

   Without updating old tail's next pointer, the list breaks the circle and newNode is not linked properly.

3. Final Answer:

   It does not update the old tail's next pointer to newNode. -> Option C

4. Quick Check:

   Old tail's next must point to new node [OK]

Hint: Always update old tail's next to new node [OK]

Common Mistakes:

• Forgetting to update old tail's next pointer
• Setting newNode->next incorrectly
• Not updating tail pointer after insertion

5. You have a circular linked list with nodes 5 -> 15 -> 25 -> (back to 5). You want to insert a new node with value 35 at the end. After insertion, you mistakenly forget to update the tail pointer to the new node. What will be the effect on the list?

hard

A. The list will have 5 -> 15 -> 25 -> (back to 5) without 35.

B. The list will have 5 -> 15 -> 25 -> 35 -> (back to 5), but tail still points to 25.

C. The new node 35 will not be linked and will be lost.

D. The list will break and become linear ending at 25.

Solution

1. Step 1: Insert new node and link old tail

   New node 35 is linked after 25, and points back to head (5), so list is 5 -> 15 -> 25 -> 35 -> back to 5.

2. Step 2: Tail pointer not updated

   Tail still points to 25, so operations relying on tail may behave incorrectly, but list structure is intact.

3. Final Answer:

   The list will have 5 -> 15 -> 25 -> 35 -> (back to 5), but tail still points to 25. -> Option B

4. Quick Check:

   Tail pointer must update, else points to old last node [OK]

Hint: Tail pointer must update to new node after insertion [OK]

Common Mistakes:

• Assuming list breaks without tail update
• Thinking new node is lost if tail not updated
• Confusing tail pointer with node links