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

Concept Flow - Insert at Beginning of Circular Linked List

Create new node

↓

Is list empty?

Yes→new_node.next = new_node

| No↓

Traverse to last node (node.next != head)

↓

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, link it to new node, new node points to old head, then update head.

Execution Sample

DSA Java

class Node {
  int data;
  Node next;
  
  Node(int data) {
    this.data = data;
  }
}

class CircularList {
  Node head;
  
  // Insert at beginning
  void insertAtBeginning(int val) {
    Node newNode = new Node(val);
    if (head == null) {
      newNode.next = newNode;
      head = newNode;
      return;
    }
    Node lastNode = head;
    while (lastNode.next != head) {
      lastNode = lastNode.next;
    }
    lastNode.next = newNode;
    newNode.next = head;
    head = newNode;
  }
}

This code implements insertion at the beginning of a circular singly linked list, handling both empty and non-empty cases to maintain the circular structure.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=10	empty	newNode.next = null	∅ (empty list)
2	Check if list is empty	empty	head == null → True	∅ (empty list)
3	Set newNode.next = newNode (self loop)	1 node	newNode.next → newNode	┌────────┐ │ data:10│ │ next:──┼──→ (points to self) └────────┘ head → newNode
4	Set head = newNode	1 node	head → newNode	┌────────┐ │ data:10│ │ next:──┼──→ (points to self) └────────┘ head → newNode
5	Insert 20 at beginning (new node)	1 node	newNode.next = null	┌────────┐ │ data:10│ │ next:──┼──→ (points to self) └────────┘ head → node10
6	Check if list empty	1 node	head != null → False	┌────────┐ │ data:10│ │ next:──┼──→ (points to self) └────────┘ head → node10
7	Traverse to last node (node10.next == head)	1 node	lastNode = node10	┌────────┐ │ data:10│ │ next:──┼──→ (points to head) └────────┘ head → node10
8	Set lastNode.next = newNode(20)	2 nodes	node10.next → newNode20	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:──┼──→ ? └────────┘ └────────┘ head → node10
9	Set newNode.next = head (node10)	2 nodes	newNode20.next → node10	┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ next:──┼──→ │ next:──┼──→ (points to node10) └────────┘ └────────┘ head → node10
10	Update head = newNode (20)	2 nodes	head → newNode20	┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ next:──┼──→ │ next:──┼──→ (points to head) └────────┘ └────────┘ head → node20
11	Insert 30 at beginning (new node)	2 nodes	newNode.next = null	┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ next:──┼──→ │ next:──┼──→ (points to head) └────────┘ └────────┘ head → node20
12	Check if list empty	2 nodes	head != null → False	┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ next:──┼──→ │ next:──┼──→ (points to head) └────────┘ └────────┘ head → node20
13	Traverse to last node (node10.next == head)	2 nodes	lastNode = node10	┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ next:──┼──→ │ next:──┼──→ (points to head) └────────┘ └────────┘ head → node20
14	Set lastNode.next = newNode(30)	3 nodes	node10.next → newNode30	┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ ? └────────┘ └────────┘ └────────┘ head → node20
15	Set newNode.next = head (node20)	3 nodes	newNode30.next → node20	┌────────┐ ┌────────┐ ┌────────┐ │ data:20│ │ data:10│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ (points to head) └────────┘ └────────┘ └────────┘ head → node20
16	Update head = newNode (30)	3 nodes	head → newNode30	┌────────┐ ┌────────┐ ┌────────┐ │ data:30│ │ data:20│ │ data:10│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ (points to head) └────────┘ └────────┘ └────────┘ head → node30
17	Stop	3 nodes	Insertion complete	Final list: 30 → 20 → 10 → (back to 30)

💡 Insertion stops after updating head to new node; list remains circular.

Variable Tracker

Variable	Start	After Step 3	After Step 8	After Step 10	After Step 14	After Step 16	Final
head	null	node10	node10	node20	node20	node30	node30
newNode	null	node10	node20	node20	node30	node30	node30
lastNode	null	null	node10	node10	node10	node10	node10
List Size	0	1	2	2	3	3	3

Key Moments - 3 Insights

Why do we set newNode.next to point to itself when the list is empty?

Because in a circular linked list with one node, that node must point to itself to maintain the circular structure. See execution_table step 3 where newNode.next points to newNode.

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

Because the last node's next pointer must be updated to point to the new head to keep the list circular. This is shown in execution_table steps 7-9.

Why does the traversal stop when lastNode.next equals head?

Because in a circular list, the last node points back to head. When lastNode.next == head, we have found the last node. See step 7 and 13 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the head node's data after step 10?

A 30

B 10

C 20

D null

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 10.

At which step does the list first have more than one node?

A Step 3

B Step 8

C Step 14

D Step 16

💡 Hint

Look at the 'Nodes in List' column to see when it changes from 1 to 2.

If the list was initially empty, what pointer change happens at step 3?

A newNode.next points to itself

B head points to null

C lastNode.next points to newNode

D head points to lastNode

💡 Hint

Refer to the 'Pointer Changes' column at step 3.

Concept Snapshot

Insert at Beginning of Circular Linked List:
- Create new node
- If list empty: newNode.next = newNode (self loop), head = newNode
- Else: find last node (lastNode.next == head)
- lastNode.next = newNode
- newNode.next = head
- head = newNode
Maintains circular structure 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 lastNode.next equals head. Then update lastNode.next to point to the new node, set newNode.next to the old head, and finally update head to the new node. This keeps the list circular and places the new node at the start.

Practice

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

easy

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

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

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

D. The list becomes linear and loses its circular property.

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 A

4. Quick Check:

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

Hint: New head points to old head, last node points 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 Java code snippets correctly inserts a new node at the beginning of a circular linked list?

easy

A. last.next = head; head = newNode; newNode.next = last;

B. head.next = newNode; newNode.next = last; last = newNode;

C. newNode.next = null; head = newNode; last.next = head;

D. newNode.next = head; last.next = newNode; head = newNode;

Solution

1. Step 1: Link new node to current head

   Set newNode.next = head to point new node to the current head.

2. Step 2: Update last node's next to new node and move head

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

3. Final Answer:

   newNode.next = head; last.next = newNode; head = newNode; -> Option D

4. Quick Check:

   Correct pointer updates = A [OK]

Hint: Link new node to head, update last.next, then move head [OK]

Common Mistakes:

• Setting newNode.next to null breaks circular link
• Not updating last.next to new node
• Incorrect order of pointer updates

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

class Node {
  int data;
  Node next;
  Node(int d) { data = d; next = null; }
}

Node head = new Node(20);
Node second = new Node(30);
head.next = second;
second.next = head; // circular link

Node newNode = new Node(10);
// Insert at beginning
newNode.next = head;
second.next = newNode;
head = newNode;

// Print list starting from head
Node temp = head;
do {
  System.out.print(temp.data + " -> ");
  temp = temp.next;
} while(temp != head);
System.out.print("null");

medium

A. 10 -> 20 -> 30 -> null

B. 20 -> 30 -> 10 -> null

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

D. 30 -> 20 -> 10 -> null

Solution

1. Step 1: Understand initial list and insertion

   Initial list: 20 -> 30 -> back to 20. New node 10 inserted at beginning, so head moves to 10.

2. Step 2: Trace the print loop

   Starting at head (10), print 10, then 20, then 30, then loop ends at head again.

3. Final Answer:

   10 -> 20 -> 30 -> null -> Option A

4. Quick Check:

   New head 10 followed by old nodes = D [OK]

Hint: Start printing from new head, follow next pointers until back to head [OK]

Common Mistakes:

• Printing nodes in wrong order
• Not updating last node's next pointer
• Confusing circular link with null termination

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

Node newNode = new Node(5);
newNode.next = head;
head = newNode;
// Missing update of last node's next pointer

medium

A. The head should not be updated before updating last node's next pointer.

B. The new node's next pointer should be null instead of head.

C. The last node's next pointer is not updated to point to the new head, breaking the circular link.

D. The new node should be inserted at the end, not the beginning.

Solution

1. Step 1: Check pointer updates after insertion

   New node points to old head, and head is updated, but last node still points to old head.

2. Step 2: Identify circular link break

   Since last node's next is not updated to new head, the circular link breaks, causing incorrect list traversal.

3. Final Answer:

   The last node's next pointer is not updated to point to the new head, breaking the circular link. -> Option C

4. Quick Check:

   Last node must point to new head to keep circle [OK]

Hint: Always update last.next to new head after insertion [OK]

Common Mistakes:

• Forgetting to update last node's next pointer
• Assuming head update is enough
• Not maintaining circular property

5. Given a circular linked list with nodes 5 -> 15 -> 25 -> back to 5, write the sequence of node values after inserting a new node with value 1 at the beginning. Assume the insertion updates all pointers correctly. What is the resulting list?

hard

A. 5 -> 15 -> 25 -> 1 -> null

B. 1 -> 5 -> 15 -> 25 -> null

C. 1 -> 15 -> 25 -> 5 -> null

D. 25 -> 5 -> 15 -> 1 -> null

Solution

1. Step 1: Insert new node at beginning

   New node with value 1 points to old head (5), and last node (25) points to new node.

2. Step 2: Update head pointer

   Head is updated to new node (1), so traversal starts from 1.

3. Final Answer:

   1 -> 5 -> 15 -> 25 -> null -> Option B

4. Quick Check:

   New head 1 followed by old nodes in order [OK]

Hint: New node becomes head, last node points to new head [OK]

Common Mistakes:

• Not updating last node's next pointer
• Incorrect order of nodes after insertion
• Confusing circular list with linear list