We base our Linked List implementation on Node class, we’ve defined in the previous post.

public void insert(int position, T value) {
    Node<T> newNode = new Node<>(value);

    // insert as the new head?
    if (position == 0) {
        // The 1st case.
        newNode.next = head;
        head = newNode;
    } else {
        // The 2nd case.
        // start from the head:
        Node<T> node = head;
        // find position just before the expected one:
        while (--position > 0) {
            node = node.next;
        }
        // insert the new node:
        newNode.next = node.next;
        node.next = newNode;
    }
}

The insertion algorithm has to support two cases.

The first case is inserting the element at the head of the list – be it an empty list or just at index 0 in an existing list. To handle this correctly we have to be sure to not overwrite the old head with the new one.
The second case is inserting the element at a position other than the head of list. To do that we have to find the node just before the expected one and insert the new node there.
Because in the second case we may need to traverse whole Linked List, the worst time complexity of the algorithm is linear – O(n).
Both cases are handled in the above code.

As always, to check that the algorithms actually works and inserts given elements at specified positions, we’ll write unit tests:

package com.farenda.tutorials.algorithms.lists;

import org.junit.Test;

import static org.junit.Assert.*;

public class LinkedListTest {

    private LinkedList<Integer> list = new LinkedList<>();

    @Test
    public void shouldInsertAtSpecifiedPosition() {
        list.insert(0, 2);
        assertEquals(1, list.size());
        list.printContent();

        list.insert(1, 3);
        assertEquals(2, list.size());
        list.printContent();

        list.insert(0, 1);
        assertEquals(3, list.size());
        list.printContent();
    }
}

When we run the tests, they will produce:

[2]
[2,3]
[1,2,3]

• Algorithms and Data Structures Tutorial
• Basic Linked List constructs – add, count, print contents