Algorithmen & Datenstrukturen mit Java: Listen als einfach verkettete Listen

List	implementiert als einfach verkettete Liste
	persistente Implementierung
	destruktive Variante in Kommentaren
	Generics
package ds.persistent.genlist;
/** Implementation of single linked lists with generics.
    This implementation is a PERSISTENT one.
*/
import java.util.Iterator;
import static ds.util.Undef.undefined;
public abstract class LinkedList<E>
    implements Iterable<E> {
    //----------------------------------------
    // the smart constructors
    // empty list
    @SuppressWarnings("unchecked")
    public static <E> LinkedList<E> empty() {
        return
            (LinkedList<E>)EMPTY;
    }
    // singleton list
    public static <E> LinkedList<E> singleton(E e) {
        LinkedList<E> l = empty();
        return
            l.cons(e);
    }
    // list from iterator
    public static <E> LinkedList<E> fromIterator(Iterator<E> elems) {
        if ( elems.hasNext() ) {
            E info = elems.next();
            return
                fromIterator(elems).cons(info);
        }
        return
            empty();
    }
    //----------------------------------------
    // public methods
    abstract public boolean       isEmpty();
    abstract public boolean       member(E e);
    abstract public int           length();
    abstract public E             head();
    abstract public LinkedList<E> tail();
    abstract public E             last();
    abstract public LinkedList<E> init();
    abstract public E             at(int i);
    /* destructive *
    abstract public LinkedList<E> copy();
    /**/
    public LinkedList<E> append(E e) {
        return
            concat(singleton(e));
    }
    public LinkedList<E> cons(E e) {
        return
            new Node<E>(e, this);
    }
    abstract public LinkedList<E> concat(LinkedList<E> l2);
    public LinkedList<E> reverse() {
        LinkedList<E> l = empty();
        return
            reverse1(l);
    }
    abstract protected LinkedList<E> reverse1(LinkedList<E> res); 
    public Iterator<E> iterator() {
        return
            new ListIterator<E>(this);
    }
    public String toString() {
        return
            (new ListIterator<E>(this)).toString();
    }
    //----------------------------------------
    // the empty list
    // the "generic" empty list object, (the singleton has a raw type)
    private static final LinkedList EMPTY
        = new Empty<Object>();
    // the singleton class for the empty list object
    private static final
        class Empty<E>
        extends LinkedList<E> {
        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<E> tail() {
            return undefined("tail of empty list");
        }
        public E last() {
            return undefined("last of empty list");
        }
        public LinkedList<E> init() {
            return undefined("init of empty list");
        }
        public E at(int i) {
            return undefined("at of empty list");
        }
        public LinkedList<E> concat(LinkedList<E> l2) {
            return
                l2;
        }
        /* destructive *
        public LinkedList<E> copy() {
            return
                this;
        }
        /**/
        //----------------------------------------
        // not public stuff
        Empty() { }
        protected LinkedList<E> reverse1(LinkedList<E> res) {
            return
                res;
        }
    }
    //----------------------------------------
    // the none empty list class
    private static final
        class Node<E>
        extends LinkedList<E> {
        public boolean isEmpty()   { return false;  }
        public boolean member(E e) {
            return
                e.equals(info)
                ||
                next.member(e);
        }
        public int length() {
            return
                1 + next.length();
        }
        public E head() {
            return
                info;
        }
        public LinkedList<E> tail() {
            return
                next;
        }
        public E last() {
            if ( next.isEmpty() )
                return
                    info;
            return
                next.last();
        }
        public LinkedList<E> 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<E> concat(LinkedList<E> l2) {
            return
                setNext(next.concat(l2));
        }
        /* destructive *
        public LinkedList<E> copy() {
            return
                next.copy().cons(info);
        }
        /**/
        //----------------------------------------
        // not public stuff
        private final E             info;
        private
            /* persistent */ final /**/
            LinkedList<E> next;
        Node(E i, LinkedList<E> n) {
            info = i;
            next = n;
            ++cntNode;
        }
        protected LinkedList<E> reverse1(LinkedList<E> res) {
            LinkedList<E> tmp = next;
            return
                tmp.reverse1(setNext(res));
        }
        LinkedList<E> setNext(LinkedList<E> next) {
            /* persistent */
            if ( next == this.next )
                return
                    this;
            return
                next.cons(info);
            /* destructive *
            this.next = next;
            return
                this;
            /**/
        }
    }
    //----------------------------------------
    // iterator class
    private static
        class ListIterator<E>
        extends ds.util.Iterator<E> {
        LinkedList<E> cur;
        ListIterator(LinkedList<E> 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.LinkedList:\n" +
            "# new Node()         : " + cntNode + "\n" +
            "# new ListIterator() : " + cntIter + "\n";
    }
}
Listen als einfach verkettete Listen

LinkedList mit Generics
