Add

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right. Returns true if operation is successful else false.

public boolean add(int index, int value) {
}

Case: Invalid index

If index is

• less than 0 or
• greater than linked list length

simply return null

public class LinkedList {

    public boolean insert(int index, int value) {
        if (index < 0 || index > length) return false;
    }
}

Case: Index is equal to zero

To insert element at index zero, you can simply perform a prepend operation which inserts element at beginning of linked list.

public class LinkedList {

    public boolean insert(int index, int value) {
        if (index < 0 || index > length) return false;
        if (index == 0) {
            prepend(value);
        }
    }
}

Case: Index is equal to linked list length

To insert element at end of linked list, you can simply perform an append operation.

public class LinkedList {

    public boolean insert(int index, int value) {
        if (index < 0 || index > length) return false;
        if (index == 0) {
            prepend(value);
        } else if (index == length) {
            append(value);
        }
    }
}

Case: Index is between zero and length of linked list

First, get the node before desired index (say temp).

Node temp = get(index - 1);

Since you are inserting desired node after temp, desired node’s next must reference to node temp’s next is pointing.

node.next = temp.next;

Now all left to do is to set the temp’s next reference as desired node.

temp.next = node;

public class LinkedList {

    public boolean insert(int index, int value) {
        if (index < 0 || index > length) return false;
        if (index == 0) {
            prepend(value);
        } else if (index == length) {
            append(value);
        } else {
            Node node = new Node(value);
            Node temp = get(index - 1);
            node.next = temp.next;
            temp.next = node;
            length++;
        }
        return true;
    }
}

Testing

public class LinkedListTest {

    @Test
    void add() {
        LinkedList linkedList = new LinkedList();
        linkedList.append(12);
        linkedList.append(14);
        linkedList.append(16);
        linkedList.append(18);
        linkedList.append(20);

        // when index is out of range
        assertFalse(linkedList.add(73, 24));

        // when index is equal to zero
        assertTrue(linkedList.add(0, 11));
        assertEquals(List.of(11, 12, 14, 16, 18, 20), convertToArrayList(linkedList));

        // when index is equal to linked list length
        assertTrue(linkedList.add(6, 21));
        assertEquals(List.of(11, 12, 14, 16, 18, 20, 21), convertToArrayList(linkedList));
        
        // when index is in range
        assertTrue(linkedList.add(3, 15));
        assertEquals(List.of(11, 12, 14, 15, 16, 18, 20, 21), convertToArrayList(linkedList));
    }
}

Time Complexity

At worst case inserting at desired index requires traversing through node’s next so, this operation has worst-case time complexity of O(n).