Insert at Beginning of Circular Linked List in DSA Typescript

Mental Model

A circular linked list connects the last node back to the first, forming a loop. Inserting at the beginning means adding a new node before the current head and updating the last node to point to this new node.

Analogy: Imagine a round table where people sit in a circle. Adding a new person at the start means placing them before the current first person and making sure the last person now points to the new person, keeping the circle unbroken.

head -> 1 -> 2 -> 3 -> back to head (1)

After insertion at beginning:
head -> new -> 1 -> 2 -> 3 -> back to head (new)

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 (circular), insert value 0 at beginning

Goal: Add a new node with value 0 at the start and keep the list circular

Step 1: Create new node with value 0

new(0) null
list: 1 -> 2 -> 3 -> back to 1

Why: We need a new node to insert at the beginning

Step 2: Find last node (3) that points back to head (1)

1 -> 2 -> 3 -> [points to 1]
new(0) null

Why: We must update last node's pointer to new node to keep circular

Step 3: Set new node's next to current head (1)

new(0) -> 1 -> 2 -> 3 -> back to 1

Why: New node should point to old first node

Step 4: Update last node's next to new node

1 -> 2 -> 3 -> new(0) -> 1

Why: Last node must point to new node to maintain circular link

Step 5: Update head pointer to new node

head -> new(0) -> 1 -> 2 -> 3 -> back to new(0)

Why: Head must now point to the newly inserted node

Result:

head -> 0 -> 1 -> 2 -> 3 -> back to head (0)

Annotated Code

DSA Typescript

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

class CircularLinkedList {
  head: Node | null = null;

  insertAtBeginning(value: number): void {
    const newNode = new Node(value); // create new node
    if (!this.head) {
      newNode.next = newNode; // points to itself if list empty
      this.head = newNode;
      return;
    }
    let last = this.head;
    while (last.next !== this.head) {
      last = last.next!; // find last node
    }
    newNode.next = this.head; // new node points to old head
    last.next = newNode; // last node points to new node
    this.head = newNode; // update head to new node
  }

  toString(): string {
    if (!this.head) return "empty list";
    let result = "";
    let current = this.head;
    do {
      result += current.value + " -> ";
      current = current.next!;
    } while (current !== this.head);
    result += "back to head (" + this.head.value + ")";
    return result;
  }
}

// Driver code
const cll = new CircularLinkedList();
cll.insertAtBeginning(1);
cll.insertAtBeginning(2);
cll.insertAtBeginning(3);
cll.insertAtBeginning(0);
console.log(cll.toString());

const newNode = new Node(value); // create new node

create a new node with the given value

if (!this.head) { newNode.next = newNode; // points to itself if list empty this.head = newNode; return; }

handle empty list by pointing new node to itself and setting head

while (last.next !== this.head) { last = last.next!; // find last node }

traverse to find the last node which points back to head

newNode.next = this.head; // new node points to old head

link new node to current head

last.next = newNode; // last node points to new node

update last node to point to new node to maintain circular link

this.head = newNode; // update head to new node

move head pointer to new node

Output

0 -> 3 -> 2 -> 1 -> back to head (0)

Complexity Analysis

Time: O(n) because we must find the last node by traversing the list once

Space: O(1) because we only create one new node and use a few pointers

vs Alternative: Compared to a singly linked list insert at beginning which is O(1), circular list insert requires O(n) to update last node's pointer

Edge Cases

empty list

new node points to itself and becomes head

DSA Typescript

if (!this.head) {
      newNode.next = newNode; // points to itself if list empty
      this.head = newNode;
      return;
    }

single node list

last node is the head itself, updated to point to new node

DSA Typescript

while (last.next !== this.head) {
      last = last.next!; // find last node
    }

When to Use This Pattern

When you see a problem asking to insert at the start of a circular linked list, remember you must update the last node's pointer to keep the circle intact.

Common Mistakes

Mistake: Not updating the last node's next pointer to the new node, breaking the circular link
Fix: Always find the last node and set its next pointer to the new node before updating head

Mistake: Forgetting to handle empty list case where head is null
Fix: Check if head is null and make new node point to itself and set head

Summary

Inserts a new node at the start of a circular linked list and updates pointers to keep the circle.

Use when you need to add elements quickly at the beginning of a circular linked list.

The key is to update the last node's pointer to the new node and then move head to new node.

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