homedukeAlgorithmen & Datenstrukturen mit Java: Beispielklasse für einfach verkettete Listen Prof. Dr. Uwe Schmidt FH Wedel

Beispielklasse für einfach verkettete Listen

weiter

weiter

LinkedList.java

List
implementiert als einfach verkettete Liste
persistente Implementierung
destruktive Variante in Kommentaren
ohne Generics
weiter
   1package ds.persistent.list;
   2
   3/** Implementation of single linked lists.
   4    The element type is the example class E
   5    In real world java progs, this would be a
   6    generic type parameter.
   7
   8    This implementation is a PERSISTENT one.
   9*/
  10
  11import ds.interfaces.List;
  12import ds.util.E;
  13import java.util.Iterator;
  14
  15import static ds.util.Undef.undefined;
  16
  17public abstract class LinkedList
  18    implements List {
  19
  20    //----------------------------------------
  21    // the smart constructors
  22
  23    // empty list
  24    public static
  25        LinkedList empty() {
  26
  27        return
  28            EMPTY;
  29    }
  30
  31    // singleton list
  32    public static
  33        LinkedList singleton(E e) {
  34        return
  35            EMPTY.cons(e);
  36    }
  37
  38    // list from iterator
  39    public static
  40        LinkedList fromIterator(Iterator<E> elems) {
  41
  42        if ( elems.hasNext() ) {
  43            E info = elems.next();
  44            return
  45                fromIterator(elems).cons(info);
  46        }
  47        return
  48            empty();
  49    }
  50
  51    //----------------------------------------
  52    // public methods
  53
  54    public boolean inv() {
  55        return true;
  56    }
  57
  58    public abstract LinkedList init();
  59    public abstract LinkedList tail();
  60
  61    public abstract LinkedList concat(List l2);
  62
  63    public LinkedList append(E e) {
  64        return
  65            concat(singleton(e));
  66    }
  67
  68    public Node cons(E e) {
  69        return
  70            new Node(ethis);
  71    }
  72
  73    public LinkedList reverse() {
  74        return
  75            reverse1(empty());
  76    }
  77    abstract protected LinkedList reverse1(LinkedList res);
  78
  79    // default impementation for copy
  80    public LinkedList copy() {
  81        return
  82            this;
  83    }
  84
  85    public Iterator<E> iterator() {
  86        return
  87            new ListIterator(this);
  88    }
  89
  90    public String toString() {
  91        return
  92            (new ListIterator(this)).toString();
  93    }
  94
  95    //----------------------------------------
  96    // the empty list
  97
  98    // the "generic" empty list object, (the singleton has a raw type)
  99
 100    private static final LinkedList EMPTY
 101        = new Empty();
 102
 103    // the singleton class for the empty list object
 104
 105    private static final
 106        class Empty
 107        extends LinkedList {
 108
 109        public boolean isEmpty() {
 110            return true;
 111        }
 112        public boolean member(E e) {
 113            return false;
 114        }
 115        public int     length() {
 116            return 0;
 117        }
 118        public E head() {
 119            return
 120                undefined("head of empty list");
 121        }
 122        public LinkedList tail() {
 123            return
 124                undefined("tail of empty list");
 125        }
 126        public E last() {
 127            return
 128                undefined("last of empty list");
 129        }
 130        public LinkedList init() {
 131            return
 132                undefined("init of empty list");
 133        }
 134        public E at(int i) {
 135            return
 136                undefined("at of empty list");
 137        }
 138        public LinkedList concat(List l2) {
 139            return
 140                (LinkedList)l2;
 141        }
 142
 143        //----------------------------------------
 144        // not public stuff
 145
 146        Empty() { }
 147
 148        protected LinkedList reverse1(LinkedList acc) {
 149            return
 150                acc;
 151        }
 152    }
 153
 154    //----------------------------------------
 155    // the none empty list class
 156
 157    private static final
 158        class Node
 159        extends LinkedList {
 160
 161        public boolean isEmpty() {
 162            return
 163                false;
 164        }
 165
 166        public boolean member(E e) {
 167            return
 168                e.equalTo(info)
 169                ||
 170                next.member(e);
 171        }
 172
 173        public int length() {
 174            return
 175                1 + next.length();
 176        }
 177
 178        public E head() {
 179            return
 180                info;
 181        }
 182
 183        public LinkedList tail() {
 184            return
 185                next;
 186        }
 187
 188        public E last() {
 189            if ( next.isEmpty() )
 190                return
 191                    info;
 192            return
 193                next.last();
 194        }
 195
 196        public LinkedList init() {
 197            if ( next.isEmpty() )
 198                return
 199                    empty();
 200            return
 201                setNext(next.init());
 202        }
 203
 204        public E at(int i) {
 205            if ( i == 0 )
 206                return
 207                    info;
 208            return
 209                next.at(i - 1);
 210        }
 211
 212        public LinkedList concat(List l2) {
 213            return
 214                setNext(next.concat(l2));
 215        }
 216
 217        /* destructive *
 218        public LinkedList copy() { // duplicate all nodes
 219            return
 220                next.copy().cons(info);
 221        }
 222        /**/
 223
 224        //----------------------------------------
 225        // not public stuff
 226
 227        private final E             info;
 228        private
 229            /* persistent */ final /**/
 230            LinkedList next;
 231
 232        Node(E iLinkedList n) {
 233            info = i;
 234            next = n;
 235            ++cntNode;
 236        }
 237
 238        protected LinkedList reverse1(LinkedList acc) {
 239            return
 240                next.reverse1(setNext(acc));
 241        }
 242
 243        Node setNext(LinkedList l2) {
 244            /* persistent */
 245            if ( l2 == next )
 246                return
 247                    this;
 248            return
 249                l2.cons(info);
 250
 251            /* destructive *
 252            next = l2;
 253            return
 254                this;
 255            /**/
 256        }
 257    }
 258
 259    //----------------------------------------
 260    // iterator class
 261
 262    private static
 263        class ListIterator
 264        extends ds.util.Iterator<E> {
 265
 266        List cur;
 267
 268        ListIterator(List l) {
 269            cur = l;
 270            ++cntIter;
 271        }
 272
 273        public boolean hasNext() {
 274            return
 275                ! cur.isEmpty();
 276        }
 277
 278        public E next() {
 279            if ( cur.isEmpty() )
 280                return
 281                    undefined("iterator exhausted");
 282
 283            E res = cur.head();
 284            cur   = cur.tail();
 285            return
 286                res;
 287        }
 288    }
 289
 290    //----------------------------------------
 291    // profiling
 292
 293    private static int cntNode = 0;
 294    private static int cntIter = 0;
 295
 296    public static String stats() {
 297        return
 298            "stats for ds.persistent.list.List:\n" +
 299            "# new Node()         : " + cntNode + "\n" +
 300            "# new ListIterator() : " + cntIter + "\n";
 301    }
 302}
Quellen
weiter

Letzte Änderung: 01.11.2017
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel