Insert at End 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 end means adding a new node just before the first node, updating the last node's link.

Analogy: Imagine people sitting in a circle holding hands. Adding a new person at the end means placing them just before the first person and making sure the last person now holds the new person's hand.

head -> 1 -> 2 -> 3 -> (back to head 1)
          ↑                       ↓
          ← ← ← ← ← ← ← ← ← ← ← ←

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 (circular), insert value 4 at end

Goal: Add a new node with value 4 at the end, keeping the list circular

Step 1: Create new node with value 4

head -> 1 -> 2 -> 3 -> (back to head 1), newNode(4) isolated

Why: We need a new node ready to insert

Step 2: Traverse from head to find last node (node with value 3)

head -> 1 -> 2 -> [curr->3] -> (back to head 1), newNode(4) isolated

Why: We must find the last node to link new node after it

Step 3: Set last node's next to new node

head -> 1 -> 2 -> 3 -> [newNode->4]

Why: Link last node to new node to insert at end

Step 4: Set new node's next to head

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

Why: Maintain circular link by pointing new node back to head

Result:

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

Annotated Code

DSA Java

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

public class CircularLinkedList {
    Node head;

    // Insert new node at end of circular linked list
    public void insertAtEnd(int value) {
        Node newNode = new Node(value); // create new node
        if (head == null) {
            head = newNode; // empty list, new node is head
            newNode.next = head; // circular link to itself
            return;
        }
        Node curr = head;
        // traverse to last node (node whose next is head)
        while (curr.next != head) {
            curr = curr.next; // advance curr to next node
        }
        curr.next = newNode; // link last node to new node
        newNode.next = head; // link new node back to head
    }

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

    public static void main(String[] args) {
        CircularLinkedList cll = new CircularLinkedList();
        cll.head = new Node(1);
        Node second = new Node(2);
        Node third = new Node(3);
        cll.head.next = second;
        second.next = third;
        third.next = cll.head; // circular link

        cll.insertAtEnd(4); // insert 4 at end
        cll.printList();
    }
}

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

create new node to insert

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

handle empty list by making new node point to itself

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

find last node by traversing until next points to head

curr.next = newNode;

link last node to new node

newNode.next = head;

link new node back to head to keep circular

Output

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

Complexity Analysis

Time: O(n) because we traverse all nodes once to find the last node

Space: O(1) because we only create one new node and use constant extra space

vs Alternative: Compared to inserting at head which is O(1), inserting at end requires traversal making it O(n)

Edge Cases

empty list

new node becomes head and points to itself

DSA Java

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

single node list

new node inserted after the single node and points back to head

DSA Java

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

When to Use This Pattern

When you see a circular linked list and need to add at the end, use traversal to find the last node and link the new node before head to maintain the circle.

Common Mistakes

Mistake: Not updating the new node's next pointer to head, breaking the circular link
Fix: Always set newNode.next = head after linking it to the last node

Mistake: Not handling empty list case, causing null pointer errors
Fix: Check if head is null and initialize properly with new node pointing to itself

Summary

Adds a new node at the end of a circular linked list while keeping the list circular.

Use when you want to append data to the end of a circular linked list.

The key is to find the last node and link the new node back to the head to maintain the circle.

Practice

1. What happens when you insert a new node at the end of an empty circular linked list?

easy

A. The new node points to the head, but the list remains empty.

B. The new node points to itself, becoming the only node in the list.

C. The new node is discarded because the list is empty.

D. The new node points to null, ending the list.

Solution

1. Step 1: Understand circular linked list empty state

   When the list is empty, there is no node, so the new node must point to itself to form a circle.

2. Step 2: Insert new node and update pointers

   The new node's next pointer is set to itself, making it the only node and the head of the list.

3. Final Answer:

   The new node points to itself, becoming the only node in the list. -> Option B

4. Quick Check:

   Empty list insertion = node points to itself [OK]

Hint: Empty circular list node points to itself [OK]

Common Mistakes:

• Setting new node's next to null
• Not updating head pointer
• Assuming list remains empty

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

easy

A. newNode.next = head; tail.next = newNode; tail = newNode;

B. newNode.next = null; tail.next = newNode; tail = newNode;

C. newNode.next = tail; head.next = newNode; tail = newNode;

D. newNode.next = head; head.next = newNode; tail = newNode;

Solution

1. Step 1: Set new node's next to head

   In a circular linked list, the last node points to the head, so newNode.next = head is correct.

2. Step 2: Update tail's next and tail pointer

   Tail's next should point to newNode, and tail should be updated to newNode to maintain the list.

3. Final Answer:

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

4. Quick Check:

   New node points to head, tail updated [OK]

Hint: New node next = head, tail next = new node [OK]

Common Mistakes:

• Setting newNode.next to null
• Updating head.next instead of tail.next
• Not updating tail pointer

3. Given the following circular linked list with nodes 10 -> 20 -> 30 -> back to 10, what will be the list after inserting 40 at the end?

Node head = new Node(10);
Node second = new Node(20);
Node third = new Node(30);
head.next = second;
second.next = third;
third.next = head;

Node newNode = new Node(40);
Node tail = third;
newNode.next = head;
tail.next = newNode;
tail = newNode;

medium

A. 40 -> 10 -> 20 -> 30 -> back to 40

B. 10 -> 20 -> 30 -> back to 10 (unchanged)

C. 10 -> 20 -> 30 -> 40 -> back to 10

D. 10 -> 20 -> 40 -> 30 -> back to 10

Solution

1. Step 1: Understand initial list and insertion

   Initial list is 10 -> 20 -> 30 -> back to 10. Inserting 40 at end means 30's next points to 40, and 40 points to head (10).

2. Step 2: Update tail and next pointers

   After insertion, tail is updated to 40, and list becomes 10 -> 20 -> 30 -> 40 -> back to 10.

3. Final Answer:

   10 -> 20 -> 30 -> 40 -> back to 10 -> Option C

4. Quick Check:

   New node added at end, circular link maintained [OK]

Hint: New node next = head, tail next = new node [OK]

Common Mistakes:

• Not updating tail.next to new node
• Not updating tail pointer
• Breaking circular link

4. Identify the error in the following code snippet that inserts a node at the end of a circular linked list:

Node newNode = new Node(50);
newNode.next = null;
tail.next = newNode;
tail = newNode;
tail.next = head;

medium

A. Setting newNode.next to null breaks the circular link.

B. Not updating tail pointer causes list corruption.

C. tail.next should point to null, not newNode.

D. head pointer is incorrectly updated.

Solution

1. Step 1: Check newNode.next assignment

   Setting newNode.next to null breaks the circular property because last node must point to head.

2. Step 2: Verify tail.next and tail updates

   tail.next is set to newNode and tail updated correctly, but newNode.next should point to head, not null.

3. Final Answer:

   Setting newNode.next to null breaks the circular link. -> Option A

4. Quick Check:

   newNode.next must point to head, not null [OK]

Hint: Last node next must point to head, never null [OK]

Common Mistakes:

• Setting newNode.next to null
• Not maintaining circular link
• Confusing tail and head pointers

5. You have a circular linked list with nodes 5 -> 15 -> 25 -> back to 5. You want to insert a new node with value 35 at the end. After insertion, you want to print the list starting from head. Which code snippet correctly performs insertion and prints the list?

Node head = new Node(5);
Node second = new Node(15);
Node third = new Node(25);
head.next = second;
second.next = third;
third.next = head;

Node newNode = new Node(35);
Node tail = third;
// Insert newNode at end
// Print list starting from head

hard

A. newNode.next = null;
tail.next = newNode;
tail = newNode;
Node temp = head;
while(temp != null) { System.out.print(temp.data + " -> "); temp = temp.next; }
System.out.print("null");

B. newNode.next = head;
tail.next = newNode;
tail = newNode;
Node temp = tail;
do { System.out.print(temp.data + " -> "); temp = temp.next; } while(temp != tail);
System.out.print("null");

C. newNode.next = head;
head.next = newNode;
tail = newNode;
Node temp = head;
do { System.out.print(temp.data + " -> "); temp = temp.next; } while(temp != head);
System.out.print("null");

D. newNode.next = head;
tail.next = newNode;
tail = newNode;
Node temp = head;
do { System.out.print(temp.data + " -> "); temp = temp.next; } while(temp != head);
System.out.print("null");

Solution

1. Step 1: Insert newNode correctly at end

   Set newNode.next to head, update tail.next to newNode, and update tail to newNode to maintain circular list.

2. Step 2: Print list starting from head using do-while

   Use a do-while loop starting at head, printing each node until we return to head, ensuring all nodes are printed once.

3. Final Answer:

   newNode.next = head; tail.next = newNode; tail = newNode; followed by do-while print from head -> Option D

4. Quick Check:

   Insert at end + do-while print from head [OK]

Hint: Use do-while to print circular list once [OK]

Common Mistakes:

• Setting newNode.next to null
• Using while loop with null condition
• Starting print from tail instead of head