CODEWITHSUNDEEP
javadata-structureslinked-listimplementationabstract-data-type
dvanaria
dvanaria

Reputation: 6783

Code Review for 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).

I have two questions:

(1) 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 < targetIndex && 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;
    }     
}

(2) I found this method very challenging to implement. To be honest, it took me several days. This is difficult to admit, because I love programming and consider myself at intermediate level in several languages and platforms. I've been programming since I was 13 (Applesoft BASIC on an Apple IIc!) and have a degree in CS. I currently work as a software tester and have plans to become a developer at some point. So the second part of my question is: am I fooling myself that this is the type of work I would excel at, or does pretty much everyone find this kind of problem challenging? Something tells me even seasoned developers, being faced to implement this method, would find it challenging.

Thanks for your feedback and advice on the second part.

Upvotes: 2

Views: 2124

Answers (3)

dgrant
dgrant

Reputation: 1427

I think it's a good start...A few suggestions:

  • I think your currentNode == null cases should be taken care of at the start, and then return. I don't like everything being inside the "if (currentNode != null)"
  • You should keep track of the size of your linked list somewhere, so that you can easily just check if i > list_size
  • I wouldn't bother renaming "i-1" to targetIndex
  • Don't create the newNode until you need to
  • Write unit tests, then you can easily change things around and know that your implementation still works.
  • Don't simply ignore illegal arguments. If index i < 0 or > size, throw an IllegalArgumentException or IndexOutOfBoundsException (thanks @JB Nizet)

Upvotes: 4

Cervo
Cervo

Reputation: 3082

This implementation is not efficient, but this is in part because the operation add(i, x) is not efficient on a normal linked list. Linked lists are not meant for random access. I think if you created a hash table or something you could probably create a more efficient index into the list. For example consider Map. Then your insertion routine (obviously there is a special case for i=0) of map.ContainsKey(i-1) map.get(i-1) and you instantly have the prior index. And if i != 0 and you do not have the key for that index then right away you know an error. Map is in theory O(1) if there aren't too many collisions, so this is much more efficient (but at the cost of some disk space) than iterating through the list each time. Again it really depends because a pure linked list is not very efficient for add(i, x).

I don't particularly like this method because it silently fails if you say add(32, x) and there are only 15 items in the list. It should at least throw an exception, return false, or something in order to indicate the insertion failed.

Also you can probably merge the two special cases. Assuming newNode.setNext(NULL) works, you just need one check for i==0 and then you can do newNode.setNext(head), head=newNode because whether the list is empty or not this works. If the list is empty you set the next pointer to NULL. This at least eliminates duplicate code.

Taking a week does seem a little much, but some people have a lot of trouble first wrapping their head around pointers (well class references in javaspeak....). The fact that you eventually got something to work is a great step in the right direction.

Upvotes: 1

Peter Lawrey
Peter Lawrey

Reputation: 533530

I suggest you start by writing some unit tests. In particular, try and add a node beyond the end of the list and see what happens. ;)

I think most developers would find writing a LinkedList difficult because a) there are many ways to implement it and b) its not something you would normally write yourself. You would normally use one of the existing implementations which works. ;)

As an exercise it is a good idea all the same. I would suggest you read the code for the built-in LinkedList and think about how you might do things differently. e.g. how you might simplify it could be a start.

Upvotes: 1

Related Questions