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

Problem Statement

Write a Java program that extends a doubly linked list implementation to include a method that inserts a new node with a given value after the first occurrence of a specified target value. The doubly linked list consists of nodes, each containing an integer value, a reference to the next node, and a reference to the previous node. The program should insert the new node by updating the next and prev pointers appropriately 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 card to a chain of numbered cards, placing it right after the first card with a specific number.

Input:

  • A doubly linked list of integers (e.g., 1↔2↔3), 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 in forward order (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, target = 2, newValue = 4
  • Output: true, "1 2 4 3"
  • Explanation: Inserts 4 after the first 2, resulting in 1↔2↔4↔3.
  • Input: List = 1↔2↔3, 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 DoublyNode
    SET value to integer
    SET next to DoublyNode (null by default)
    SET prev to DoublyNode (null by default)
ENDCLASS

FUNCTION insertAfterValue(head, target, newValue)
    IF head is null THEN
        RETURN false
    ENDIF
    SET current to head
    WHILE current is not null
        IF current.value equals target THEN
            CREATE newNode as new DoublyNode(newValue)
            SET newNode.next to current.next
            SET newNode.prev to current
            IF current.next is not null THEN
                SET current.next.prev to newNode
            ENDIF
            SET current.next to newNode
            RETURN true
        ENDIF
        SET current to current.next
    ENDWHILE
    RETURN false
ENDFUNCTION

FUNCTION printForward(head)
    IF head is null THEN
        RETURN "[]"
    ENDIF
    CREATE result as new StringBuilder
    SET current to head
    WHILE current is not null
        APPEND current.value to result
        IF current.next is not null 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, 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 printForward
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a DoublyNode class with: a. An integer value. b. A next pointer to the next node. c. A prev pointer to the previous node.
  2. In insertAfterValue: a. If head is null, return false (empty list). b. Traverse the list using current until the target value is found or the list ends. c. If target is found:
    • Create a new node with newValue.
    • Set newNode.next to current.next and newNode.prev to current.
    • Update current.next.prev to newNode if current.next exists.
    • Set current.next to newNode.
    • Return true. d. If target is not found, return false.
  3. In printForward: a. If head is null, return "[]". b. Traverse the list using next pointers, appending each value 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

public class InsertAfterValue {
    // Node class for the doubly linked list
    static class DoublyNode {
        int value;
        DoublyNode next;
        DoublyNode prev;

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

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

    // Prints the list in forward direction
    public String printForward(DoublyNode head) {
        if (head == null) {
            return "[]";
        }
        StringBuilder result = new StringBuilder();
        DoublyNode current = head;
        while (current != null) {
            result.append(current.value);
            if (current.next != null) {
                result.append(" ");
            }
            current = current.next;
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        DoublyNode 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 DoublyNode(values[0]);
            DoublyNode current = head;
            for (int i = 1; i < values.length; i++) {
                DoublyNode newNode = new DoublyNode(values[i]);
                newNode.prev = current;
                current.next = newNode;
                current = newNode;
            }
        }
    }

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

        // 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.printForward(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.printForward(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.
  • 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.
  • Test case 5: Inserts 2 after first 1 in 1↔1↔1, resulting in 1↔2↔1↔1.

How It Works

  • DoublyNode: Stores an integer value, a next pointer, and a prev pointer.
  • insertAfterValue:
    • Returns false for empty lists.
    • Traverses list to find first node with target value.
    • If found, inserts new node, updating next and prev pointers, returns true.
    • If not found, returns false.
  • printForward: Traverses list using next pointers, returns space-separated string or "[]".
  • Example Trace (Test case 1):
    • Input: 1↔2↔3, target=2, newValue=4.
    • current=1, no match, move to 2.
    • current=2, match: create newNode(4), newNode.next=3, newNode.prev=2, 3.prev=newNode, 2.next=newNode.
    • Result: 1↔2↔4↔3, 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)
Print ForwardO(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 printForward (traverse list).
  • Space complexity: O(1) for insertAfterValue (constant pointers); O(n) for printForward (StringBuilder).
  • Worst case: O(n) time, O(n) space for output with large lists.

✅ Tip: Use the doubly linked list’s prev pointers to easily link the new node to the next node’s previous pointer, ensuring bidirectional consistency. Test with duplicates to verify insertion after the first occurrence.

⚠ Warning: Update both next and prev pointers carefully to maintain the doubly linked list structure. Check for null pointers to handle edge cases like empty lists or inserting at the end.