Datenstrukturen

1 Begriff

Pausengespräch zweier Schüler:

In der Informatik geht ohne Ordnung überhaupt nichts. Diese Ordnung kann mit Hilfe von Daten-strukturen geschaffen werden, die dazu dienen, Daten zu speichern und zu organisieren.

Eine Datenstruktur ist ein Objekt zur Speicherung und Organisation von Daten, die in einer bestimmten Art und Weise angeordnet und verknüpft werden, um den Zugriff auf sie und ihre Verwaltung effizient zu ermöglichen.

Vor allem Such- und Sortiervorgänge benötigen spezielle Datenstrukturen. Sie gewährleisten, dass die Programme mit einfachem, kurzem Programmcode und wenig Anweisungen entwickelt werden können, die nur geringe Rechnerleistung in Anspruch nehmen und einen geringen Speicherbedarf haben.

Zu den wichtigsten Datenstrukturen zählen:

• Array
• Verkettete Liste
• Stapelspeicher
• Warteschlange
• Baum

Die Entscheidung für eine bestimmte Datenstruktur ist immer abhängig von der Zielsetzung der Datenspeicherung und von den Operationen auf die zu speichernden Daten.

2 Merkmale ausgewählter Datenstrukturen

2.1 Das Array

Ein Array ist eine Kombination mehrerer Datenelemente des gleichen Datentyps, die in einem Speicher direkt hintereinander gespeichert werden.

Die Datenstruktur Array kann unterschieden werden in statische und dynamische Arrays. Bei der Ver-wendung statischer Arrays muss festgelegt werden, wie viele Elemente im Array erfasst werden sollen. Seine Größe ist somit für immer fest bestimmt und kann nicht geändert werden. Um diesen Nachteil zu vermeiden, können dynamische Arrays verwendet werden. Hier kann die Zahl der Elemente verändert und an die jeweils aktuellen Bedürfnisse angepasst werden.

Jedes zusätzliche Element wird am Ende des Arrays "angehängt". Der Zugriff auf die Array-Elemente erfolgt über fortlaufende Index-Werte (0, 1, 2, 3, usw.), die beim Hinzufügen der Elemente automatisch vergeben werden. Daraus ergibt sich, dass auf jedes Element direkt zugegriffen werden kann.
Das Entfernen von Elementen aus Arrays ist dagegen technisch aufwändiger.

2.2 Die verkettete Liste

Eine verkettete Liste ist eine Datenstruktur, in dem mehrere Elemente beliebiger Datentypen gespeichert werden können. Die zu speichernden Daten werden in den Listenelementen, den sogenannten Knoten erfasst. Jeder Knoten enthält einen Verweis zum nächsten Knoten, dem sogenannten Zeiger.

Bei Bedarf können weitere Knoten in die verkettete Liste eingefügt oder aus ihr entfernt werden. Dazu müssen lediglich die Zeiger entsprechend neu festgelegt werden.

Da jedes Listenelement nur den Weg zu seinen unmittelbaren Nachfolgeelement kennt, kann der Zugriff auf die Elemente einer verketteten Liste nur schrittweise entlang der Zeiger von einem Knoten zum nächsten erfolgen.

Bei der verketteten Liste handelt es sich um eine dynamische Datenstruktur, da die Länge der Liste beliebig erweitert werden kann.

2.3 Der Stapelspeicher (Stack)

Ein Stapelspeicher oder Stack ist eine dynamische Datenstruktur, mit der mehrere Datenobjekte erfasst werden können. Sie können nur oben auf den Stapel gelegt und auch nur von dort wieder abgerufen werden.

2.4 Die Warteschlange (Queue)

Eine Warteschlange ist eine dynamische Datenstruktur, mit der mehrere Datenobjekte erfasst werden können. Die Datenobjekte werden immer an das Ende der Warteschlange angefügt. Die Rückgabe der Datenobjekte erfolgt in der Reihenfolge ihres Einfügens. Das bedeutet, dass zuerst auf das Daten-element zugegriffen wird, das als erstes eingefügt wurde. Danach auf das, das als zweites eingefügt wurde, usw.

2.5 Der Baum

Ein Baum ist eine dynamische Datenstruktur, die zur Abbildung hierarchischer Strukturen verwendet wird. Die Datenelemente werden dabei in Objekten, sogenannten Knoten, erfasst, die durch die Hierarchie vorgegeben sind. Jeder Knoten verweist auf die ihm untergeordneten Knoten. Bei den verweisenden Knoten wird von einem Elternteil, bei den untergeordneten Knoten von Kindern gesprochen. Alle Knoten bis auf den ersten haben einen Vorfahren. Dieser wird als Wurzel bezeichnet.