Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Insert After Value in Circular Linked List

Problem Statement

Write a Java program that adds a method to insert a new node with a given value after the first occurrence of a specified target value in a circular linked list. A circular linked list is a singly linked list where the last node’s next pointer points to the head, forming a cycle. The method should insert the new node by updating the next pointers to maintain the circular structure and return true if the insertion is successful (target value found) or false if the target value is not found. Test the implementation with cases where the target value exists in the list and where it does not, including empty lists and single-node lists. You can visualize this as adding a new numbered card to a circular chain of cards, placing it right after the first card with a specific number.

Input:

  • A circular linked list of integers (e.g., 1→2→3→1, where 3→1 forms the cycle), a target value (e.g., 2), and a new value to insert (e.g., 4). Output: A boolean indicating whether the insertion was successful, and the updated list printed as a string, listing nodes from the head until just before it cycles (e.g., "1 2 4 3"). Constraints:
  • The list size is between 0 and 10^5.
  • Node values and the new value are integers in the range [-10^9, 10^9].
  • The list may be empty or not contain the target value. Example:
  • Input: List = 1→2→3→1, target = 2, newValue = 4
  • Output: true, "1 2 4 3"
  • Explanation: Inserts 4 after the first 2, resulting in 1→2→4→3→1.
  • Input: List = 1→2→3→1, target = 5, newValue = 4
  • Output: false, "1 2 3"
  • Explanation: Target 5 not found, list unchanged.
  • Input: List = [], target = 1, newValue = 2
  • Output: false, "[]"
  • Explanation: Empty list, no insertion possible.

Pseudocode

CLASS Node
    SET value to integer
    SET next to Node (null by default)
ENDCLASS

FUNCTION insertAfterValue(head, target, newValue)
    IF head is null THEN
        RETURN false
    ENDIF
    SET current to head
    SET found to false
    REPEAT
        IF current.value equals target THEN
            SET found to true
            BREAK
        ENDIF
        SET current to current.next
    UNTIL current equals head
    IF not found THEN
        RETURN false
    ENDIF
    CREATE newNode as new Node(newValue)
    SET newNode.next to current.next
    SET current.next to newNode
    RETURN true
ENDFUNCTION

FUNCTION toString(head)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    SET visited as new Set
    WHILE current is not null AND current not in visited
        ADD current to visited
        APPEND current.value to result
        IF current.next is not head THEN
            APPEND " " to result
        ENDIF
        SET current to current.next
    ENDWHILE
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of test cases (list values, target, newValue)
    FOR each testCase in testCases
        PRINT test case details
        CALL insertAfterValue(testCase.head, testCase.target, testCase.newValue)
        PRINT insertion result and updated list using toString
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a Node class with: a. An integer value. b. A next pointer to the next node.
  2. In insertAfterValue: a. If the list is empty, return false. b. Traverse the list starting from head until the target value is found or the traversal returns to head. c. If target is not found, return false. d. If target is found:
    • Create a new node with newValue.
    • Set newNode.next to current.next.
    • Set current.next to newNode.
    • Return true.
  3. In toString: a. If head is null, return "[]". b. Traverse from head, use a Set to avoid cycling, append values with spaces. c. Return the string representation.
  4. In main, test with cases where the target exists, does not exist, and edge cases like empty or single-node lists.

Java Implementation

import java.util.*;

public class InsertAfterValueCircular {
    // Node class for the circular linked list
    static class Node {
        int value;
        Node next;

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

    // Inserts a new node after the first occurrence of target
    public boolean insertAfterValue(Node head, int target, int newValue) {
        if (head == null) {
            return false;
        }
        Node current = head;
        boolean found = false;
        do {
            if (current.value == target) {
                found = true;
                break;
            }
            current = current.next;
        } while (current != head);
        if (!found) {
            return false;
        }
        Node newNode = new Node(newValue);
        newNode.next = current.next;
        current.next = newNode;
        return true;
    }

    // Converts circular linked list to string
    public String toString(Node head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        Node current = head;
        Set<Node> visited = new HashSet<>();
        while (current != null && !visited.contains(current)) {
            visited.add(current);
            result.append(current.value);
            if (current.next != head) {
                result.append(" ");
            }
            current = current.next;
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        Node head;
        int target;
        int newValue;

        TestCase(int[] values, int target, int newValue) {
            this.target = target;
            this.newValue = newValue;
            if (values.length == 0) {
                head = null;
                return;
            }
            head = new Node(values[0]);
            Node current = head;
            for (int i = 1; i < values.length; i++) {
                current.next = new Node(values[i]);
                current = current.next;
            }
            // Make circular
            current.next = head;
        }
    }

    // Main method to test insert after value
    public static void main(String[] args) {
        InsertAfterValueCircular inserter = new InsertAfterValueCircular();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new int[]{1, 2, 3}, 2, 4),      // Target exists
            new TestCase(new int[]{1, 2, 3}, 5, 4),      // Target does not exist
            new TestCase(new int[]{}, 1, 2),             // Empty list
            new TestCase(new int[]{5}, 5, 6),            // Single node, target exists
            new TestCase(new int[]{1, 1, 1}, 1, 2)       // Duplicates, insert after first
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            TestCase test = testCases[i];
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input list: " + inserter.toString(test.head));
            System.out.println("Insert " + test.newValue + " after " + test.target);
            boolean result = inserter.insertAfterValue(test.head, test.target, test.newValue);
            System.out.println("Insertion successful: " + result);
            System.out.println("Updated list: " + inserter.toString(test.head) + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input list: 1 2 3
Insert 4 after 2
Insertion successful: true
Updated list: 1 2 4 3

Test case 2:
Input list: 1 2 3
Insert 4 after 5
Insertion successful: false
Updated list: 1 2 3

Test case 3:
Input list: []
Insert 2 after 1
Insertion successful: false
Updated list: []

Test case 4:
Input list: 5
Insert 6 after 5
Insertion successful: true
Updated list: 5 6

Test case 5:
Input list: 1 1 1
Insert 2 after 1
Insertion successful: true
Updated list: 1 2 1 1

Explanation:

  • Test case 1: Inserts 4 after first 2, resulting in 1→2→4→3→1.
  • Test case 2: Target 5 not found, list unchanged, returns false.
  • Test case 3: Empty list, no insertion, returns false.
  • Test case 4: Inserts 6 after 5 in single-node list, resulting in 5→6→5.
  • Test case 5: Inserts 2 after first 1 in 1→1→1→1, resulting in 1→2→1→1→1.

How It Works

  • Node: Stores an integer value and a next pointer.
  • insertAfterValue:
    • Returns false for empty lists.
    • Traverses the list in a loop, stopping at the first node with the target value or when returning to head.
    • If target is not found, returns false.
    • If found, inserts new node, updating next pointers, returns true.
  • toString: Traverses from head, uses a Set to prevent cycling, returns space-separated string or "[]".
  • Example Trace (Test case 1):
    • Input: 1→2→3→1, target=2, newValue=4.
    • current=1, no match, current=2, match.
    • newNode(4).next=3, 2.next=newNode.
    • Result: 1→2→4→3→1, return true.
  • Main Method: Tests target exists, target does not exist, empty list, single node, and duplicates.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Insert After ValueO(n)O(1)
To StringO(n)O(n)

Note:

  • n is the number of nodes in the list.
  • Time complexity: O(n) for insertAfterValue (traverse to find target); O(n) for toString (traverse list).
  • Space complexity: O(1) for insertAfterValue (constant pointers); O(n) for toString (StringBuilder and Set).
  • Worst case: O(n) time, O(n) space for output with large lists.

✅ Tip: Use a do-while loop to traverse the circular list and stop at the head to avoid infinite loops. Insert the new node by carefully updating next pointers to maintain the circular structure.

⚠ Warning: Check for the target value in one full cycle to handle cases where it doesn’t exist. Ensure proper handling of edge cases like empty or single-node lists to avoid null pointer issues.