Insert at Beginning of Circular Linked List in DSA Java - Build from Scratch

Insert at Beginning of Circular Linked List

📖 Scenario: You are managing a circular linked list that represents a round-robin queue of tasks. You need to add a new task at the beginning of this circular list to prioritize it.

🎯 Goal: Build a Java program that creates a circular linked list, sets up a helper variable for the new node, inserts a new node at the beginning of the circular linked list, and prints the list to show the updated order.

📋 What You'll Learn

Create a Node class with an integer data field and a next pointer

Create a circular linked list with three nodes having data 10, 20, and 30

Create a new Node with data 5 to insert at the beginning

Write code to insert the new node at the beginning of the circular linked list

Print the circular linked list starting from the new head node

💡 Why This Matters

🌍 Real World

Circular linked lists are used in real-time systems like task scheduling where the list cycles through tasks repeatedly.

💼 Career

Understanding circular linked lists helps in roles involving system programming, embedded systems, and designing efficient data structures.

1

Create Circular Linked List with Three Nodes

Create a class called Node with an integer data and a Node next pointer. Then create three nodes with data 10, 20, and 30 linked in a circular way where the last node points back to the first node. Store the reference to the first node in a variable called head.

DSA Java

// Define Node class and create circular linked list with nodes 10, 20, 30
// Your code here

Hint

Remember to link the last node's next to the head to make the list circular.

2

Create New Node to Insert

Create a new Node called newNode with data 5 that you will insert at the beginning of the circular linked list.

DSA Java

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

public class CircularLinkedList {
    public static void main(String[] args) {
        Node head = new Node(10);
        Node second = new Node(20);
        Node third = new Node(30);
        head.next = second;
        second.next = third;
        third.next = head; // circular link

        // Create newNode with data 5
        // Your code here
    }
}

Hint

Use the new keyword to create a new node with data 5.

3

Insert New Node at Beginning of Circular Linked List

Insert the newNode at the beginning of the circular linked list. Update the next pointers so that newNode becomes the new head and the list remains circular. Update the head variable to point to newNode. Use a Node variable called temp to traverse the list and find the last node.

DSA Java

        Node temp = head;
        while (temp.next != head) {
            temp = temp.next;
        }
        temp.next = newNode;
        newNode.next = head;
        head = newNode;
        // Print circular linked list

Hint

Traverse to the last node using temp, then link it to newNode. Set newNode.next to old head and update head to newNode.

4

Print Circular Linked List Starting from New Head

Print the circular linked list starting from the head node. Use a Node variable called current to traverse the list. Print each node's data followed by ->. Stop printing when you reach the head node again to avoid infinite loop. Finally, print null.

DSA Java

Hint

Use a do-while loop to print nodes starting from head until you circle back to head.

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