Implementation of a double linked list with generics and inheritance

Question

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<T> implements Iterable<T>{
 // A Double Linked List with Iterator and ListElements.
 protected class ListIterator<T> implements Iterator<T>{
 private ListElement<T> currentElement;
 /**
 * PRECONDITION
 * head != null
 */
 protected ListIterator(ListElement<T> head) {
 this.currentElement = head;
 }
 /**
 * POSTCONDITIONS
 * return the current element
 */
 public ListElement<T> getCurrentElement(){
 return this.currentElement;
 }
 /**
 * POSTCONDITIONS
 * return the next current element
 */
 public boolean hasNext() {
 return this.currentElement != null;
 }
 /**
 * PRECONDITION
 * currentElement != null
 * POSTCONDITIONS
 * return all elements consecutively in the given order
 */
 public T next(){
 ListElement<T> next = this.currentElement.getNext();
 ListElement<T> returnElement = this.currentElement;
 this.currentElement = next;
 return returnElement.getValue();
 }
 /**
 * PRECONDITION
 * currentElement != null
 * POSTCONDITION: The element is removed from the linked list.
 */
 public void remove() {
 ListElement<T> nextElement = this.currentElement.getNext();
 ListElement<T> previousElement = this.currentElement.getPrevious();
 previousElement.setNext(nextElement);
 nextElement.setPrevious(previousElement);
 this.currentElement = nextElement;
 }
 /**
 * PRECONDITION
 * builder != null
 * POSTCONDITIONS
 * return elements as a String
 */
 public String toString(){
 ListIterator<T> iterator = new ListIterator<T>(this.currentElement);
 StringBuilder builder = new StringBuilder();
 builder.append("[");
 while(iterator.hasNext()){
 builder.append(iterator.next());
 builder.append(", ");
 }
 builder.append("]");
 return builder.toString();
 }
 }
 protected class ListElement<T>{
 private T value;
 private ListElement<T> previous;
 private ListElement<T> next;
 private ListElement(){
 this(null, null, null);
 }
 /**
 * PRECONDITION
 * value != null, previous != null, next != null
 */
 protected ListElement(T value, ListElement<T> previous, ListElement<T> next){
 this.value = value;
 this.previous = previous;
 this.next = next;
 }
 /**
 * POSTCONDITIONS
 * return next element in the list
 */
 protected ListElement<T> getNext(){
 return this.next;
 }
 /**
 * PRECONDITION
 * next != null
 */
 public void setNext(ListElement<T> elem){
 this.next = elem;
 }
 /**
 * POSTCONDITIONS
 * return previous element
 */
 public ListElement<T> getPrevious(){
 return this.previous;
 }
 /**
 * PRECONDITION
 * previous != null
 */
 public void setPrevious(ListElement<T> elem){
 this.previous = elem;
 }
 /**
 * POSTCONDITIONS
 * return value
 */
 public T getValue(){
 return this.value;
 }
 /**
 * POSTCONDITIONS
 * return the value as a String
 */
 public String toString(){
 return this.value.toString();
 }
 }
 private ListElement<T> head;
 private ListElement<T> tail;
 private int listSize;
 public SList(){
 this.listSize = 0;
 this.head = null;
 this.tail = null;
 }
 public void add(int position, T value){
 if (Math.abs(position) > (this.listSize + 1)){
 throw new IndexOutOfBoundsException("The provided position is out of bounds: "+position);
 }
 // hier noch ein paar Exceptions her zum Schutz!
 if (shouldBeAppend(position)) {
 append(value, position);
 }
 else if (shouldBeLeftAppended(position)) {
 leftAppend(value, position);
 }else if (shouldBeInsertedLeft(position)){
 leftInsert(value, position);
 }else if (shouldBeInsertedRight(position)){
 rightInsert(value, position);
 }
 listSize ++;
 }
 private void append(T value, int position){
 // first entry in new list
 if (listSize == 0 && head == null && tail == null){
 ListElement<T> element = new ListElement<>(value, null, null);
 this.head = element;
 this.tail = element;
 }else{
 ListElement<T> element = new ListElement<>(value, this.tail, null);
 tail.setNext(element);
 this.tail = element;
 }
 }
 /**
 * PRECONDITION
 * head != null, tail != null, value != null
 */
 private void leftAppend(T value, int position){
 ListElement<T> element = new ListElement<>(value, null, this.head);
 this.head.setPrevious(element);
 this.head = element;
 }
 /**
 * PRECONDITION
 * foundElement != null, value != null
 * POSTCONDITION
 * An additional element is added to the list.
 */
 private void insert(T value, ListElement<T> foundElement){
 ListElement<T> nextElement = foundElement.getNext();
 ListElement<T> element = new ListElement<>(value, foundElement, nextElement);
 foundElement.setNext(element);
 nextElement.setPrevious(element);
 }
 /**
 * PRECONDITION
 * head != null, value != null, position > 0
 * POSTCONDITION
 * An additional element is added to the list.
 */
 private void leftInsert(T value, int position){
 ListElement<T> foundElement = head;
 for (int i=1; i < position; i++){
 foundElement = foundElement.getNext();
 }
 insert(value, foundElement);
 }
 /**
 * PRECONDITION
 * tail != null, value != null, position < 0
 * POSTCONDITION
 * An additional element is added to the list.
 */
 private void rightInsert(T value, int position){
 ListElement<T> foundElement = tail;
 for (int i=-1; i > position; i--){
 foundElement = foundElement.getPrevious();
 }
 insert(value, foundElement);
 }
 private boolean shouldBeAppend(int position){
 return (listSize == 0) || (position == -1) || (listSize == position);
 }
 private boolean shouldBeLeftAppended(int position){
 return (listSize != 0) && (position == 0);
 }
 private boolean shouldBeInsertedLeft(int position){
 return (position != 0) && (position > 0) && (position != listSize);
 }
 private boolean shouldBeInsertedRight(int position){
 return (position < 0) && (position != -1) && (Math.abs(position) != listSize);
 }
 public int size(){
 return this.listSize;
 }
 public Iterator<T> iterator(){
 ListIterator<T> iterator = new ListIterator<>(this.head);
 return iterator;
 }
 /**
 * POSTCONDITIONS
 * return the iterator as a String
 */
 public String toString(){
 return this.iterator().toString();
 }
}

AList

package Aufgabe5;
import java.util.Iterator;
public class AList<K, V> extends SList<Tuple<K, V>>{
 public AList() {
 super();
 }
 /**
 * POSTCONDITION
 * inserts an element with 3 parameters
 */
 public void add(int position, K key, SList<V> elements){
 Tuple<K, V> tuple = new Tuple<>(key, elements);
 super.add(position, tuple);
 }
 /**
 * POSTCONDITION
 * return another iterator in Iterator
 */
 public Iterator<Tuple<K, V>> iterator(){
 return super.iterator();
 }
}

DList

import java.util.Iterator;
public class DList<K extends Dependent<? super K>,V > extends AList<K, V> {
 /**
 * CLIENT HISTORY CONSTRAINT: list was filled with elements.
 * POSTCONDITIONS
 * return true if all elements don't depend on one another (false)
 */ 
 public boolean consistent() {
 Iterator<Tuple<K,V>> it= super.iterator();
 boolean pos_found = false;
 boolean independent = true;
 while (it.hasNext() ) {
 Tuple<K,V> elem = it.next();
 Iterator<Tuple<K,V>> it2 = super.iterator();
 pos_found = false;
 while(it2.hasNext())
 {
 Tuple<K,V> elem2 = it2.next();
 if(pos_found)
 {
 if(elem.getXCoordinate().dependsOn(elem2.getXCoordinate()))
 {
 independent = false;
 }
 }
 if(elem2.equals(elem))
 {
 pos_found = true;
 }
 }
 }
 return independent;
 } 
}

Tuple

package Aufgabe5;
import java.util.Iterator;
class Tuple<X, Y> implements Iterable<Y>{
 private final X xCoordinate;
 private final SList<Y> yCoordinate;
 /**
 * PRECONDITION
 * xCoordinate != null, yCoordinate != null,
 */
 public Tuple(X xCoordinate, Y yCoordinate){
 this.xCoordinate = xCoordinate;
 this.yCoordinate = new SList<>();
 }
 /**
 * PRECONDITION
 * xCoordinate != null, yCoordinate != null,
 */
 public Tuple(X xCoordinate, SList<Y> list){
 this.xCoordinate = xCoordinate;
 this.yCoordinate = list;
 }
 /**
 * POSTCONDITIONS
 * return xCoordinate
 */
 public X getXCoordinate() {
 return this.xCoordinate;
 }
 public Iterator<Y> iterator(){
 return yCoordinate.iterator();
 }
 /**
 * PRECONDITION
 * builder != null
 * POSTCONDITIONS
 * return key and value as a String
 */
 public String toString(){
 StringBuilder builder = new StringBuilder();
 builder.append("("); builder.append(this.xCoordinate); builder.append(" ,"); // (key,
 builder.append(this.yCoordinate); builder.append(")"); // value)
 return builder.toString();
 }
}

Interface Dependent necessary for dependsOn

public interface Dependent <T> {
 // Compares two items on a certain property
 // Such a property can be e.g. if elements are integers
 // or if the elements are characters.
 // PRECONDITION: x != null
 public boolean dependsOn(T x);
}

• Juliano Alves: A comment about Tuple.toString, in this case you can concat Strings without StringBuilder: "(" + this.xCoordinate+ " ," + this.yCoordinate + ")". The only situation where it can be a problem is when you are concatenating strings inside a loop. More here: bit.ly/1gcj08u

Answer 1

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<T> 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<T> iterator = new ListIterator<T>(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 < 0) because the two other cases were handled earlier. The test Math.abs(position) != listSize simplifies to -position != lisSize because of that.

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

  So, what input doesn't get handled? position == -listSize. Oops!

  A note on style: Settle for one style to format if/else. In Java it is common to "cuddle" them onto one line, but in that case put a space in between: } else if (...) {. I prefer to put the else on a new line, because it allows me to put a comment line before each condition.

• 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, and write instead:

  private void append(T value, int position){
   ListElement<T> element = new ListElement<T>(value, this.tail, null);
   // handle case of empty list: insert at beginning too
   if (tail == null) {
   assert listSize == 0;
   assert head == null;
   this.head = element;
   }
   // append at the end of an existing list
   else {
   assert tail.getNext() == null;
   tail.setNext(element);
   }
   this.tail = element;
  }
  

  Is there any specific reason you use both this.tail and a bare tail here?

AList

• I don't quite see why this class needs its own iterator() implementation, considering that it just calls the parent class' method.

DList

• You have switched to another brace style, putting each brace on its own line for control flow constructs. Settle for a single style, etc.

• There is no way for independent to become true again once it is set to false. It might be better to remove that variable and return immediately once the value can be determined.

• pos_found should be named posFound, because this is the naming convention is Java. Actually, booleans should usually have an is... prefix. As the variable is only used inside the loop (and reset there to its original value each time), it should be declared inside the loop.

• Conditionals of the form if (cond1) { if (cond2) { ... } } should be written as if (cond1 && cond2) to avoid unnecessary indentation.

• When looping over the elements in an Iterable object, it is often better to use a for (Tuple<K, V> elem : this) { ... } loop rather than manually accessing the iterator methods with a while.

• It is usually better to use a 4-space indent instead of 8-space indent (or even tabs). Most editors can be configured to use a certain indentation style.

This class looks like it was written by a C programmer.

Tuple

• Using X and Y for type parameters is confusing. Use something that makes sense in the problem domain, like K, V.

• What is all this talk about coordinates, considering that yCoordinate isn't even a number, but a list? Such terminology generally needs a comment explaining what it means.

• return xCoordinate – most useless comment ever.

• Don't put multiple statements onto the same line. You gain nothing, and loose readability.

• Philipp: Wow - this was really comprehensive. If you are next time around Vienna - drop me a line - I will invite you to a glass of beer.

Answer 2

Just some comments on your code:

• Don't call your Iterator ListIterator<T> - that is the name of an interface in java.util and it confused me for a moment.
• It is 'unconventional' to use positive/negative positions to insert values relative to the beginning/end of the list. One effect of this, is that you cannot use -0 to insert at the end of the list.... right? (some form of rightAppend()) method
• you have split up the logic about how you append/insert the data relatively well, but pwehaps you can take it further... Since you know the length of the list, and since you are doubly-linked... when you are inserting data you should go the 'short' way around the loop to find the insert point ... i.e. if the list is size 10, and the position is 9, then you should step 1 back from the end instead of 9 forward from the front.

As for the actual criticism from your course... your Tuple class is not publically visible.... what are they talking about? It is 'package private' ... only classes in your package can see it. If you wanted to, you could nest the Tuple class in your AList class as a protected-static class, but I am not sure that is any better... well, actually, it is better. So, let me change my mind... Tuple should be a protected-static nested class in AClass.

I have not inspected the logic of the Depends processing, but at face value it looks right. I think the interfaces is fine. One possible extension is to use another (a second) interface so that you can support classes that do not implement Dependent, just like there is Comparable and Comparator.