Beispiel
|
Abstrakter Datentyp List implementiert mit einfach verketteten Listen
|
| |
abstrakt
|
nur die Schnittstelle der Operationen ist nach außen bekannt,
nicht die innere Struktur
|
Schnittstelle |
in Java: interface List
|
?
|
|
Hilfsklassen
|
|
E
|
für die Elemente
|
Invariant
|
für die Konsistenz-Überprüfung
|
Implementierung |
in Java: class LinkedList
|
|
public abstract
class LinkedList
implements List {
...
private static final
class Empty
extends LinkedList {
...
}
private static final
class Node
extends LinkedList {
E info;
LinkedList next;
...
}
...
}
|
|---|
Undef
|
zum Fehler auslösen
|
Iteratoren |
Muster zum Iterieren über alle Elemente einer Kollektion
|
JDK Klassen |
|
Iterator
|
Hilfsklasse zur bequemeren Implementierung von Iteratoren und
mit einigen nützlichen allgemein verwendbaren Iteratoren
|
Erzeugung |
von neuen Listen mit Konstruktor-Funktionen (smart constructors)
|
|
public abstract
class LinkedList
implements List {
...
public static
LinkedList empty() {
...
}
public static
LinkedList singleton(E e) {
...
}
public static
LinkedList fromIterator(Iterator<e> elems) {
...
}
...
}
|
|---|
Software-Technik |
|
|
Schnittstelle wird in einem Java Interface festgelegt (List)
|
|
Wiederverwendung
|
|
Implementierung in einer abstrakten Klasse (LinkedList)
|
|
Nur diese abstrakte Klasse ist öffentlich bekannt
|
|
Wartbarkeit durch Information Hiding
|
|
Erzeugende Funktionen werden durch öffentliche, statische Funktionen realisiert,
nie direkt durch Konstruktoren
|
|
Wartbarkeit durch Information Hiding
|
|
Summen-Datentypen werden durch Vererbung realisiert (Empty, Node, LinkedList)
|
|
In einer industriell einsetzbaren Container-Bibliothek sollte, um Typsicherheit
zu erreichen, über die
Element-Datentypen abstrahiert werden und mit Generics gearbeitet werden (nicht eine feste Klasse E)
|
|
Eine Implementierung mit Generics wird in Java sehr,
sehr unübersichtlich und verschleiert das Ziel
dieser Veranstaltung, das Verständnis über den inneren Aufbau und die Funktionsweise
von Datenstrukturen
|
|
Die Java-Implementierungen sind um Größenordnungen länger als vergleichbare
Haskell-Implementierungen.
|
|
Haskell-Implementierungen können sehr gut als Spezifikation dienen und führen
zu besseren Java-Implementierungen
|
Algorithmen & Datenstrukturen mit Java: Motivation und einführende Beispiele
