17. Erweiterung der Implementierung mit verketteter Liste

Die zweite Implementierung der Schnittstelle ExtQ ist eine Erweiterung der Klasse ListQ.

Bei equals stellt sich wieder die Frage nach Objektgleichheit. Aufgrund der folgenden Objektdiagramme[1] soll nun der Vergleich a.equals(b) das Ergebnis false liefern, während a.equals(c) das Ergebnis true:

Abbildung 34: Objektgleichheit bei verketteten Listen

Bei der Programmierung von equals verwenden wir wieder zwei Variablen dieser und jener, die unabhängig voneinander durch die beiden verketteten Listen laufen. Da die Elemente hier nicht in Reihungen sondern in Knoten gespeichert werden, sind sie diesmal vom Typ Node:

Abbildung 35: Durchlauf zweier verketteten Listen

Bei der Programmierung von copy stellen sich wieder die vier Alternativen:

Abbildung 36: Erste Alternative: Referenzkopie

Abbildung 37: Zweite Alternative: flache Kopie

Abbildung 38: Dritte Alternative: logische Kopie

Abbildung 39: Vierte Alternative: tiefe Kopie

Dieselben Überlegungen wie bei der Reihungsimplementierung sprechen für die dritte Alternative (logische Kopie) aus: Die Knoten der verketteten Liste werden dupliziert aber die enthaltenen Elemente nicht mehr.

Hieraus ergibt sich die zweite Implementierung von ExtQ:

/** List implementation of Extended Queue - ExtListQ.scala*/

class ExtListQ[E] extends ListQ[E] with ExtQ[E] {

def equals(q: ExtQ[E]): Boolean = {

try {

val that = q.asInstanceOf[ExtListQ[E]]

var dieser = this.ältester

var jener = that.ältester

while (dieser != None && jener != None) {

if (dieser.get.wert != jener.get.wert)

return false

dieser = dieser.get.verbindung

jener = jener.get.verbindung }

return dieser == None && jener == None

} catch { // if (q.getClass != this.getClass)

case e: ClassCastException =>

return false } }

def copy(q: ExtQ[E]) = {

this.clear

val that = q.asInstanceOf[ExtListQ[E]]

var node = that.ältester

while (node != None) {

this.add(node.get.wert.get)

node = node.get.verbindung } } }

Die Objektdiagramme helfen bei solchen komplexen Überlegungen die richtige Alternative auszuwählen.

[1] Hier verwenden wir eine weitere Vereinfachung: Knoten-Objekte mit ihren zwei Referenzen wert und verbindung stellen wir einfach als geteilte Ovale dar.

Version: 5. Dezember 2010