Dynamische Datenstruktur

Dynamische Datenstrukturen sind in der Programmierung essenzielle Datenbehälter (Container) für Objekte. Sie reservieren flexibel und zur Laufzeit des Programms Arbeitsspeicher und können somit eine theoretisch unbegrenzte Anzahl von Objekten aufnehmen. Im Gegensatz zu Arrays (Datenfeldern), die eine statische, bei der Initialisierung festgelegte Länge besitzen, bieten dynamische Datenstrukturen die notwendige Flexibilität bei der Verwaltung variabler Datenmengen.

Einführung

In komplexen Softwareanwendungen müssen häufig sehr viele Objekte verwaltet und effizient organisiert werden. Ein klassischer Behälter hierfür ist das Array. Da ein Array jedoch eine feste Größe besitzt, führt dies oft zu Speicherverschwendung (wenn das Array zu groß dimensioniert ist) oder zu Speicherfehlern (wenn das Array zu klein ist). Dynamische Datenstrukturen lösen dieses Problem, indem sie Mechanismen bereitstellen, um den reservierten Speicherplatz mit jeder hinzugefügten oder entfernten Dateneinheit dynamisch anzupassen[cite: 3].

Bekannte Beispiele für abstrakte, dynamische Datenstrukturen sind:

Schlange (Queue)
Stapel (Stack)
Liste (List)

Der insgesamt reservierbare Arbeitsspeicher ist dabei lediglich durch die Systemressourcen und den verwendeten Datentyp begrenzt. In der beruflichen Praxis und der Anwendungsentwicklung ist es eine Kernkompetenz, die Effizienz und Einsatzmöglichkeiten dieser Strukturen analysieren und eigene, maßgeschneiderte Strukturen entwerfen zu können[cite: 4].

Knoten als Basis dynamischer Strukturen

Während man einfache Listen auch mittels intern vergrößerbarer Arrays umsetzen kann, werden klassische dynamische Datenstrukturen häufig über Knoten (engl. Node) realisiert.

Ein Knoten ist ein Instanzobjekt einer speziellen Klasse, das neben den eigentlichen Nutzdaten auch mindestens einen Zeiger (Referenz) auf einen anderen Knoten enthält. Durch diese Verkettung von Objekten im Arbeitsspeicher entsteht eine vernetzte Datenstruktur (z. B. eine verkettete Liste).

Ein Zeiger kann auf einen konkreten Nachfolgeknoten verweisen.
Ein Zeiger kann auf null (nichts) verweisen, was in der Regel das Ende der Struktur markiert.
Mindestens ein Zeiger (meist start, head oder root genannt) muss im Hauptprogramm auf das erste Element verweisen, da die Struktur sonst vom Garbage Collector aus dem Speicher gelöscht wird.

Je nach Aufbau der Zeiger unterscheidet man verschiedene Arten von Knoten:

Unidirektionale Knoten

Unidirektional (aus dem Lateinischen uni für „ein“) bedeutet, dass die Verkettung nur in eine einzige Richtung verläuft. Ein unidirektionaler Knoten speichert exakt eine Referenz auf seinen Nachfolger. Eine Navigation zurück zum Vorgänger ist in dieser Struktur nicht möglich.

Bidirektionale Knoten

Ein bidirektionaler Knoten (lateinische Vorsilbe bi- für „zwei“) speichert Zeiger in zwei Richtungen. Er verweist sowohl auf seinen direkten Nachfolger als auch auf seinen direkten Vorgänger. Dies ermöglicht die Vorwärts- und Rückwärtsnavigation innerhalb der Datenstruktur, erfordert jedoch geringfügig mehr Arbeitsspeicher für den zusätzlichen Zeiger.

Implementierungsbeispiel (Java)

Das folgende Beispiel veranschaulicht den Aufbau einer einfachen, unidirektional verketteten Liste in der objektorientierten Programmierung.

Visuelle Repräsentation der verketteten Struktur (Knoten mit Daten und Zeiger): [math]\displaystyle{ meineListe \rightarrow \boxed{5}\boxed{\rightarrow} \rightarrow \boxed{42}\boxed{\rightarrow} \rightarrow \boxed{16}\boxed{\emptyset} }[/math]

Die Knoten-Klasse

Diese Klasse definiert das Speicherobjekt. Sie beinhaltet die Nutzdaten und die Referenz auf das nächste Element.

public class Knoten {
    
    private double daten;      // Nutzdaten, zum Beispiel 5.0 oder 42.0
    private Knoten naechster;  // Zeiger (Referenz) auf den nächsten Knoten

    /**
     * Standardkonstruktor: Erzeugt einen leeren Knoten.
     */
    public Knoten() {
        this.naechster = null; // Zeigt noch nirgendwo hin
    }

    /**
     * Konstruktor zur direkten Übergabe von Nutzdaten.
     */
    public Knoten(double pDaten) {
        this.daten = pDaten;
        this.naechster = null;
    }

    /**
     * Konstruktor zur Übergabe von Daten und Setzen des Nachfolgers.
     */
    public Knoten(double pDaten, Knoten pNext) {
        this.daten = pDaten;
        this.naechster = pNext;
    }

    // --- Getter- und Setter-Methoden zur Datenkapselung ---

    public Knoten getNaechster() {
        return this.naechster;
    }

    public void setNaechster(Knoten pNaechster) {
        this.naechster = pNaechster;
    }
    
    public double getDaten() {
        return this.daten;
    }
    
    public void setDaten(double pDaten) {
        this.daten = pDaten;
    }
}

Die Listen-Klasse

Die verwaltende Klasse kapselt die Zugriffslogik und speichert den Startpunkt der Struktur.

public class Liste {
    
    private Knoten start; // Zeiger auf das erste Element der Liste

    public Liste() {
        this.start = null; // Eine neu erzeugte Liste ist anfangs leer
    }

    /**
     * Testmethode zur manuellen Erzeugung und Verkettung von drei Knoten.
     */
    public void testen() {
        // 1. Startknoten als Platzhalter initialisieren
        this.start = new Knoten();
        
        // 2. Weitere Knoten mit Werten erzeugen
        Knoten knoten1 = new Knoten(5.0);
        Knoten knoten2 = new Knoten(16.0);
        Knoten knoten3 = new Knoten(42.0);
        
        // 3. Knotenlogik: Die Objekte miteinander verketten
        this.start.setNaechster(knoten1);
        knoten1.setNaechster(knoten2);
        knoten2.setNaechster(knoten3);
        // knoten3.getNaechster() ist weiterhin null und markiert das Listenende.
    }

    public Knoten getStart() {
        return this.start;
    }
}

Das Java Collection Framework

In der professionellen Softwareentwicklung (Software Engineering) müssen diese fundamentalen Datenstrukturen in der Regel nicht von Grund auf neu programmiert werden[cite: 3]. Java fasst fertig implementierte, typisierte und hochoptimierte Datenbehälter im Java Collection Framework zusammen.

Neben den eigentlichen Containern gehören hierzu auch mächtige Standardalgorithmen, wie beispielsweise effiziente Sortierverfahren oder Suchalgorithmen, die direkt auf den Containern operieren. Die Grundlage dieses Frameworks sind sogenannte Interfaces (Schnittstellen), die das Verhalten der Datencontainer vertraglich vorgeben.

Die Klasse java.util.ArrayList ist beispielsweise eine in der Praxis extrem häufig genutzte dynamische Datenstruktur, die das List-Interface (ein Sub-Interface der Oberschnittstelle Collection) implementiert.
In der flexiblen Listenstruktur der ArrayList können zur Laufzeit beliebig viele Objekte hinzugefügt und auch wieder entfernt werden, da sich die Datenstruktur im Hintergrund selbstständig vergrößert oder verkleinert.