Einführung

Das Zusammenfassen von Objekten, Datenstrukturen zu einer Menge von Objekten ist eine typische Anforderung in der Informatik. Zur Lösung dieses Anforderung müssen die folgenden Aspekte betrachtet werden:

• Ist die Menge der Objekte statisch oder kann sie sich veränderen. Ist sie dynamisch?
• Bilden die Elemente der Menge eine bestimmte Reihenfolge?
• Ist die Position des Elements in der Menge wichtig? Muss das Objekt über seine Position zugreifbar sein?
• Sollen Elemente zur Laufzeit zur Menge hinzugefügt oder entfernt werden können?
• Reicht es zu wissen, dass ein Element zur Menge gehört?
• Muss der Zugriff der Elemente über eine Nachbarschaftsbeziehung gegeben sein? 
• Müssen die Elemente einer bestimmten Sortierreihenfolge genügen (z. Bsp. lexikographische Ordnung?)
• Ist es erlaubt Duplikate in der Menge zu verwalten?

Beispiele aus dem echten Leben

Welche der oben geforderten Kriterien gelten hier?

• Bierkasten mit Bierflaschen (Antialkoholiker mögen mit einem Kasten Sprudel arbeiten)
• Schulheft mit Seiten
• Ringbuch mit Seiten
• Ringbuch mit Seiten und Trennern

Felder

Die bisher verwendete Datenstruktur zum Verwalten von Objekten war das Feld (Array). Ein Feld hat die folgenden Vorteile:

• Sehr schneller, indexierter Zugriff auf ein Objekt über dessen Position im Feld: O(1)
• Konstante Größe

Diesen Vorteilen stehen die folgenden Nachteile gegenüber:

• Aufwändiges Einfügen: O(n)
• Feld muss bei einer nötigen Vergrößerung umkopiert werden.

Die Referenz ist die zweite Datenstruktur mit der Objekte verwaltet werden können. Sie erlaubt jedoch nur den direkten Zugriff auf ein einzelnes Objekt.

Dynamische Datenstrukturen

Zur Verwaltung von beliebig vielen Objekten verwendet man dynamische Datenstrukturen in Java die man durch Verkettung von Objekten mit Objektreferenzen erhält.

Die Datenstrukturen sind dynamisch, da während der Laufzeit beliebig viele Objekte in sie eingefügt oder aus ihnen entfernt werden können. Die Anzahl ihrer Objekte (Knoten) ist nicht vorab festgelegt.

Verketteten Datenstrukturen können linear (nicht verzweigt) oder auch verzweigt sein.

• Lineare Datenstrukturen sind typischerweise Listen, Warteschlangen, Stacks
• Verzweigte Datenstrukturen finded man typischerweise in Bäumen

Vertreter dynamischer Datenstrukturen