Datentypen und Datenstrukturen: Feld, Liste, Stapel, Warteschlange

Zwei Programme verwalten dieselbe Liste von 100 000 Namen. Beide fügen laufend neue ein und löschen andere. Das eine braucht Sekunden, das andere Minuten.

Der Unterschied liegt nicht im Algorithmus, sondern in der Datenstruktur. Wie die Daten im Speicher angeordnet sind, entscheidet darüber, welche Zugriffe billig und welche teuer sind.

In diesem Kapitel geht es um vier Grundstrukturen und um die entscheidende Frage bei jeder: Welche Zugriffe kommen in meinem Programm häufig vor? Die Antwort darauf legt die Wahl fest, und sie legt sie oft eindeutig fest.

Vorausgesetzt werden Variablen und einfache Datentypen aus Variablen, Datentypen und Wertzuweisung sowie die O-Notation aus Aufwand von Algorithmen.

Neu ist die Frage, wie Daten angeordnet sind und was das kostet.

Ein einfacher Datentyp speichert genau einen Wert: Ganzzahl, Gleitkommazahl, Wahrheitswert, Zeichen.

Ein strukturierter Datentyp fasst mehrere Werte zu einer Einheit zusammen. Zwei Bauarten sind zu unterscheiden:

• Gleichartig: alle Elemente vom selben Typ, angesprochen über einen Index. Das ist das Feld.
• Ungleichartig: verschiedene Typen, angesprochen über Namen. Das ist der Verbund (auch Datensatz), also etwa eine Person mit Name, Alter und Note.

Verbund und Feld lassen sich beliebig verschachteln, und daraus entsteht praktisch jede Datenhaltung: ein Feld von Verbünden ist bereits eine einfache Tabelle.

Ein Feld liegt zusammenhängend im Speicher. Alle Elemente sind gleich groß und stehen direkt hintereinander.

Index:      0     1     2     3     4
Adresse:  1000  1004  1008  1012  1016
Inhalt:   [ 7 ][ 3 ][ 9 ][ 1 ][ 5 ]

Daraus folgt unmittelbar der große Vorteil. Die Adresse des Elements mit Index $i$ ist

Das ist eine Multiplikation und eine Addition, unabhängig davon, ob das Feld 10 oder 10 Millionen Einträge hat. Zugriff über den Index kostet also $O(1)$.

Ebenso unmittelbar folgt der Nachteil. Soll vorne etwas eingefügt werden, müssen alle nachfolgenden Elemente um einen Platz nach hinten rücken, damit die Zusammenhängigkeit erhalten bleibt. Das kostet $O(n)$. Dasselbe gilt fürs Löschen. Und die Größe steht beim Anlegen fest; wächst der Bedarf, muss ein größeres Feld angelegt und alles umkopiert werden.

Die verkettete Liste dreht beide Eigenschaften um. Jedes Element (Knoten) enthält den Wert und einen Verweis auf den nächsten Knoten. Die Knoten liegen irgendwo im Speicher verstreut.

[ 7 | •]──→[ 3 | •]──→[ 9 | •]──→[ 1 | ⊥]
                                      ↑
                                    Ende

Einfügen ist jetzt billig: Man erzeugt einen Knoten und hängt zwei Verweise um. Nichts muss verschoben werden, also $O(1)$, sofern man schon an der richtigen Stelle steht.

Der Preis ist der Zugriff. Es gibt keine Adressformel mehr; um zum $i$-ten Element zu kommen, muss man vom Anfang aus durchhangeln, also $O(n)$.

🔴 Es gibt hier keinen Sieger, und genau das ist die Lehre. Die Frage lautet nie „welche Struktur ist besser?", sondern „welche Zugriffe kommen in meinem Programm häufig vor?". Wer viel über den Index zugreift, nimmt ein Feld. Wer viel einfügt und löscht, nimmt eine Liste.

Beachte auch die letzte Zeile: Eine Liste braucht zusätzlichen Speicher für die Verweise. Bei kleinen Elementen kann der Verweis größer sein als der Wert selbst.

Die nächsten beiden Strukturen sind anders gedacht. Sie schreiben nicht die Anordnung im Speicher vor, sondern die Zugriffsregel: Sie erlauben absichtlich weniger als Feld und Liste.

Der Stapel (Stack) arbeitet nach LIFO, also last in, first out. Man legt oben auf und nimmt oben weg.

        ┌───┐  ← ablegen und entnehmen
        │ 9 │
        │ 3 │
        │ 7 │
        └───┘

Wie ein Bücherstapel: Das zuletzt aufgelegte Buch liegt oben und wird zuerst wieder genommen.

Die Warteschlange (Queue) arbeitet nach FIFO, also first in, first out. Man reiht hinten ein und entnimmt vorn.

  entnehmen ←── [ 7 ][ 3 ][ 9 ] ←── einreihen

Wie die Schlange an der Kasse: Wer zuerst kam, ist zuerst dran.

Beide bieten nur zwei wesentliche Zugriffe, üblicherweise ablegen und entnehmen, und beide kosten $O(1)$.

Warum baut man etwas, das weniger kann? Weil die Beschränkung genau das Verhalten erzwingt, das gebraucht wird. Wer eine Warteschlange benutzt, kann sich nicht versehentlich vordrängeln; die Reihenfolge ist durch die Struktur garantiert und nicht durch die Sorgfalt des Programmierers. Das ist derselbe Gedanke, aus dem heraus man Variablen einen Typ gibt: Man schließt Fehler aus, statt sie zu vermeiden.

Stapel:

• Die Rücktaste in Editoren und Zeichenprogrammen: Der letzte Schritt wird zuerst rückgängig gemacht.
• Der Aufrufstapel eines Programms: Ruft $A$ die Funktion $B$ auf und $B$ die Funktion $C$, so wird $C$ zuerst beendet. Genau darauf beruht die Rekursion.
• Die Prüfung geschachtelter Klammern: Öffnende Klammer ablegen, bei schließender die oberste entnehmen und vergleichen.

Warteschlange:

• Druckaufträge: Wer zuerst gedruckt hat, bekommt sein Blatt zuerst.
• Tastatureingaben: Die Reihenfolge der Tastendrücke muss erhalten bleiben.
• Netzwerkpakete in einem Puffer.

Bemerkenswert an der Klammerprüfung: Der Stapel macht genau das möglich, woran der endliche Automat aus der theoretischen Informatik scheiterte. Der Automat konnte die Verschachtelungstiefe nicht zählen, weil er nur endlich viele Zustände hat; der Stapel kann beliebig hoch werden.

Dieser Abschnitt gehört zum erhöhten Anforderungsniveau.

Fällt dir auf, dass bei Stapel und Warteschlange nie stand, wie sie gespeichert sind? Das ist Absicht.

Ein abstrakter Datentyp ist durch seine Operationen und deren Verhalten festgelegt, nicht durch die Umsetzung. Für den Stapel:

Ein Stapel lässt sich mit einem Feld umsetzen (Index des obersten Elements mitführen) oder mit einer verketteten Liste (immer vorn einfügen und entnehmen). Beide erfüllen dieselben Zusagen.

Der Nutzen dieser Trennung ist groß: Der benutzende Code muss nur die Operationen kennen. Wechselt man später die Umsetzung, etwa weil die feste Größe des Feldes stört, bleibt alles Übrige unverändert.

🔴 Das ist derselbe Gedanke wie die Kapselung in der objektorientierten Modellierung: außen die zugesagten Operationen, innen die frei wählbare Umsetzung. Der Fachbegriff dafür ist Datenkapselung, und er ist einer der tragenden Gedanken der praktischen Informatik.