homeduke Prof. Dr. Uwe Schmidt FH Wedel
zurück
Inhaltsverzeichnis

Die Datei: LinkedList.java

weiter
   1/**
   2 * @author Uwe Schmidt
   3 *
   4 * eine Klasse fuer verkettete Listen
   5 *
   6 * int dieser Klasse, die mit Generics arbeitet,
   7 * wird die eigentliche Liste durch eine Kette von
   8 * Knoten repraesentiert.Fuer die Knoten wird eine
   9 * lokale Klasse definiert, mit der wie in C mit Records
  10 * und Zeiger gearbeitet wird.
  11 *
  12 * die LinkedList-Klasse dient nur als Wrapper,
  13 * um die eigentliche C-aehnliche Implementierung zu
  14 * kapseln.
  15 *
  16 * Es wird also int einem C-Stil int Java programmiert.
  17 * Dieses ist bei Verwendung von Generics int Java auch
  18 * notwendig, da die leere Liste durch die null-Referenz
  19 * dargestellt wird.
  20 *
  21 * Dieser Ansatz wird fuer die Realisierung von
  22 * Baeumen aus Performanzgruenden noch viel wichtiger
  23 * als fuer Listen.
  24 *
  25 * die Routinen sind alle in rekursiver Form
  26 * die meisten Rekursionen sind Endrekursionen
  27 * oder lineare, koennen also einfach in Schleifen
  28 * transformiert werden
  29 *
  30 * in der Routine remove wird mit Seiteneffekten
  31 * gearbeitet, hier wird also der rein funktionale
  32 * Stil verlassen, um Kopieroperationen zu vermeiden
  33 *
  34 * die Konstruktoren sind nicht oeffentlich,
  35 * sie sind durch statische Methoden ersetzt
  36 *
  37 */
  38
  39//--------------------
  40
  41public class LinkedList<E> {
  42
  43    //--------------------
  44    //
  45    // protected als Zugriffsattribut
  46    // erlaubt die schrittweise Erweiterung
  47    // der Menge der Methoden
  48
  49    // die lokale Hilfsklasse fuer
  50    // die Knoten-Records
  51
  52    protected static class Node<E> {
  53        protected E info;
  54        protected Node<E> next;
  55
  56        protected Node(E e, Node<E> l) {
  57            info = e;
  58            next = l;
  59        }
  60    }
  61
  62    protected Node<E> data;
  63
  64    protected LinkedList () {
  65        data = null;
  66    }
  67
  68    //--------------------
  69    //
  70    // mkEmptyList erzeugt immer ein neues Objekt
  71    // das Objekt fuer die leere Liste ist immer ein neues
  72    // Das Singleton Muster ist nicht anwendbar
  73
  74    public static
  75        <E> LinkedList<E> mkEmptyList()
  76    {
  77        return
  78            new LinkedList<E> ();
  79    }
  80
  81    //--------------------
  82
  83    public
  84        LinkedList<E> cons(E info)
  85    {
  86        data = new Node<E> (info, data);
  87        return
  88            this;
  89    }
  90
  91    //--------------------
  92
  93    public
  94        boolean isEmpty()
  95    {
  96        return
  97            data == null;
  98    }
  99
 100    //--------------------
 101
 102    public
 103        E hd()
 104        throws IndexOutOfBoundsException
 105    {
 106        if ( isEmpty() )
 107            throw
 108                new IndexOutOfBoundsException
 109                    ("hd of empty list");
 110
 111        return
 112            data.info;
 113    }
 114
 115    //--------------------
 116
 117    public
 118        LinkedList<E> tl()
 119        throws IndexOutOfBoundsException
 120    {
 121        if ( isEmpty() )
 122            throw
 123                new IndexOutOfBoundsException
 124                    ("tl of empty list");
 125
 126        data = data.next;
 127        return
 128            this;
 129    }
 130
 131    //--------------------
 132
 133    private
 134        int len(Node<E> l) {
 135        return
 136            l == null
 137            ? 0
 138            : 1 + len(l.next);
 139    }
 140
 141    public
 142        int len () {
 143        return
 144            len(data);
 145    }
 146    
 147    //--------------------
 148
 149    private
 150        E at(Node<E> l, int i)
 151        throws IndexOutOfBoundsException
 152    {
 153        if (i < 0 || l == null)
 154            throw
 155                new IndexOutOfBoundsException
 156                    ("illegal index into linked list");
 157        return
 158            ( i == 0 )
 159            ? l.info
 160            : at(l.next, i - 1);
 161    }
 162    
 163    public
 164        E at(int i)
 165        throws IndexOutOfBoundsException
 166    {
 167        return
 168            at(data, i);
 169    }
 170
 171    //--------------------
 172
 173    private
 174        boolean isIn(E e, Node<E> l) {
 175        return
 176            ( l != null )
 177            &&
 178            ( l.info.equals(e)
 179              ||
 180              isIn(e, l.next) );
 181    }
 182
 183    public
 184        boolean isIn(E e) {
 185        return
 186            isIn(e, data);
 187    }
 188
 189    //--------------------
 190
 191    /**
 192     * erzeugt eine neue Liste
 193     * die das Objekt o enthaelt
 194     */
 195
 196    public
 197        LinkedList<E> insert(E e)
 198    {
 199        if ( isIn(e) )
 200            return
 201                this;
 202        return
 203            cons(e);
 204    }
 205
 206    //--------------------
 207
 208    /**
 209     * erzeugt eine neue Liste
 210     * die das Objekt e nicht mehr enthaelt
 211     */
 212
 213    private
 214        Node<E> remove(E e, Node<E> l) {
 215        if ( l == null )
 216            return
 217                l;
 218
 219        if ( l.info.equals(e) )
 220            return
 221                l.next;
 222
 223        l.next = remove(e, l.next);
 224            
 225        // !!! Seiteneffekt
 226        // Liste wird veraendert
 227            
 228        return
 229            l;
 230    }
 231
 232    public
 233        LinkedList<E> remove(E e) {
 234        data = remove(e,data);
 235        return
 236            this;
 237    }
 238}

Die Quelle: LinkedList.java

Seitenanfangzurück
Inhaltsverzeichnis
Letzte Änderung: 29.04.2013
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel