FLBK-Wiki

Dynamische Datenstruktur: Unterschied zwischen den Versionen

← Zum vorherigen Versionsunterschied

Flbkwikiadmin (Diskussion | Beiträge)

3 Benutzergruppen
2.286 Bearbeitungen
VisuellWikitext
Keine Bearbeitungszusammenfassung
Keine Bearbeitungszusammenfassung
 
(5 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 1: Zeile 1:
'''Dynamische Datenstrukturen''' sind in der Programmierung Behälter für [[Objekt|Objekte]], die eine flexible Menge an Arbeitsspeicher reservieren und somit eine beliebige Anzahl von Objekten aufnehmen können. Im Gegensatz zu [[Array|Arrays]] mit fester Länge bieten sie mehr Flexibilität bei der Verwaltung von Datenmengen.
'''Dynamische Datenstrukturen''' sind in der [[Programmierung]] essenzielle Datenbehälter (Container) für [[Objekt]]e. Sie reservieren flexibel und zur Laufzeit des Programms Arbeitsspeicher und können somit eine theoretisch unbegrenzte Anzahl von Objekten aufnehmen. Im Gegensatz zu [[Array]]s (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 ==
== 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:
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].


[[Warteschlange (Datenstruktur)|Schlange (Queue)]]
Bekannte Beispiele für abstrakte, dynamische Datenstrukturen sind:
* [[Schlange]] (Queue)
* [[Stapel]] (Stack)
* [[Liste]] (List)


[[Stapelspeicher|Stapel (Stack)]]
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].


[[Liste (Datenstruktur)|Liste (List)]]
== 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.


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.
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 <code>null</code> (nichts) verweisen, was in der Regel das Ende der Struktur markiert.
* Mindestens ein Zeiger (meist <code>start</code>, <code>head</code> oder <code>root</code> genannt) muss im Hauptprogramm auf das erste Element verweisen, da die Struktur sonst vom ''Garbage Collector'' aus dem Speicher gelöscht wird.


== Knoten ==
Je nach Aufbau der Zeiger unterscheidet man verschiedene Arten von 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 [[Zeiger|Zeigern]] zu verketten sind, so dass eine Listenstruktur entsteht. Eine Knoteninstanz kann mehrere Zeiger besitzen. Zeiger können auf nichts (Wert <code>null</code>), auf einen anderen oder auf den eigenen Knoten zeigen. Mindestens ein Zeiger muss "von außen" auf die Struktur verweisen (im Bild der Zeiger <code>start</code>). Welche Daten in einem Knoten verwaltet werden, wird in der zugehörigen Klasse durch [[Instanzvariable]]n definiert. Die Knoten können unidirektional oder bidirektional angelegt werden.


=== Unidirektional ===
=== Unidirektionale Knoten ===
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.
[[Datei:Unidirektionaler Knoten.png|mini|Schematische Darstellung eines unidirektionalen Knotens]]
[[Datei:Unidirektionaler Knoten.png|mini]]
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.
=== 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.
=== Bidirektionale Knoten ===
[[Datei:Bidirektionaler Knoten.png|mini]]
[[Datei:Bidirektionaler Knoten.png|mini|Schematische Darstellung eines bidirektionalen Knotens]]
== Beispiel ==
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.
 
[[Datei:BlueJ Inspektion.png|mini|Darstellung der Objektverkettung im Speicher]]
 
Visuelle Repräsentation der verketteten Struktur (Knoten mit Daten und Zeiger):
<math>
<math>
meineListe \rightarrow \boxed{5}\boxed{\phantom{5}}
meineListe \rightarrow \boxed{5}\boxed{\rightarrow}  
\rightarrow \boxed{42}\boxed{\phantom{42}}
\rightarrow \boxed{42}\boxed{\rightarrow}  
\rightarrow \boxed{16}\boxed{\phantom{16}}
\rightarrow \boxed{16}\boxed{\emptyset}
</math>
</math>
=== Die Knoten-Klasse ===
Diese Klasse definiert das Speicherobjekt. Sie beinhaltet die Nutzdaten und die Referenz auf das nächste Element.
<syntaxhighlight lang="java">
<syntaxhighlight lang="java">
public class Knoten {
public class Knoten {
private double daten; // Attribut mit Daten zum Beispiel 5 oder 42
   
private Knoten naechster; // Zeiger auf den nächsten Knoten
    private double daten;     // Nutzdaten, zum Beispiel 5.0 oder 42.0
    private Knoten naechster; // Zeiger (Referenz) auf den nächsten Knoten


// einfacher Konstruktor
    /**
public Knoten() {
    * Standardkonstruktor: Erzeugt einen leeren Knoten.
    naechster = null; // zeigt noch nirgendwo hin
    */
}
    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;
    }


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


// Konstruktor mit Ziel
     // --- Getter- und Setter-Methoden zur Datenkapselung ---
public Knoten(double n, Knoten next) {
    daten = n;
     naechster = next; // zeigt auf den nächsten Knoten
}


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


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


<syntaxhighlight lang="java"> public class Liste { private Knoten start;
=== Die Listen-Klasse ===
text
Die verwaltende Klasse kapselt die Zugriffslogik und speichert den Startpunkt der Struktur.
public void testen() {
 
    start = new Knoten();
<syntaxhighlight lang="java">
    Knoten knoten1 = new Knoten(5.0);
public class Liste {
    Knoten knoten2 = new Knoten(16.0);
    Knoten knoten3 = new Knoten(42.0);
      
      
     start.setNaechster(knoten1);
     private Knoten start; // Zeiger auf das erste Element der Liste
    knoten1.setNaechster(knoten2);
 
    knoten2.setNaechster(knoten3);
    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() {
    public Knoten getStart() {
    return start;
        return this.start;
}
    }
}
}
</syntaxhighlight>
</syntaxhighlight>
[[Datei:BlueJ Inspektion.png|mini]]
== 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 [[Sortierverfahren|Sortieren]] dazu, die auf den Containern arbeiten. Die Grundlage dieses Frameworks sind so genannte Interfaces, die das typische Verhalten der Datencontainer vorgeben.


Die Klasse <code>java.util.ArrayList</code> ist z.B. eine dynamische Datenstruktur, die das <code>List</code>-Interface - ein Subinterface von <code>Collection</code> - implementiert hat. In der Listenstruktur der <code>ArrayList</code> können beliebig viele Objekte hinzugefügt und dann auch wieder entfernt werden.
== 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 <code>java.util.ArrayList</code> ist beispielsweise eine in der Praxis extrem häufig genutzte dynamische Datenstruktur, die das <code>List</code>-Interface (ein Sub-Interface der Oberschnittstelle <code>Collection</code>) implementiert.  
* In der flexiblen Listenstruktur der <code>ArrayList</code> 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.


[[Kategorie:Programmierung]]
[[Kategorie:Programmierung]]
[[Kategorie:FI_I_SDM]]
[[Kategorie:FI I SDM]]
[[Kategorie:FI I TP1]]
[[Kategorie:AHR I Informatik LK]]
Abgerufen von „https://wiki.flbk-hamm.de/Dynamische_Datenstruktur“