Datenstrukturen, ADT - Abstrakte Datentypen Verkettete Listen bestehen aus miteinander verketteten Elementen(Knoten) Jeder Knoten besitzt einen Schlüssel und einen Verweis auf seinen Nachfolger (Unter Umständen auch Vorgänger)
Beispiel für Schlüssel ohne Verweis auf Vorgänger
Man bezeichnet das erste Element als “Listenkopf” Ein Zeiger zeigt immer auf den Listenkopf
Falls kein Nachfolger / Vorgänger existiert wird der Zeiger = “NIL(Not In List)” oder ”/”
- Objekte werden in linearer Reihenfolge angeordnet
- Reihenfolge wird durch Zeiger festgelegt
Verschiedene Formen von Listen
Verkettung
- einfach verkettet: nur Nachfolger
- doppelt verkettet: Nachfolger & Vorgänger
Sortierung
- sortiert
- nicht sortiert
Anordnung
- zyklisch: nachfolgendes Element von Listenende zeigt auf Listenkopf, Vorgänger von Listenkopf zeigt auf Listenende
- nicht zyklisch: NIL /
Wächter
Dummy-Objekt zur Vereinfachung von Randbedingungen
Der Wächter zeigt bei der Listenerzeugung auf sich selbst und ist nur dazu da eine Liste Zyklisch zu gestalten.
Ohne
Mit
