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<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);


}