Dynamische Datenstruktur
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:
Dynamische Datenstrukturen bezeichnen Variablen, die eine flexible Menge an Arbeitsspeicher reservieren und somit eine beliebige Anzahl von Objekten aufnehmen können. Grundsätzlich ist der reservierte Arbeitsspeicher 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 Zeigerstart). 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.
Unidirektion
Unidirektional (lateinischen uni für „ein“) bedeutet, dass mit Hilfe eines Zeigers nur in eine Richtung verwiesen wird. So kann zum Beispiel eine unidirektionaler Konten nur auf seine Nachfolger, nicht aber auf seinen Vorgänger verweisen.
Bidirektionaler
Ein bidirektionaler (nach der lateinischen Vorsilbe bi- für „zwei“) Knoten kann in zwei Richtungen verweisen. So kann zum Beispiel eine bidirektionaler Konten nicht nur auf seine Nachfolger sondern auch zusätzlich auf seinen Vorgänger verweisen.
Beispiel
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;
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 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.