11. Implementierung mit verketteten Listen

Noch flexibler ist eine Lösung mit verketteten Listen.

Sie beruht auf der Idee einer inneren Klasse Node, deren Objekte Knoten der verketteten Liste sind. Jeder Knoten enthält ein Attribut wert (vom generischen Typ E für die Speicherung der Elemente) sowie ein Attribut verbindung (vom Typ Node), in der die Adresse des nächsten Knoten gespeichert wird. Eine leere Warteschlange enthält gar keine Knoten; bei jedem add wird ein neues Node-Objekt erzeugt und in die Kette (nach dem jüngsten Element) eingefügt. Bei remove wird das älteste Knoten einfach aus der Kette ausgehängt und der automatischen Speicherbereinigung überlassen.

Um dies zu erreichen, müssen wir uns im ListQ-Objekt die Adressen des ältesten und des jüngsten Knoten merken (globale Variablen ältester und jüngster).

In vielen Implementierungen (wie z.B. in Java) würden wir das Ende der verketteten Liste mit null markieren. In Scala gibt es hierfür die Klasse Option mit den möglichen Werten None und Some; ein Zugriff auf die gekapselten Werte erfolgt mit get:

/** List implementation of Queue - ListQ.scala*/
class Node[E] ( // [1]
     var wert: Option[E], 
     var verbindung: Option[Node[E]]) {}

class ListQ[E] extends Queue[E] {
   protected var ältester: Option[Node[E]] = None
   protected var jüngster: Option[Node[E]] = None

   def clear =
     ältester = None

   def add(o: E) = {
     if (isFull)
        throw new IllegalStateException
     val neu = Some(new Node[E](Some(o), None)) // [2]
     if (isEmpty)
        ältester = neu
     else
        jüngster.get.verbindung = neu
     jüngster = neu }

   def element: E =
     if (isEmpty)
        throw new NoSuchElementException
     else
        ältester.get.wert.get

   def remove =
     if (isEmpty)
        throw new NoSuchElementException
     else
        ältester = ältester.get.verbindung

   def isEmpty =
     ältester == None

   def isFull = // voll wenn kein Node erzeugt werden kann
     try {
        new Node[E](None, None) // [3]
        false
     } catch {
        case e: OutOfMemoryError =>
           true } }

Im letzten Methodenrumpf versuchen wir einen neuen Knoten (als Attrappe) zu erzeugen; wenn es gelingt, ist die Halde (und somit das Queue-Objekt) nicht voll. Die Attrappe wird automatisch entsorgt.

Um die Arbeitsweise dieser Implementierung zu verstehen und ihre Korrektheit zu nachvollziehen, sind Objektdiagramme nützlich.

[1] Es wäre zweckmäßiger, protected class Node als innere Klasse von ListQ[] zu vereinbaren; dies führt aber zu Problemen beim Zugriff auf das Parameterobjekt in equals und copy (s. Seite 23), weil Scala zwischen den Typen this.Node und that.Node unterscheidet.

[2] im Java-Stil einfacher aber unsicherer: neu = new Node(o, null);

[3] Hier ist die Technik mit Option/Some/None notwendig, weil der Scala-Compiler new Node(null, null) – im Gegensatz zu Java – nicht akzeptiert.

Version: 5. Dezember 2010