Sequentielle Datentypen

Aktualisiert am:

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

Sequentielle Datentypen Stack

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

Sequentielle Datentypen 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

Schreibe einen Kommentar

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