Sequentielle Datentypen

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.

Kommentare

Eingehende Suchbegriffe zum Artikel:

Zusammenfassung
Sequentielle Datentypen
Artikeltitel
Sequentielle Datentypen
Beschreibung
In diesen Beitrag behandeln wir die Themen rund um sequentiellen Datentypen
Autor

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

E-Mail-Benachrichtigung bei weiteren Kommentaren.
Auch möglich: Abo ohne Kommentar.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.

Pin It on Pinterest

Durch die weitere Nutzung der Seite stimmst du der Verwendung von Cookies zu. Weitere Informationen

Die Cookie-Einstellungen auf dieser Website sind auf "Cookies zulassen" eingestellt, um das beste Surferlebnis zu ermöglichen. Wenn du diese Website ohne Änderung der Cookie-Einstellungen verwendest oder auf "Akzeptieren" klickst, erklärst du sich damit einverstanden.

Schließen