Listenimplementierung Flashcards
Implementationen für Sammlungen
dynamische Datenstrukturen: ° wachsende Arrays ° verkettete Listen ° balancierte Bäume ° Hash-Verfahren
Dynamische Datenstrukturen
° bezeichnen die Organisationsform von veränderbaren Sammlungen von Objekten
° Struktur ist ein: Gebilde aus Elementen (Objekten) mit Beziehungen (Relationen)
° meist gleichartig rekursiv aufgebaut
° Einteilung in:
- Strukturen von Elementen ohne Relation zueinander (z.B. für Mengen)
- Lineare oder sequenzielle Strukturen (z.B. für Listen)
- Bäume, in denen ein Element ein Vorgängerelement aber mehr als ein Nachfolgerelement haben kann
- Graphen, in denen ein Element beliebig mit anderen Elementen verbunden sein kann
Strukturen verändern
-> Hinzufügen, Modifizieren und Löschen von Elementen
-> Ändern von Beziehungen
° Datenstrukturen sind dynamisch, wenn sie durch das Einfügen und Entfernen ihrer Elemente wachsen und schrumpfen
Sammlungen als Listen implementieren
° Liste = grundlegendste sequenzielle Struktur
° Weitere lineare Sammlungsarten wie Stacks und Queues bauen darauf auf
° Zwei Implementationsformen:
- Verkettung, basiert auf dem Konzept verkettete Liste (LinkedList)
- Arrays, basiert auf dem Konzept wachsender Arrays (ArrayList)
Klientensicht auf Listen
° beinhaltet beliebig viele Elemente
° Zugriff über den Index auf ein beliebiges Element
° Einfügen eines Elements erhöht den Indes der nachfolgenden Elemente
° Entfernen eines Elements verringert den Index der nachfolgenden Elemente
° Testen ob ein gegebenes Element bereits in der Liste enthalten ist
Verkettung: Lineare Datenstrukturen
für Listen
° Listenelemente besitzen eine Reihenfolge
° Elemente des Grundtyps können mehrfach enthalten sein (Duplikate)
° Eine verkettete Liste ist eine Sequenz ihrer Elemente:
- Jedes Listenelement ist mit dem nächsten verbunden
- Vom Anfang zum Ende der Liste, muss jedes Element traversiert werden
° Einfach verkettete Liste:
- Jedes Listenelement hat nur eine Referenz aus sein Nachfolgerelement
- Die Liste kann nur elementweise vom Anfang zum Ende traversiert werden
° Doppelt verkettete Liste:
- Jedes Listenelement hat eine Referenz aus sein Nachfolger- und sein Vorgängerelement
- Liste kann elementweise in beide Richtungen traversiert werden
Objektorientierter Entwurf einer Liste
° Ein Listenobjekt, das die Liste für den Klienten repräsentiert
° Objekte als Kettenglieder, die die Verkettung der Liste realisieren (unsichtbar für den Klienten)
° Objekte, die als Elemente in der Liste gespeichert sind (verwaltet über die Umgangsfornen der Liste)
Komposition eines Kettenglied Objektes
° Jedes Kettenglied ist ein eigenes Objekt (Klasse Kettenglied)
° Jedes Kettenglied hält eine Referenz auf das eigentliche Element der Sammlung
° Ein Kettenglied hält außerdem mindestens eine Referenz auf ein weiteres Kettenglied (das Nachfolgerelement) als Verkettungsreferenz
Klassendefinition für Kettenglieder
class Kettenglied {
private Kettenglied _nachfolger;
private Person _element;
...
}
° Die Exemplarvariable hat den gleichen Typ wie die definierende Klasse
° wird auch strukturelle Rekursion genannt
Einfach verkettete Liste
° Liste selbst ist ein Exemplar einer eigenen Klasse z.B. LinkedList
° Kettenglieder (Exemplare von Kettenglied) bilden die innere Struktur der Liste
° enthaltenen referenzierten Elemente werde üblicherweise nicht als Teil der Liste angesehen
° In der Klasse LinkedList wird üblicherweise die Referenz auf das erste Kettenglied gehalten (Listenkopf)
° Einfügen in eine verkettete Liste:
- Referenz auf ein neues Element
- Erzeugung eines neuen Kettenglieds
- Das neue Kettenglied wird an die gewünschte Stelle “eingekettet”:
- Nachfolger-Element wird gesetzt
- Vorgänger verweist auf das neue Element
Einfügen und Entfernen aus einer verketteten Liste
Einfügen in eine verkettete Liste:
° Referenz auf ein neues Element
° Erzeugung eines neuen Kettenglieds
° Das neue Kettenglied wird an die gewünschte Stelle “eingekettet”:
- Nachfolger-Element wird gesetzt
- Vorgänger verweist auf das neue Element
Entfernen aus einer verketteten Liste:
° Referenz des Vorgängers wird auf den Nachfolger umgebogen
° Das Kettenglied wird dann vom Garbage-Collector entfernt, sobald keine Referenz mer darauf existiert
Klassendiagramme einer LinkedList
LinkedList:
- hält einen Verweis auf die Klasse Kettenglied im Attribut _listenkopf
- Benutzt die Klasse Element in den Parametern ihrer Methoden
Kettenglied:
- Speichert jeweils ein Exemplar der Klasse Element im Attribut _wert
- Kettenglied verweist auf sich selbst, um im Attribut _nachfolger das nächste Kettenglied referenzieren zu können
11,19
Doppelt verkettete Liste
° Kettenglied hat zusätzlich eine Referenz auf das vorherige Kettenglied
° Ermöglicht effizientes Durchlaufen der Liste in beide Richtungen
° Einfügen und Entfernen werden vereinfacht
° JCF-Implementation LinkedList basiert auf diesem Konzept
Designalternative für Listenende
° An Listenenden (Anfang und/oder Ende) können explizit leere Kettenelemente stehen, sog. Wächter
° Vorteil eines Wächter-Objektes:
- Weniger Sonderfälle zu programmieren (Beim Einfügen, Entfernen etc.)
Sonderfälle: Listenanfang
° Ein Element soll an Position x eingefügt werden
° Ohne Wächter müssen wir die Einfügeposition x = 0 explizit mit einer if-Abfrage behandeln
° Mit Wächter entfällt diese Behandlung, da ein Wächterelement am Anfang steht
