Definition
|
|
destruktiv
|
Zur Konstruktion neuer Listen werden in vorhandenen Listen
einzelne Knoten verändert.
|
|
Es wird mit Zuweisungen an Komponenten einzelner Knoten gearbeitet
|
|---|
|
...
l -> next = f(...);
return l;
...
|
|---|
|
Speicherplatz-Effizienz
|
|
Seiteneffekte
|
persistent
|
Zur Konstruktion neuer Listen werden NIE in vorhandenen Listen
einzelne Knoten verändert, sondern IMMER nur gelesen und daraus neue Knoten
mit den passenden Elementen erzeugt.
|
|
Es wird NIE mit Zuweisungen an Komponenten einzelner Knoten gearbeitet
|
|---|
|
...
return cons(l->info, f(...));
...
|
|---|
|
Speicherplatz-Effizienz
|
|
keine Seiteneffekte
|
| |
Argumente
|
destruktiv
|
Listen als Argumente werden verbraucht.
|
|
Diese Listen dürfen nicht weiter verwendet werden.
|
|---|
falsch |
...
l2 = append(l1, x);
...
l3 = append(l1, y);
...
|
|
Listen müssen geklont werden
|
|---|
richtig |
...
l2 = append(clone(l1), x);
...
l3 = append(l1, y);
...
|
|
sehr fehleranfällig
|
persistent
|
Listen als Argumente werden nur gelesen und behalten somit ihre Werte.
|
|
Sie dürfen beliebig weiterverwendet werden.
|
|---|
richtig |
...
l2 = append(l1, x);
...
l3 = append(l1, y);
...
|
|
keinerlei Fehlerquelle
|
| |
Mehrfachverwendung
|
destruktiv
|
Listen dürfen auch in einer Operation nie mehrfach verwendet werden.
|
falsch |
...
l2 = concat(l1, l1);
...
|
richtig |
...
l2 = concat(clone(l1), l1);
...
|
|
sehr fehleranfällig
|
persistent
|
Listen dürfen beliebig häufig verwendet werden.
|
richtig |
...
l2 = concat(l1, concat(l1, l1));
...
|
|
keinerlei Fehlerquelle
|
| |
Sharing |
Gemeinsame Nutzung von Teilstrukturen
|
destruktiv
|
nicht möglich
|
falsch |
...
l2 = cons(x, l1);
l1 = append(l1, y);
...
|
richtig |
...
l2 = cons(x, clone(l1));
l1 = append(l1, y);
...
|
|
Speicherplatz-Effizienz
|
persistent
|
Listen dürfen gemeinsame Teile besitzen
|
|
...
l2 = cons(x, l1);
l1 = append(l1, y);
...
|
|---|
|
keinerlei Fehlerquelle, das Verdoppeln geschieht automatisch
|
| |
Speicherverwaltung |
|
destruktiv |
händisch: Durch Freigabe aller Knoten
|
|
(relativ) einfach
|
persistent |
händisch: Zum Beispiel durch Referenz-Zähler
|
|
schwierig, aufwändig
|
|
Bei Sprachen mit automatischer Speicherverwaltung
(Java, Javascript, Python, Ruby, Scala, Haskell, ...) entfällt dieses Problem
|
| |
Korrektheit |
|
destruktiv |
|
|
Sehr fehleranfällig durch viele verschiedene Zugriffspfade
auf die gleichen Knoten und durch Zuweisungen an Komponenten der Knoten
|
persistent |
|
|
Einfach: Es gibt keinen Unterschied zwischen einfachen
Werten und Listen.
|
| |
|
Der hier für Listen gemachte Vergleich ist allgemeingültig für alle dynamischen Datenstrukturen,
z.B. für Suchbäume, Warteschlangen, Hash-Tabellen, ...
|
Systemnahe Programmierung in C: Vergleich: Destruktive vs. persistente Listen
