In diesen Beitrag behandeln wir die Themen rund um sequentiellen Datentypen. Sequentielle Datentypen ist eine Datenstruktur, die als Folge von gleichartigen Elementen definiert ist. Die Elemente liegen in einer geordneten Reihenfolge vor, sodass man mit einem Index auf sie zugreifen kann.
Array
Ein Array ist wie folgt definiert:
- Es besitzt eine feste Anzahl von Elementen.
- Die Reihenfolge der Elemente ist eindeutig definiert.
- Ein ganzzahliger Index identifiziert ein Element im Array.
- Ein Array belegt im Speicher einen zusammenhängenden Block, daher ist ein Array eine Und-Verknüpfung aus seinen Elementen und seiner Länge.
Listen
Eine Liste ist einem Array sehr ähnlich, jedoch sieht dieser Datentyp es vor, die Anzahl seiner Elemente zu verändern.
- Veränderliche Anzahl von Elementen.
- Klar definierte Reihenfolge.
- Ein ganzzahliger Index identifiziert ein Element in der Liste.
Vergleich von Array-List und LinkedList in Java
Im nachfolgendem wird ein Vergleich zwischen den Implementierungsarten einer Liste aufgestellt. Um eine Liste zu Implementieren kann man entweder eine Array-Datenstrucktur oder eine LinkedList-Datenstruktur benutzen.
Bei einer Implementierung mittels Arrays werden die Elemente intern in einem Array abgespeichert, welches beispielsweise bei einem Aufruf der add-Methode vollständig kopiert werden muss. Eine LinkedList hingegen hängt das übergebene Element einfach ans Ende seiner verketteten Struktur an.
Laufzeiten-Vergleich:
- size-Methode
- array: O(1)
- linked: O(1)
- set-Methode
- array: 0 (1)
- linked:O (n)
- get-Methode
- array: 0 (1)
- linked 0 (n)
- add-Methode:
- array: 0(1)
- linked: 0 (1)
- insert-Methode
- array: 0 (n)
- linked:O (n)
- remove-Methode
- array: 0 (n)
- linked:O (n)
Wie man erkennen kann, schneidet die LinkedList bei den set- und get-Methoden deutlich schlechter ab, als eine ArrayList.
Iteratoren
Ein Iterator wird genutzt, um eine Datenstruktur von Anfang bis Ende zu durchlaufen. Ein Iterator muss mindestens zwei Operationen zur Verfügung stellen: „hasNext” und „next”. Die „hasNext”-Methode liefert entweder „true” oder „false ” zurück, je nach dem, ob ein Folgeelement existiert oder nicht. Die „next”-Methode liefert das nächste Element der Datenstruktur.
Stacks
Stapel (engl. Stack) ist eine Datenstruktur, die Zwei Operationen zur Verfügung stellt:
- push: legt ein Element auf den Stapel
- pop: entfernt das Oberste Element vom Stapel.
Queue
Warte Schlangen (engl. Queue) arbeiten nach dem fifo- Prinzip („first-in-first-out”). Das heißt, wer zuerst in die Warteschlange aufgenommen wird, kommt auch als erstes wieder heraus.
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
