Generic Linked List Implementation in Java

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.

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 -

• What happens if the argument is not a DoublyLinkedList?

• What happens if the argument is a DoublyLinkedList with different elements

• What happens if the argument is a DoublyLinkedList with the same elements in a different order?

• What happens if the argument is a DoublyLinkedList with the same elements in the same order?

• 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.

StackExchange Code Review Q#8185, answer score: 4