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
Designalternative Verweise
° Verweise auf: Anfang und Ende möglich
° Vorteil: Der Zugriff auf das Listenende ist genau so schnell wie auf den Listenanfang (gut für Operationen wie Anfügen)
Array-Implementation für Listen
° Eine Klasse ArrayListe, repräsentiert dem Klienten gegenüber die gesamte Liste und bietet alle Operationen einer Liste an ihrer Schnittstelle
° Intern wird ein Array verwendet, in dem alle bisher eingefügten Elemente gehalten werden (Innensicht, Implementation)
“Wachsende” Arrays für Listen
° Arrays sind als direkte Implementation wegen ihrer festen Größe ungeeignet
° Konzept von wahcsenden Arrays:
- Erzeugung eines Arrays mit einer Anfangsgröße
- Füllung mit den einzufügenden Elementen
- Wenn das Array voll ist; Erzeugung eines größeren und einer Kopie aller enthaltenden Elemente in das neue Array
° Unterscheidung zwischen: Kardinalität (Anzahl der enthaltenen Elemente) und Kapazität ( Anzahl der Elemente die reinpassen könnten)
- Es muss gelten: Kapazität >= Kardinalität
° Bei jedem Einfügen oder Löschen müssen die nachfolgenden Elemente innerhalb des Arrays verschoben werdem
° Extremfall(einfügen am Listanfang): Alle Elemente müssen um eine Position verschoben werden
° Wenn die Kapazität des Arrays für ein neu einzufügendes Element nicht ausreicht, muss zuerst ein größeres Array (bspw. mit doppelter Kapazität) angelegt werden
- Alte Elemente werden kopiert
- Anschließend kann wie vorher eingefügt werden
- Die Klasse ArrayList des JCF basiert auf diesem Konzept
Vergleich der Listen-Implementation
° Einfügen in eine Liste
LinkedList (linearer Aufwand):
- Zielposition ist erst durch Traversieren der Liste zu erreichen
- Objekterzeugung für jede Einfügung
+ Das Einfügen ist sehr einfach
ArrayList (linearer Aufwand):
- Alle Elemente nach der Einfügeposition müssen um eine Position verschoben werden
- Wenn die Kapazität ausgeschöpft ist, muss ein neues Array angelegt und alle Elemente müssen umkopiert werden
+ Die Position zum Einfügen kann direkt angesprochen werden
Zugriff:
+ Bei ArrayList erfolgt der Zugriff in konstanter Zeit (konstanter Aufwand)
- Bei der LinkedList wird durchschnittlich die halbe Liste durchlaufen (linearer Aufwand)
ArrayList eignet sich: Bei Listen mit relativ konstanter Größe mit häufigen Zugriffen auf beliebige Positionen
LinkedList eignet sich: Bei listen mit dynamischer Größe, bei denen viel eingefügt und entfernt wird (insbesondere am Listenanfang)
