Insert Operation

Suppose we have a linked list with $n$ elements (nodes), and we want to insert a new node at index $k$. That is, we insert a new node between elements at indices $k-1$ and $k$. After the insertion, we will have $n + 1$ elements:

• The node at index $k - 1$ before the insertion will remain at that index after the insertion.
• The node at index $k$ before the insertion will be at index $k+1$ after the insertion.
• The newly added node will be at index $k$.

For example, we have a linked list with three nodes at indices 0, 1, and 2.

We will insert a new node at index 2:

Exercise Complete the implementation of insert which adds a new node at the given index.

public void insert(int index, T t) {
    // TODO Implement me!
}

Hint: Use the following visualization as guidance.

public void insert(int index, T t) {
  Node<T> target = head;
  for (int counter = 0; counter < index - 1; counter++) {
    target = target.next;
  }

  Node<T> node = new Node(t);
  node.next = target.next;
  target.next = node;
}