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

↓

last_node.next = new_node

↓

new_node.next = head

↓

head = new_node

↓

Done

Start by creating a new node. If the list is empty, point new node to itself. Otherwise, find the last node, update its next to new node, set new node's next to old head, and update head to new node.

Execution Sample

DSA Javascript

function insertAtBeginning(head, data) {
  const newNode = { data, next: null };
  if (!head) {
    newNode.next = newNode;
    return newNode;
  }
  let current = head;
  while (current.next !== head) current = current.next;
  current.next = newNode;
  newNode.next = head;
  return newNode;
}

This code inserts a new node at the start 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	newNode.next = null	No nodes yet
2	Check if list is empty	empty	head = null	List is empty
3	Set newNode.next = newNode (self-loop)	1 node	newNode.next → newNode	┌────────┐ │ data:10│ │ next:─┐│ └───────┘│ ↑ └─ (points to self) newNode
4	Return newNode as head	1 node	head → newNode	┌────────┐ │ data:10│ │ next:─┐│ └───────┘│ ↑ └─ (points to self) head/newNode
5	Insert 20 at beginning (list not empty)	1 node	Create newNode with data=20	Existing list: ┌────────┐ │ data:10│ │ next:─┐│ └───────┘│ ↑ └─ head head
6	Traverse to last node (data=10)	1 node	current = head (data=10)	┌────────┐ │ data:10│ │ next:─┐│ └───────┘│ ↑ └─ head current
7	Set last node's next to newNode	2 nodes	current.next → newNode	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ next:─┐│ │ next:null│ └───────┘│ └────────┘ ↑ └─ head current
8	Set newNode.next to head	2 nodes	newNode.next → head	┌────────┐ ┌────────┐ │ data:10│───→│ data:20│ │ next:─┐│ │ next:─┐│ └───────┘│ └───────┘│ ↑ └─────────────┘ head
9	Update head to newNode	2 nodes	head → newNode	┌────────┐ ┌────────┐ │ data:20│───→│ data:10│ │ next:─┐│ │ next:─┐│ └───────┘│ └───────┘│ ↑ └─────────────┘ head
10	Return new head	2 nodes	head points to newNode	Final list: ┌────────┐ ┌────────┐ │ data:20│───→│ data:10│ │ next:─┐│ │ next:─┐│ └───────┘│ └───────┘│ ↑ └─────────────┘ head

💡 Return newNode as new head after updating pointers to maintain circular list

Variable Tracker

Variable	Start	After Step 3	After Step 7	After Step 8	After Step 9	Final
head	null	newNode(10)	newNode(10)	newNode(10)	newNode(20)	newNode(20)
newNode	undefined	newNode(10)	newNode(20)	newNode(20)	newNode(20)	newNode(20)
current	undefined	undefined	node(10)	node(10)	node(10)	node(10)

Key Moments - 3 Insights

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

Because in a circular linked list, the last node points back to head. We must update last node's next to new node to keep the circle intact, as shown in step 7 of execution_table.

What happens if the list is empty when inserting?

If empty, new node points to itself (self-loop) to form a circular list of one node, as shown in steps 3 and 4.

Why do we update head to newNode at the end?

Because we insert at beginning, newNode becomes the new head. This is done after fixing pointers to maintain the circle, as in step 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what pointer change happens?

A head points to current

B newNode.next points to head

C current.next points to newNode

D newNode.next points to itself

💡 Hint

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

At which step does the new node become the head?

A Step 9

B Step 8

C Step 6

D Step 10

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns around step 9

If the list was empty, what would newNode.next point to after insertion?

A null

B newNode itself

C head

D undefined

💡 Hint

Refer to step 3 in execution_table where newNode.next points to itself

Concept Snapshot

Insert at Beginning of Circular Linked List:
- Create new node
- If empty, newNode.next = newNode (self-loop)
- Else, find last node
- last_node.next = newNode
- newNode.next = head
- head = newNode (new start)

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, making a single-node circle. If not empty, traverse the list to find the last node, which points back to the head. Update the last node's next pointer to the new node. Then set the new node's next to the old head. Finally, update the head pointer to the new node. This keeps the circular structure intact 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, breaking the circular link.

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

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 A

4. Quick Check:

   New head points to old head, circle intact [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 to new head
• Inserting at end instead of beginning

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 JavaScript?

easy

A. const newNode = { data: value, next: head }; last.next = newNode; head = newNode;

B. const newNode = { data: value, next: null }; last.next = head; head = newNode;

C. const newNode = { data: value, next: head }; head.next = newNode; head = newNode;

D. const newNode = { data: value, next: null }; newNode.next = head; head = newNode;

Solution

1. Step 1: Create new node with next pointing to current head

   The new node's next should point to the current head to insert at beginning.

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

   Since it's circular, last node's next must point to new node, then head is updated to new node.

3. Final Answer:

   const newNode = { data: value, next: head }; last.next = newNode; head = newNode; -> Option A

4. Quick Check:

   New node next = head, last.next = new node, head updated [OK]

Hint: New node next = head; last.next = new node; update head [OK]

Common Mistakes:

• Not updating last.next to new node
• Setting newNode.next to null instead of head
• Updating head before last.next

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

function Node(data) { this.data = data; this.next = null; }

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

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

// Print list starting from head
let temp = head;
do {
  console.log(temp.data);
  temp = temp.next;
} while(temp !== head);

medium

A. 20 30 10

B. 10 20 30

C. 10 30 20

D. 30 20 10

Solution

1. Step 1: Understand the initial circular list

   Initially, list is 20 -> 30 -> back to 20.

2. Step 2: Insert 10 at beginning and update links

   New node 10 points to 20 (old head), 30 (last node) points to 10, head updated to 10.

3. Step 3: Print order starting from new head

   Traversal prints 10, then 20, then 30, then stops as it loops back to head.

4. Final Answer:

   10 20 30 -> Option B

5. Quick Check:

   New head 10, then 20, then 30 [OK]

Hint: New head data prints first, then follow next pointers [OK]

Common Mistakes:

• Not updating last node's next to new head
• Printing nodes until null instead of circular condition
• Confusing node order after insertion

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

function insertAtBeginning(head, value) {
  const newNode = { data: value, next: head };
  let temp = head;
  while(temp.next !== null) {
    temp = temp.next;
  }
  temp.next = newNode;
  head = newNode;
  return head;
}

medium

A. The function should not return head.

B. The newNode's next should be null, not head.

C. The head should not be updated after insertion.

D. The while loop condition should check for temp.next !== head instead of null.

Solution

1. Step 1: Analyze loop condition for circular list

   In a circular linked list, last node's next points to head, not null, so loop should check temp.next !== head.

2. Step 2: Understand impact of wrong condition

   Checking for null causes infinite loop or error because next is never null in circular list.

3. Final Answer:

   The while loop condition should check for temp.next !== head instead of null. -> Option D

4. Quick Check:

   Loop until last node points to head [OK]

Hint: In circular list, last.next points to head, not null [OK]

Common Mistakes:

• Using null check in circular list traversal
• Not updating last node's next pointer correctly
• Forgetting to update head after insertion

5. You have a circular linked list with nodes containing values 5, 15, and 25. You want to insert a new node with value 10 at the beginning. After insertion, what will be the correct order of nodes when traversed starting from the new head, and why is updating the last node's next pointer essential?

hard

A. 5 -> 15 -> 25 -> 10; last.next should point to old head, not new node.

B. 10 -> 5 -> 15 -> 25; updating last.next is optional since newNode.next points to head.

C. 10 -> 5 -> 15 -> 25; updating last.next maintains the circular link to new head.

D. 10 -> 15 -> 25 -> 5; last.next should point to newNode.next.

Solution

1. Step 1: Insert new node at beginning and update pointers

   New node 10 points to old head 5; last node 25 must point to new node 10 to keep circular link.

2. Step 2: Traverse list from new head

   Traversal order is 10 -> 5 -> 15 -> 25, then back to 10.

3. Step 3: Importance of updating last.next

   If last.next is not updated to new head, circular link breaks and traversal fails.

4. Final Answer:

   10 -> 5 -> 15 -> 25; updating last.next maintains the circular link to new head. -> Option C

5. Quick Check:

   Last node points to new head to keep circle [OK]

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

Common Mistakes:

• Skipping update of last.next pointer
• Assuming newNode.next update is enough
• Incorrect traversal order after insertion