Die Liste als abstrakter Datentyp

Aktualisiert am:

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.Die Liste als abstrakter Datentyp Verkettete Liste

Weitere Beiträge aus dieser Serie

Schreibe einen Kommentar

Notify me of followup comments via e-mail. You can also subscribe without commenting.