Dynamische Datenstruktur

Dynamische Datenstrukturen sind in der Programmierung Behälter für Objekte, die eine flexible Menge an Arbeitsspeicher reservieren und somit eine beliebige Anzahl von Objekten aufnehmen können. Im Gegensatz zu Arrays mit fester Länge bieten sie mehr Flexibilität bei der Verwaltung von Datenmengen.

Einführung

In einem Programm werden oft mehrere Objekte einer Klasse verwaltet. Diese müssen in Behältern organisiert werden. Ein Beispiel für einen solchen Behälter ist das Array. Da ein Array immer eine feste Länge hat, ist es für viele Zwecke allerdings zu unflexibel. Beispiele für dynamische Datenstrukturen sind:

Schlange (Queue)

Stapel (Stack)

Liste (List)

Der reservierte Arbeitsspeicher ist abhängig vom Datentyp der gespeicherten Objekte. Dynamische Datenstrukturen bieten Mechanismen, den reservierten Speicher mit jeder hinzugefügten Dateneinheit zu vergrößern. In manchen Situationen ist es erforderlich, eigene Strukturen zu entwerfen, die Objekte dynamisch verwalten.

Knoten

Dynamische Datenstrukturen lassen sich mit Arrays oder Knoten realisieren. Ein Knoten ist ein Objekt einer Klasse. Die Klasse definiert, wie ihre Instanzen mit Hilfe von Zeigern zu verketten sind, so dass eine Listenstruktur entsteht. Eine Knoteninstanz kann mehrere Zeiger besitzen. Zeiger können auf nichts (Wert null), auf einen anderen oder auf den eigenen Knoten zeigen. Mindestens ein Zeiger muss "von außen" auf die Struktur verweisen (im Bild der Zeiger start). Welche Daten in einem Knoten verwaltet werden, wird in der zugehörigen Klasse durch Instanzvariablen definiert. Die Knoten können unidirektional oder bidirektional angelegt werden.

Unidirektional

Unidirektional (lateinisch uni für „ein“) bedeutet, dass mit Hilfe eines Zeigers nur in eine Richtung verwiesen wird. So kann zum Beispiel ein unidirektionaler Knoten nur auf seinen Nachfolger, nicht aber auf seinen Vorgänger verweisen.

Bidirektional

Ein bidirektionaler (nach der lateinischen Vorsilbe bi- für „zwei“) Knoten kann in zwei Richtungen verweisen. So kann zum Beispiel ein bidirektionaler Knoten nicht nur auf seinen Nachfolger, sondern auch zusätzlich auf seinen Vorgänger verweisen.

Beispiel

[math]\displaystyle{ meineListe \rightarrow \boxed{5}\boxed{\phantom{5}} \rightarrow \boxed{42}\boxed{\phantom{42}} \rightarrow \boxed{16}\boxed{\phantom{16}} }[/math]

public class Knoten {
private double daten; // Attribut mit Daten zum Beispiel 5 oder 42
private Knoten naechster; // Zeiger auf den nächsten Knoten

// einfacher Konstruktor
public Knoten() {
    naechster = null; // zeigt noch nirgendwo hin
}

// einfacher Konstruktor
public Knoten(double n) {
    daten = n;
    naechster = null; // zeigt noch nirgendwo hin
}

// Konstruktor mit Ziel
public Knoten(double n, Knoten next) {
    daten = n;
    naechster = next; // zeigt auf den nächsten Knoten
}

// Getter und Setter
public Knoten getNaechster() {
    return naechster;
}

public void setNaechster(Knoten naechster) {
    this.naechster = naechster;
}
}

 public class Liste { private Knoten start;
text
public void testen() {
    start = new Knoten();
    Knoten knoten1 = new Knoten(5.0);
    Knoten knoten2 = new Knoten(16.0);
    Knoten knoten3 = new Knoten(42.0);
    
    start.setNaechster(knoten1);
    knoten1.setNaechster(knoten2);
    knoten2.setNaechster(knoten3);
}

public Knoten getStart() {
    return start;
}
}

Collection Framework

Java fasst die bereitgestellten Datenbehälter im Java Collection Framework zusammen. Neben den eigentlichen Containern gehören auch noch Standardmethoden wie beispielsweise das Sortieren dazu, die auf den Containern arbeiten. Die Grundlage dieses Frameworks sind so genannte Interfaces, die das typische Verhalten der Datencontainer vorgeben.

Die Klasse java.util.ArrayList ist z.B. eine dynamische Datenstruktur, die das List-Interface - ein Subinterface von Collection - implementiert hat. In der Listenstruktur der ArrayList können beliebig viele Objekte hinzugefügt und dann auch wieder entfernt werden.