Insert at End of Circular Linked List in DSA Java - 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

No↓

Start at head

↓

Traverse until current.next == head

↓

Set current.next = new_node

↓

Set new_node.next = head

↓

Done

Insert a new node by creating it, then either initialize the list if empty or traverse to the last node and link the new node at the end pointing back to head.

Execution Sample

DSA Java

class Node {
  int data;
  Node next;
}

// Insert at end of circular linked list
Node insertEnd(Node head, int val) {
  Node newNode = new Node();
  newNode.data = val;
  newNode.next = null;

  if (head == null) {
    newNode.next = newNode;
    head = newNode;
    return head;
  }

  Node current = head;
  while (current.next != head) {
    current = current.next;
  }

  current.next = newNode;
  newNode.next = head;

  return 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=40	10 -> 20 -> 30 (circular)	newNode created with data=40, next=null	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ head └────────┘ └────────┘ └────────┘
2	Traverse to last node (node with data=30)	10 -> 20 -> 30 (circular)	current moves from head(10) → 20 → 30	┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ head └────────┘ └────────┘ └────────┘ head current
3	Set current.next = newNode	10 -> 20 -> 30 -> 40 (circular)	30.next changes from head to newNode	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:null│ └────────┘ └────────┘ └────────┘ └────────┘
4	Set newNode.next = head	10 -> 20 -> 30 -> 40 (circular)	newNode.next points to head (10)	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ head └────────┘ └────────┘ └────────┘ └────────┘
5	Insertion complete	10 -> 20 -> 30 -> 40 (circular)	Pointers stable, list circular	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:40│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ head └────────┘ └────────┘ └────────┘ └────────┘

💡 Insertion stops after newNode.next points to head, maintaining circular link.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
head	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)	Node(10)
current	null	null	Node(30)	Node(30)	Node(30)	Node(30)
newNode	null	Node(40)	Node(40)	Node(40)	Node(40)	Node(40)

Key Moments - 3 Insights

Why do we check current.next == head to find the last node?

Because in a circular linked list, the last node points back to head. So when current.next equals head, current is the last node. See execution_table step 2 where traversal stops at node with data 30.

What happens if the list is empty when inserting?

If empty, newNode.next points to itself and head is set to newNode, making a single-node circular list. This is shown in concept_flow under the 'Yes' branch of 'Is list empty?'.

Why must newNode.next point to head after insertion?

To maintain the circular property, the new last node must link back to head. This is shown in execution_table step 4 where newNode.next is set to head.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, where is the 'current' pointer located?

A At node with data 30

B At node with data 20

C At head node with data 10

D At newNode with data 40

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns in step 2 of execution_table.

At which step does the new node start pointing back to the head?

A Step 1

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Pointer Changes' column for when newNode.next is assigned.

If the list was empty, what would be the visual state after insertion?

A newNode.next points to null

B newNode.next points to itself, head points to newNode

C head remains null

D newNode.next points to head which is null

💡 Hint

Refer to concept_flow's 'Yes' branch for empty list insertion.

Concept Snapshot

Insert at End of Circular Linked List:
- Create new node
- If list empty: newNode.next = newNode; head = newNode
- Else traverse to last node (current.next == head)
- Set current.next = newNode
- Set newNode.next = head
- List remains circular with new node at end

Full Transcript

To insert at the end of a circular linked list, first create a new node with the given data. If the list is empty, point the new node's next to itself and set head to this new node, forming a single-node circular list. If not empty, start from head and traverse nodes until reaching the last node, identified when current.next points back to head. Then, set the last node's next pointer to the new node, and set the new node's next pointer back to head. This maintains the circular structure with the new node at the end. The pointers and nodes update step-by-step as shown in the execution table and pointer diagrams.

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 the head, but the list remains empty.

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

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

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

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 B

4. Quick Check:

   Empty list insertion = node points to itself [OK]

Hint: Empty circular list node points to itself [OK]

Common Mistakes:

• Setting new node's next to null
• Not updating head pointer
• Assuming list remains empty

2. Which of the following Java code snippets correctly inserts a new node at the end of a circular linked list?

easy

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

B. newNode.next = null; 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 is correct.

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

   Tail's next should point to newNode, and tail should be updated to newNode to maintain the list.

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: New node next = head, tail next = new node [OK]

Common Mistakes:

• Setting newNode.next to null
• Updating head.next instead of tail.next
• Not updating tail pointer

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

Node head = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
head.next = second;
second.next = third;
third.next = head;

Node newNode = new Node(40);
Node tail = third;
newNode.next = head;
tail.next = newNode;
tail = newNode;

medium

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

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

C. 10 -> 20 -> 30 -> 40 -> back to 10

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

Solution

1. Step 1: Understand initial list and insertion

   Initial list is 10 -> 20 -> 30 -> back to 10. Inserting 40 at end means 30's next points to 40, and 40 points to head (10).

2. Step 2: Update tail and next pointers

   After insertion, tail is updated to 40, and list becomes 10 -> 20 -> 30 -> 40 -> back to 10.

3. Final Answer:

   10 -> 20 -> 30 -> 40 -> back to 10 -> Option C

4. Quick Check:

   New node added at end, circular link maintained [OK]

Hint: New node next = head, tail next = new node [OK]

Common Mistakes:

• Not updating tail.next to new node
• Not updating tail pointer
• Breaking circular link

4. Identify the error in the following code snippet that inserts a node at the end of a circular linked list:

Node newNode = new Node(50);
newNode.next = null;
tail.next = newNode;
tail = newNode;
tail.next = head;

medium

A. Setting newNode.next to null breaks the circular link.

B. Not updating tail pointer causes list corruption.

C. tail.next should point to null, not newNode.

D. head pointer is incorrectly updated.

Solution

1. Step 1: Check newNode.next assignment

   Setting newNode.next to null breaks the circular property because last node must point to head.

2. Step 2: Verify tail.next and tail updates

   tail.next is set to newNode and tail updated correctly, but newNode.next should point to head, not null.

3. Final Answer:

   Setting newNode.next to null breaks the circular link. -> Option A

4. Quick Check:

   newNode.next must point to head, not null [OK]

Hint: Last node next must point to head, never null [OK]

Common Mistakes:

• Setting newNode.next to null
• Not maintaining circular link
• Confusing tail and head pointers

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 want to print the list starting from head. Which code snippet correctly performs insertion and prints the list?

Node head = new Node(5);
Node second = new Node(15);
Node third = new Node(25);
head.next = second;
second.next = third;
third.next = head;

Node newNode = new Node(35);
Node tail = third;
// Insert newNode at end
// Print list starting from head

hard

A. newNode.next = null;
tail.next = newNode;
tail = newNode;
Node temp = head;
while(temp != null) { System.out.print(temp.data + " -> "); temp = temp.next; }
System.out.print("null");

B. newNode.next = head;
tail.next = newNode;
tail = newNode;
Node temp = tail;
do { System.out.print(temp.data + " -> "); temp = temp.next; } while(temp != tail);
System.out.print("null");

C. newNode.next = head;
head.next = newNode;
tail = newNode;
Node temp = head;
do { System.out.print(temp.data + " -> "); temp = temp.next; } while(temp != head);
System.out.print("null");

D. newNode.next = head;
tail.next = newNode;
tail = newNode;
Node temp = head;
do { System.out.print(temp.data + " -> "); temp = temp.next; } while(temp != head);
System.out.print("null");

Solution

1. Step 1: Insert newNode correctly at end

   Set newNode.next to head, update tail.next to newNode, and update tail to newNode to maintain circular list.

2. Step 2: Print list starting from head using do-while

   Use a do-while loop starting at head, printing each node until we return to head, ensuring all nodes are printed once.

3. Final Answer:

   newNode.next = head; tail.next = newNode; tail = newNode; followed by do-while print from head -> Option D

4. Quick Check:

   Insert at end + do-while print from head [OK]

Hint: Use do-while to print circular list once [OK]

Common Mistakes:

• Setting newNode.next to null
• Using while loop with null condition
• Starting print from tail instead of head