Datenstrukturen: Grobe Zusammenfassung

Eine Datenstruktur ist eine Art, Daten im Speicher eines Rechners zu speichern und zu verwalten. Sie bietet mindestens 3 Operationen:

-       Daten aufnehmen

-       Daten löschen

-       Daten lesen

 

Es gibt statitische und dynamische Datenstrukturen. Ein Array, Liste oder ein Stack sind Beispiele für Datenstrukturen.

Ein Array ist eine statische Datenstruktur mit einem zusammenhängendem Speicherbereich, dessen Größe zur Laufzeit nicht veränderbar ist.

Eine Liste ist eine dynamische Datenstruktur, die eine Speicherung einer im Voraus unbekanten Anzahl von miteinander verknüpften Objekten erlaubt.

Listen bestehen aus zwei Sorten von Verwaltungselementen:

-       Knoten:

  • Kennen jeweils ihren Nachfolger, bzw. bei doppeltverketteten Listen auch ihren Vorgänger, und ein Datenelement.

-       Listenelement:

  • Kennt den ersten Knoten bzw. bei einer doppeltverketteten Liste auch den letzten Knoten der Liste.

 

Einen Keller kann man sich wie einen Stapel vorstellen, der nach dem LiFo-Prinzip funktioniert. Man kann einen Keller sowohl mit einem Array als auch mit einer verketteten Liste implementieren.

Dynamische Datenstrukturen müssen in Programmiersprachen wie Java erstmal implementiert werden, da sie sich über dem Abstraktionsniveau der Sprache befinden. Implementierung von dynamischen Datenstrukturen kann mit statischen Datenstrukturen (Arrays) realisiert werden.