Implementation of a double linked list with generics and inheritance

Disclaimer: The code already was graded - so I don't ask for a homework here -just for a code review. :)

For a university course my colleagues and I had to implement a list without using any Arrays or any utilities from java collections. Only interfaces were allowed.

We received a small feedback complaining that the our class Tuple is publicly visible. As I do this course just for learning I felt the need for more details and a comprehensive feedback. I add our task that you can better understand why we coded it in this way.

Our Task

We had to implement a list with two inheritance generations with the following properties.

-
SList: SList implements java.lang.Iterable and provides a method add with two parameters:

• the position where it should be inserted and

• the element which should be added.

-
AList: AList inherits from SList - with the necessary types set through generics it is a subtype of SList. Each AList list element is affiliated with
a possible empty list. The type of the affiliated list items is set through an other type parameter. AList provides another add method with three parameters:

• position and

• element like in SList

• affiliated_list which is affiliated to the added element.

-
DList: With the necessary types set through generics it is a subtype of AList. All elements added to DList should support a dependsOn method. Moreover DList provides a method consistent which returns true if all list elements from DList do not depend on each other. This is evaluated thanks to the dependsOn method.

If you speak German, you can take a look on the task directly.

SList

```
package Aufgabe5;

import java.util.Iterator;

public class SList implements Iterable{
// A Double Linked List with Iterator and ListElements.

protected class ListIterator implements Iterator{

private ListElement currentElement;
/**
* PRECONDITION
* head != null
*/
pr

This is great code, and I trust that you can implement the required data structure correctly. Therefore, I won't review it with respect to the assignment.

Most things I found are nitpicks (e.g. about proper formatting). There are a couple of suggestions you can consider. And then there is even one little bug.

SList

-
A package declaration should create a globally unique name space, e.g. at.ac.tuwien.nutzerkennung.oop13.aufgabe5. All parts should be lowercase.

-
Inconsistent spacing irks me: …head) { vs …Element(){. Pick one style and enforce it consistently (e.g. by using automated formatters). The Java Coding Conventions seem to suggest a single space between closing paren and opening curly brace.

In a similar vein, always keep an empty line before a method declaration. A documentation comment belongs to the following declaration.

It is almost never necessary for good readability to have the first line of a method empty.

-
PRECONDITION head != null doesn't help much as a comment. Enforce this precondition, e.g. via assert head != null. But it's good that you have carefully thought about such conditions.

-
Having a comment describe the functionality of a class/method/field is a good idea. However, such a comment usually precedes the declaration, and should use a documentation comment (/**). This criticism applies to the comment // A Double Linked List with Iterator and ListElements..

-
You consequently mention this when referring to instance fields: this.currentElement. I personally like this a lot (coming from languages like Perl), but it isn't exactly common. Such usage is of course OK if it is part of your groups coding convention.

-
The way you have designed your classes, ListElement is actually Iterable as well. At least you use it as such. Encoding this relationship by formally implementing that interface would clean your code up in some parts:

SList#iterator() would become

public Iterator iterator(){
    return this.head.iterator();
}

and ListIterator#toString() would become

public String toString(){
    StringBuilder builder = new StringBuilder();

    builder.append("[");
    for (T item : this.currentElement) {
        builder.append(item);
        builder.append(", ");  // FIXME remove trailing comma

    }
    builder.append("]");

    return builder.toString();
}

-
If we don't do that, there is an easy way to remove the trailing comma in ListIterator#toString():

public String toString(){
    ListIterator iterator = new ListIterator(this.currentElement);
    StringBuilder builder = new StringBuilder();

    builder.append("[");
    while(iterator.hasNext()){
        builder.append(iterator.next());
        if (iterator.hasNext()) {
            builder.append(", ");
        }
    }
    builder.append("]");

    return builder.toString();
}

Notice also how I used empty lines to separate the three distinct tasks initialization – enclosing the items in brackets – returning.

-
As far as I can see, new ListElement() == new ListElement(null, null, null) has no useful interpretation, and isn't used anywhere. Remove that useless constructor.

-
shouldBeAppend should be shouldBeAppended ;-)

-
It is dubious that all those shouldBeXAppended methods make sense on their own; it would not impact the code negatively if you would put the conditions directly into the SList#add conditional. Having them in their own methods only makes the code more self-documenting, and a bit easier to test (also, it hides cyclomatic complexity). I personally would not have put them into separate methods, so that it is easier to get an overview of the possible paths.

if ((listSize == 0) || (position == -1) || (listSize == position)) {
    append(value, position);
}
else if ((listSize != 0) && (position == 0)) {
    leftAppend(value, position);
}else if ((position != 0) && (position > 0) && (position != listSize)){
    leftInsert(value, position);
}else if ((position < 0) && (position != -1) && (Math.abs(position) != listSize)){
    rightInsert(value, position);
}

Can we be sure from this mess that all paths are actually covered, and that we are allowed to omit the else?

Some of the tests are unneccessary: if the first branch is not taken, we already know that (listSize != 0) && (position != -1) && (listSize != position). We can remove those tests from the other branches. The test (position != 0) && (position > 0) looks a bit silly, we can simplify that as well. In the final branch, we already know that (position

-
if (listSize == 0 && head == null && tail == null) – the class is small enough to keep all invariants in mind, but listSize == 0 and head == null && tail == null` imply each other. In general, an assertion to make sure that these two are in sync would be better than to take another branch as if nothing happened.

In this special case, you could remove those two large branches as they share most code,

StackExchange Code Review Q#36759, answer score: 5