Insert at Beginning of Circular Linked List in DSA Java

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 people standing in a circle holding hands. To add a new person at the start, you place them before the first person and make sure the last person now holds hands with the new person, keeping the circle unbroken.

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

Inserting new node 0 at beginning:
head -> 0 -> 1 -> 2 -> 3 -> back to head (0)

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

newNode(0), list: 1 -> 2 -> 3 -> back to 1

Why: We need a new node to insert

Step 2: Find last node (node with value 3)

lastNode(3), list: 1 -> 2 -> 3 -> back to 1

Why: Last node must point to new head after insertion

Step 3: Set newNode.next to current head (1)

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

Why: New node points to old first node

Step 4: Set lastNode.next to newNode

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

Why: Last node now points to new first node

Step 5: Update head to newNode

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

Why: Head must point to new first node

Result:

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

Annotated Code

DSA Java

public class CircularLinkedList {
    static class Node {
        int data;
        Node next;
        Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    Node head = null;

    // Insert at beginning of circular linked list
    public void insertAtBeginning(int data) {
        Node newNode = new Node(data); // create new node
        if (head == null) { // empty list
            newNode.next = newNode; // points to itself
            head = newNode; // head is new node
            return;
        }
        Node temp = head;
        // find last node
        while (temp.next != head) {
            temp = temp.next; // advance to next node
        }
        newNode.next = head; // new node points to old head
        temp.next = newNode; // last node points to new node
        head = newNode; // update head to new node
    }

    // Print circular linked list
    public void printList() {
        if (head == null) {
            System.out.println("List is empty");
            return;
        }
        Node temp = head;
        do {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        } while (temp != head);
        System.out.println("back to " + head.data);
    }

    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();
        // Create initial list 1->2->3 circular
        cll.insertAtBeginning(3);
        cll.insertAtBeginning(2);
        cll.insertAtBeginning(1);
        System.out.print("Original list: ");
        cll.printList();

        // Insert 0 at beginning
        cll.insertAtBeginning(0);
        System.out.print("After inserting 0 at beginning: ");
        cll.printList();
    }
}

Node newNode = new Node(data); // create new node

create new node to insert

if (head == null) { newNode.next = newNode; head = newNode; return; }

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

while (temp.next != head) { temp = temp.next; }

find last node which points back to head

newNode.next = head;

new node points to old head

temp.next = newNode;

last node points to new node

head = newNode;

update head to new node

Output

Original list: 1 -> 2 -> 3 -> back to 1

After inserting 0 at beginning: 0 -> 1 -> 2 -> 3 -> back to 0

Complexity Analysis

Time: O(n) because we must traverse the list to find the last node before insertion

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 Java

if (head == null) { newNode.next = newNode; head = newNode; return; }

single node list

last node is the head itself; after insertion, last node points to new node

DSA Java

while (temp.next != head) { temp = temp.next; }

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: Not handling empty list case where head is null
Fix: Check if head is null and make new node point to itself and become head

Summary

Inserts a new node at the start of a circular linked list while keeping the list circular.

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

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