Generic Linked List Implementation in Java

Question

I am looking for feedback on my doubly linked list implementation that I have written in Java. I am looking for specific feedback on the efficiency of my code, as well as my usage of generics. I am pretty new to using generics in Java, and I'm not quite sure that I am using them correctly yet.

My node class is pretty basic, but I'd like to revisit my Equals and Hashcode. Am I implementing these correctly? See snippet below:

My node class's equals/hashcode:

@Override
public boolean equals(Object that){
    if(this == that)
        return true;
    if(!(that instanceof LLNode))
        return false;

    return this.data.equals(((LLNode)that).getData());
}

@Override
public int hashCode(){
    return (this.data == null ? 0 : this.data.hashCode());
}     

The DoublyLinkedList class, where the linked list is actually implemented can be found here, as there is too much to post here I think. Am I missing any major functionality? Are generics used properly?

If possible I'd also like to have my test cases reviewed to see if they are strong enough, and at least somewhat well designed. Those are here.

I was unsure of how to test certain things - specifically cases where I am expecting exceptions to be thrown.

Answer 1

My answer only deals with the "testing" part of your question, not the review of the classes themselves.

If I can start with a question - are you expecting LLNode to be used by other classes? Or is it only for use by DoublyLinkedList? If it's the latter, then it's effectively private to DoublyLinkedList, whether you've declared it that way or not. That is, it's not part of your library's API, and I wouldn't bother with separate tests for it.

Your tests for removeAt look like they're only checking that the size of the structure is correct at the end of the test, not that the correct nodes have been removed. They really need some kind of assertion to make sure that the list has the right nodes in it afterwards.

The way you've tested exceptions is fine; although there are other ways of doing it. I suggest you read up on the ExpectedException feature of JUnit, and see whether it's what you want to use.

Now for the controversial stuff - I've been shot down for this point of view before, but this is the voice of experience speaking.

It's hard, on reading your test, to tell what behaviour of the list has been tested, and what hasn't. For example, you have a testRemoveAt; but without reading every line of the test, I can't tell which cases of the removeAt method have been tested - for example, (1) What if the argument is negative? (2) What if the argument is greater than the number of things in the list? (3) What if the argument is valid? (4) What if the list is empty?. I think you've tested (3) and (4), but not (1) and (2), but I'm not sure.

For this reason, I strongly recommend naming your tests after the behaviour that they test, NOT after the method that implements that behaviour. This means you'll have more tests, and smaller ones, but you'll be able to see far more easily which behaviour has and hasn't been tested. Also, in the event of a failure, it will be easier to see what has actually gone wrong. So in this particular case, I would name the tests for removeAt something like -

@Test
public void removeAtThrowsException_withNegativeArgument(){
}

@Test
public void removeAtThrowsException_whenListIsEmpty(){
}

@Test
public void removeAtRemovesCorrectNodeFromList_whenArgumentLessThanSizeOfList(){
}    

@Test
public void removeAtThrowsException_whenArgumentNotLessThanSizeOfList(){
}

As far as tests for equals go, you probably want quite a few cases. Such as -

1. What happens if the argument is not a DoublyLinkedList?
2. What happens if the argument is a DoublyLinkedList with different elements
3. What happens if the argument is a DoublyLinkedList with the same elements in a different order?
4. What happens if the argument is a DoublyLinkedList with the same elements in the same order?
5. What happens if the argument is a DoublyLinkedList with equal elements (but not the same) in the same order?

Again, I recommend having each of these as a separate test method, with a descriptive name. And the biggest benefit is that you can look at your test method names, and know which cases have and have not been tested, without having to read through the code.

Answer 2

David had some really good points about your tests. I just wanted to add a few more in regard to your list.

1. The Iterable interface is generic and you should bind a type parameter to it, so your client receives a type-safe iterator.

2. If you didn't design this list to be subclassed, you should declare it as final. I really don't forsee any issues in subclassing your list since there's no case of self-use, but it's a good practice if you don't want to commit to maintaining a class hierarchy.

3. As David mentioned, the client should know nothing of your node class. Have your public methods return data and have your iterator deal with data as well. If you return to me the head of the list I can call head.setNext(null) and your list is gone. It's OK to have methods that accept nodes, but they should be private, e.g. private boolean removeNode(LLNode).

4. In LLNode.equals you test if that is null right after testing if its an instance of LLNode. The instance check will return false if its parameter is null, so the null check isn't necessary.

5. Also in LLNode.equals -- I'm being picky here -- you don't have to call LLNode.getData. You can access another instance's private data from inside its class. If your doing a lot of comparisons, you'll cut method invocation overhead, but that's not going to result in significant savings of any kind.

6. A contains(T data) method would be nice.

7. You could easily extend LLIterator to support reverse iteration by setting currentPos to the size of your list and decrementing the position in next().