In diesem Beitrag werden wir uns mit dem Typ “Liste” als abstrakten Datentyp beschäftigen. Eine Liste ist abstrakter Datentyp, der eine veränderliche Anzahl von Elementen in fester Ordnung über einen ganzzahligen Index speichern kann.
Ein abstrakter Datentyp wird über sein Verhalten definiert. Das heißt, man beschreibt die möglichen Operationen und Effekte (siehe Interface), die man mit einem Objekt von diesen Typ durchführen kann, ohne diese Operationen oder Effekte zu implementieren.
Array Liste
Als Speicher dieser Liste wird ein Array benutzt. Sobald ein Element der Liste hinzugefügt wird, muss das vorhanden Array in ein größeres Array mit der Länge „+1″ kopiert werden. Die Elemente eines Arrays liegen im Speicher direkt hintereinander.
Verkettete Liste
Im Vergleich zur Array-Liste müssen die Elemente der verketteten Liste nicht hintereinander im Speicher liegen. Jedes Element dieser Liste verlinkt auf sein nächstes Element (bzw. auf ein NIL). Ein NIL ist ein leeres Element von dem kein Verweis auf ein nächstes Element existiert.
Weitere Beiträge aus dieser Serie
- Binäre Suchbäume in der Informatik einfach erklärt
- Durchsuchen von Array-Listen - Lineare und Binäre Suche
- Sequentielle Datentypen
- Algorithmische Techniken - Brute Force, Greedy, Teile und Herrsche, Dynamische Programmierung und Backtracking
- Lazy Evaluation und Streams
- Die Liste als abstrakter Datentyp
- Korrektheitsbeweise von Klassen und Schleifen
- Der Graph als abstrakter Datentyp
