Insert at Beginning of Circular Linked List in DSA Javascript

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

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

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

Why: To keep circular link, last node must point to new head

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

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

Why: New node should come before current head

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

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

Why: Last node must point to new head to maintain circle

Step 5: Update head pointer to new node

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

Why: Head must point to the new first node

Result:

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

Annotated Code

DSA Javascript

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

class CircularLinkedList {
  constructor() {
    this.head = null;
  }

  insertAtBeginning(value) {
    const newNode = new Node(value);
    if (!this.head) {
      newNode.next = newNode; // points to itself
      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 current head
    last.next = newNode; // last node points to new node
    this.head = newNode; // update head to new node
  }

  printList() {
    if (!this.head) {
      console.log('List is empty');
      return;
    }
    let result = '';
    let current = this.head;
    do {
      result += current.value + ' -> ';
      current = current.next;
    } while (current !== this.head);
    result += '(back to head)';
    console.log(result);
  }
}

// Driver code
const cll = new CircularLinkedList();
cll.insertAtBeginning(1);
cll.insertAtBeginning(2);
cll.insertAtBeginning(3);
// List is now 3 -> 2 -> 1 -> back to head
cll.insertAtBeginning(0); // Insert 0 at beginning
cll.printList();

if (!this.head) { newNode.next = newNode; // points to itself 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 last node that points back to head

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

link new node to current head to insert at beginning

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 as new start

Output

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

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 insertion at beginning which is O(1), circular list insertion requires O(n) to update the last node's pointer

Edge Cases

empty list

new node points to itself and becomes head

DSA Javascript

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

single node list

last node is the head itself; update pointers accordingly

DSA Javascript

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 maintain the circle.

Common Mistakes

Mistake: Not updating the last node's next pointer to the new head, 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 the empty list case where head is null
Fix: Check if head is null and point new node to itself, then set head to new node

Summary

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

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 next pointer to the new node and then move head to the 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 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