Insert at Beginning of Circular Linked List in DSA Typescript - 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 (node.next == head)

↓

last_node.next = new_node

↓

new_node.next = head

↓

head = new_node

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

Execution Sample

DSA Typescript

class Node {
  data: number;
  next: Node | null;
  constructor(data: number) {
    this.data = data;
    this.next = null;
  }
}

function insertAtBeginning(head: Node | null, data: number): Node {
  const newNode = new Node(data);
  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 beginning of a circular linked list, updating pointers to keep the list circular.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create new node with data=5	head → 10 → 20 → 30 → (back to head)	newNode.next = null	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:5 │ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head
2	Check if list empty	head → 10 → 20 → 30 → (back to head)	No pointer change	List not empty, proceed to find last node
3	Traverse to last node (current.next != head)	head → 10 → 20 → 30 → (back to head)	current moves: 10 → 20 → 30	Traversal steps: current=10 current=20 current=30 (last node)
4	Update last node's next to newNode	head → 10 → 20 → 30 → (back to head)	30.next = newNode	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:5 │ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:∅ │ └────────┘ └────────┘ └────────┘ └────────┘ head ↑ last node now points to newNode
5	Set newNode.next to head	head → 10 → 20 → 30 → (back to head)	newNode.next = head	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:10│ │ data:20│ │ data:30│ │ data:5 │ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ (back to 10) └────────┘ └────────┘ └────────┘ └────────┘ head ↑ last node
6	Update head to newNode	head → 5 → 10 → 20 → 30 → (back to head)	head = newNode	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:5 │ │ data:10│ │ data:20│ │ data:30│ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ │ next:──┼──→ (back to 5) └────────┘ └────────┘ └────────┘ └────────┘ head (new start)
7	End	head → 5 → 10 → 20 → 30 → (back to head)	No change	Insertion complete, circular list updated

💡 Insertion done, head updated to new node, list remains circular

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	Final
head	Node(10)	Node(10)	Node(10)	Node(10)	Node(5)	Node(5)
newNode	null	Node(5)	Node(5)	Node(5)	Node(5)	Node(5)
current	Node(10)	Node(30)	Node(30)	Node(30)	Node(30)	Node(30)

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 step 4 of the execution_table.

What happens if the list is empty when inserting?

The new node points to itself (newNode.next = newNode), making a single-node circular list, as explained in the concept_flow and implied in step 2.

Why do we update head only after changing pointers?

Updating head last ensures all pointers correctly link the new node into the list before changing the start, preventing broken links, as seen in step 6.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 3?

A Node with data 10

B Node with data 20

C Node with data 30

D null

💡 Hint

Check the 'current' variable in variable_tracker after step 3

At which step does the last node's next pointer change to point to the new node?

A Step 4

B Step 2

C Step 5

D Step 6

💡 Hint

Look at the 'Pointer Changes' column in execution_table for step 4

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

A head

B newNode itself

C null

D last node

💡 Hint

Refer to concept_flow and key_moments about empty list insertion

Concept Snapshot

Insert at Beginning of Circular Linked List:
- Create new node
- If empty, point newNode.next to itself
- Else find last node (node.next == head)
- Set last_node.next = newNode
- Set newNode.next = head
- Update head = newNode
- List remains circular

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 circular list. If not empty, traverse to the last node whose next points to head. Update the last node's next to point to the new node, then set the new node's next to the current head. Finally, update head to the new node. This keeps the list circular and inserts 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 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 list becomes linear instead of circular.

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

Solution

1. Step 1: Understand the circular linked list structure

   A circular linked list has its last node pointing 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 D

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 connecting last node
• Replacing the last node instead of adding new head

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

easy

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

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

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

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

Solution

1. Step 1: Link new node to current head

   newNode.next = head sets the new node's next pointer to the current head.

2. Step 2: Update last node's next pointer and head

   last.next = newNode updates the last node to point to the new node, and head = newNode sets the new node as the head.

3. Final Answer:

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

4. Quick Check:

   Correct pointer updates maintain circular list [OK]

Hint: Set newNode.next to head, update last.next, then head [OK]

Common Mistakes:

• Setting newNode.next to null breaks circularity
• Not updating last.next to newNode
• Assigning head incorrectly before linking nodes

3. Given the following TypeScript code for inserting at the beginning of a circular linked list, what will be the printed list after insertion?

class Node {
  data: number;
  next: Node | null;
  constructor(data: number) {
    this.data = data;
    this.next = null;
  }
}

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

let newNode = new Node(5);
// Insert at beginning
newNode.next = head;
third.next = newNode;
head = newNode;

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

medium

A. 5 -> 10 -> 20 -> 30 (circular)

B. 5 -> 20 -> 30 -> 10 (circular)

C. 10 -> 20 -> 30 -> 5 (circular)

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

Solution

1. Step 1: Understand the initial circular list

   Initial list is 10 -> 20 -> 30 -> back to 10 (circular).

2. Step 2: Insert new node with data 5 at beginning

   newNode.next = head points 5 to 10; third.next = newNode points 30 to 5; head = newNode updates head to 5.

3. Step 3: Print traversal

   Starting at head (5), traversal prints 5, 10, 20, 30, then stops as it loops back to 5.

4. Final Answer:

   5 -> 10 -> 20 -> 30 (circular) -> Option A

5. Quick Check:

   New head 5 leads list, circle intact [OK]

Hint: New node data first, then old nodes, circle stays [OK]

Common Mistakes:

• Printing null at end instead of circular loop
• Not updating last node's next pointer
• Confusing order of nodes after insertion

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

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

medium

A. The last.next pointer is updated after changing head, causing incorrect link.

B. No error; code correctly inserts at beginning.

C. newNode.next should point to last instead of head.

D. head should be updated after last.next to maintain circularity.

Solution

1. Step 1: Analyze pointer updates order

   newNode.next = head sets new node's next to old head correctly.

2. Step 2: Verify the updates

   head = newNode updates head to new node. Then last.next = newNode correctly sets the last node's next to the new head since 'last' references the unchanged last node.

3. Step 3: Confirm circularity

   The final structure is newHead -> oldHead -> ... -> last -> newHead, fully circular with no breaks.

4. Final Answer:

   No error; code correctly inserts at beginning. -> Option B

5. Quick Check:

   last reference stable, circle intact [OK]

Hint: last reference remains valid after head update [OK]

Common Mistakes:

• Assuming changing head before last.next breaks circle
• Not updating last.next at all
• Pointing newNode.next incorrectly

5. You have a circular linked list with nodes containing values [15, 25, 35], where 35 points back to 15. You want to insert a new node with value 5 at the beginning. Which sequence of pointer updates correctly maintains the circular linked list?

hard

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

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

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

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

Solution

1. Step 1: Link new node to current head

   newNode.next = head points the new node (5) to the current head (15).

2. Step 2: Update last node's next pointer

   last.next = newNode updates the last node (35) to point to the new node (5), maintaining circularity.

3. Step 3: Update head pointer

   head = newNode sets the new node as the head of the list.

4. Final Answer:

   Set newNode.next = head; last.next = newNode; head = newNode; -> Option C

5. Quick Check:

   New head points to old head; last points to new head [OK]

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

Common Mistakes:

• Updating pointers in wrong order
• Pointing newNode.next to last instead of head
• Not updating last.next to newNode