Algorithmen & Datenstrukturen mit Java: Beispielklasse für einfach verkettete Listen

List	implementiert als einfach verkettete Liste
	persistente Implementierung
	destruktive Variante in Kommentaren
	ohne Generics
	--> ein Versuch mit Generics
package ds.persistent.list;
/** Implementation of single linked lists.
    The element type is the example class E
    In real world java progs, this would be a
    generic type parameter.
    This implementation is a PERSISTENT one.
*/
import ds.interfaces.List;
import ds.util.E;
import java.util.Iterator;
import static ds.util.Undef.undefined;
public abstract class LinkedList
    implements List {
    //----------------------------------------
    // the smart constructors
    // empty list
    public static
        LinkedList empty() {
        return
            EMPTY;
    }
    // singleton list
    public static
        LinkedList singleton(E e) {
        return
            EMPTY.cons(e);
    }
    // list from iterator
    public static
        LinkedList fromIterator(Iterator<E> elems) {
        if ( elems.hasNext() ) {
            E info = elems.next();
            return
                fromIterator(elems).cons(info);
        }
        return
            empty();
    }
    //----------------------------------------
    // public methods
    public boolean inv() {
        return true;
    }
    public abstract LinkedList init();
    public abstract LinkedList tail();
    public abstract LinkedList concat(List l2);
    public LinkedList append(E e) {
        return
            concat(singleton(e));
    }
    public Node cons(E e) {
        return
            new Node(e, this);
    }
    public LinkedList reverse() {
        return
            reverse1(empty());
    }
    abstract protected LinkedList reverse1(LinkedList res);
    // default impementation for copy
    public LinkedList copy() {
        return
            this;
    }
    public Iterator<E> iterator() {
        return
            new ListIterator(this);
    }
    public String toString() {
        return
            (new ListIterator(this)).toString();
    }
    //----------------------------------------
    // the empty list
    // the "generic" empty list object, (the singleton has a raw type)
    private static final LinkedList EMPTY
        = new Empty();
    // the singleton class for the empty list object
    private static final
        class Empty
        extends LinkedList {
        public boolean isEmpty() {
            return true;
        }
        public boolean member(E e) {
            return false;
        }
        public int     length() {
            return 0;
        }
        public E head() {
            return
                undefined("head of empty list");
        }
        public LinkedList tail() {
            return
                undefined("tail of empty list");
        }
        public E last() {
            return
                undefined("last of empty list");
        }
        public LinkedList init() {
            return
                undefined("init of empty list");
        }
        public E at(int i) {
            return
                undefined("at of empty list");
        }
        public LinkedList concat(List l2) {
            return
                (LinkedList)l2;
        }
        //----------------------------------------
        // not public stuff
        Empty() { }
        protected LinkedList reverse1(LinkedList acc) {
            return
                acc;
        }
    }
    //----------------------------------------
    // the none empty list class
    private static final
        class Node
        extends LinkedList {
        public boolean isEmpty() {
            return
                false;
        }
        public boolean member(E e) {
            return
                e.equalTo(info)
                ||
                next.member(e);
        }
        public int length() {
            return
                1 + next.length();
        }
        public E head() {
            return
                info;
        }
        public LinkedList tail() {
            return
                next;
        }
        public E last() {
            if ( next.isEmpty() )
                return
                    info;
            return
                next.last();
        }
        public LinkedList init() {
            if ( next.isEmpty() )
                return
                    empty();
            return
                setNext(next.init());
        }
        public E at(int i) {
            if ( i == 0 )
                return
                    info;
            return
                next.at(i - 1);
        }
        public LinkedList concat(List l2) {
            return
                setNext(next.concat(l2));
        }
        /* destructive *
        public LinkedList copy() { // duplicate all nodes
            return
                next.copy().cons(info);
        }
        /**/
        //----------------------------------------
        // not public stuff
        private final E             info;
        private
            /* persistent */ final /**/
            LinkedList next;
        Node(E i, LinkedList n) {
            info = i;
            next = n;
            ++cntNode;
        }
        protected LinkedList reverse1(LinkedList acc) {
            return
                next.reverse1(setNext(acc));
        }
        Node setNext(LinkedList l2) {
            /* persistent */
            if ( l2 == next )
                return
                    this;
            return
                l2.cons(info);
            /* destructive *
            next = l2;
            return
                this;
            /**/
        }
    }
    //----------------------------------------
    // iterator class
    private static
        class ListIterator
        extends ds.util.Iterator<E> {
        List cur;
        ListIterator(List l) {
            cur = l;
            ++cntIter;
        }
        public boolean hasNext() {
            return
                ! cur.isEmpty();
        }
        public E next() {
            if ( cur.isEmpty() )
                return
                    undefined("iterator exhausted");
            E res = cur.head();
            cur   = cur.tail();
            return
                res;
        }
    }
    //----------------------------------------
    // profiling
    private static int cntNode = 0;
    private static int cntIter = 0;
    public static String stats() {
        return
            "stats for ds.persistent.list.List:\n" +
            "# new Node()         : " + cntNode + "\n" +
            "# new ListIterator() : " + cntIter + "\n";
    }
}
Quellen
	interface List
	class LinkedList (persistent)
	class LinkedList (destruktiv)
	class E
	class Undef
Beispielklasse für einfach verkettete Listen

LinkedList.java
