Code Review for Java Implementation of Linked List add(i, x) Method

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.

Usually implementation of LinkedList<T> assumes that there are public methods like addBefore(Note<T>, T value) and addAfter(Note<T>, T value).

Therefore your implementation should look like the one bellow:

public void add(int index, Object x) {
    // There is a small optimization can be made if index == size of the linked list. 
    // Hence you can insert just after the tail of the list 
    // without the traversal of the whole list.
    Node node = findNode(index); 
    addBefore(node, x); // use the existing method.
}

The implementation of addBefore(node, x) should not be very complex.

In your solution, you have to deal with an annoying corner case : if the node is to be inserted in front of the list, then you cannot just apply a setNext(newNode) to the previous node, since there is no previous node. Instead, you have to deal with the attribute head just for this specific case.

You can greatly simplify things if you introduce a "root" node. This root node will always exist in the LinkedList (So, an empty list is composed of only one Node : the root).

Using this convention, I can implement your method with 9 lines of code, containing only one loop. I will post this solution if you want to (I don't know if it is ok to give his own solution on this site, and maybe you'd like to try on your own before I post my implementation).

to answer the question 2, I think implementing such a method is not an easy task, because it is not natural for our human brain to reason about a recursive data type. And if you introduce corner cases as you did, you quickly become overwhelmed by what you have to keep in mind in order to design your algorithm.

Here is what I did in order to implement your method :

1. I drew example lists, with boxes and arrows with a pencil and paper. An empty list, a list with one element, with 2 and with 3.
2. Then I drew the expected result, when I insert at 0 for the empty list, at 0 and 1 for the singleton list, etc.
3. I tried to find an approximative algorithm in my head, and with the help of the drawings, and focusing on the nominal case (an insertion between 2 nodes).
4. I put this algorithm in code (or at least what seemed about right)
5. I mentally executed on my drawings the algorithm I wrote (you can draw step by step modifications, if you prefer)
6. I found a case where the algorithm fails. I spotted the flaw in my initial algorithm, rethought it, then went back to step 4

After some iterations, I realized it was almost working, except for the corner case (insertions in front of the list). I introduced the root Node, and my algorithm worked.

Edit

Here is my implementation :

public class LinkedList<T> {
    private static class Node<T> {
        private T value;
        private Node next;

        public Node(T value) {
            this.value = value;
        }        
    }

    private Node root = new Node(null);

    public void add(int i, T v) {
        Node n = root;
        while(i>0) {
            if (n.next == null) {
                throw new ArrayIndexOutOfBoundsException();
            }
            n = n.next;
            i--;
        }
        Node newNode = new Node(v);
        newNode.next = n.next;
        n.next = newNode;
    }
}

This method looks totally counterintuitive, probably because it shouldn't even be a part of your interface (insert OBJECT by index in the linked list, seriously?)

See, if you're trying to "to brush up on ADT implementations", you should probably know, that the linked list doesn't allow inserting the elements by index (that would be odd, because list is not an array and insertion like that is a O(n)operation).

Now, I think that the best way for you to dive into the ADT programming would mean writing something like a template doubly-linked list. Insertion and deletion operations would require some thinking about the references and usage of generics makes you think a bit "more generic" :)