Java Implementation of linked list add(i, x) method I'm currently trying to brush up on ADT implementations, specifically an implementation for a Linked List (I'm using Java 5 to do this).

Is this implementation I've written for add(i, x) correct and efficient?

public void add(int i, Object x) {

    // Possible Cases:
    //
    //     1. The list is non-empty, but the requested index is out of
    //        range (it must be from 0 to size(), inclusive)
    //
    //     2. The list itself is empty, which will only work if i = 0
    //
    // This implementation of add(i, x) relies on finding the node just before
    // the requested index i.

    // These will be used to traverse the list
    Node currentNode = head;
    int indexCounter = 0;

    // This will be used to mark the node before the requested index node
    int targetIndex = i - 1;

    // This is the new node to be inserted in the list
    Node newNode = new Node(x);

    if (currentNode != null) {

        while (indexCounter &lt; targetIndex &amp;&amp; currentNode.getNext() != null) {

            indexCounter++;
            currentNode = currentNode.getNext();
        }

        if (indexCounter == targetIndex) {

            newNode.setNext(currentNode.getNext());
            currentNode.setNext(newNode);

        } else if (i == 0) {

            newNode.setNext(head);
            head = newNode;
        }

    } else if (i == 0) {

        head = newNode;
    }     
}
First: Java-1.5 and a List of Object, not a generic List? But a CS-degree and intermediate level? 

Second: Your comment complicates 2 cases: List is empty or not - if not ... - well, if you don't distinguish the cases, from: 

// 1. The list is non-empty, but the requested index is out
// of range (it must be from 0 to size (), inclusive)


to:

// it must be from 0 to size (), inclusive. 


Now look at condition 2:

// 2. The list itself is empty, which will only work if i = 0


If the size is 0, and i=0, then i is in the range of 0 to 0 inclusive, isn't it? So it is just one condition, and a much shorter condition. 

However, the code seems right, and can't be simplified like the condition*), and it isn't that easy, even if it looks easy in the end. Several days seems a lot, but several hours can vanish like nothing, expecially, if you get a wrong start. I remember John Bentley, who wrote, that a simple binary search wasn't correctly implemented by most of the professional developers he interviewed. By none of them, if I remember correctly ('Programming Pearls'). 

*) This claim isn't proved. Disprove it, friends!

I would expect an IndexOutOfBoundsException if the index is negative or too big. A size-Method would be useful for that.