StoutList in Java: Eine doppelt verkettete Liste mit Knoten-Arrays – Tutorial zu Coms 2280 Projekt 3

Einführung in die StoutList

Die StoutList ist eine besondere Form einer doppelt verketteten Liste, bei der jeder Knoten ein Array fester Größe M (eine positive gerade Zahl) speichert. Statt dass jeder Knoten nur ein Element enthält, können hier bis zu M Elemente in einem Knoten liegen. Das reduziert die Anzahl der Knoten und verbessert die Cache-Effizienz – ähnlich wie bei modernen Datenbanken, die Seitenweise speichern. In diesem Tutorial zeigen wir dir, wie du eine solche Liste in Java implementierst, basierend auf der Aufgabenstellung von Coms 2280 Projekt 3.

Stell dir vor, du entwickelst eine Playlist-App für das Summer Music Festival 2026: Jeder Knoten ist wie ein Album, das bis zu M Songs enthält. Wenn ein Album voll ist, wird ein neues angelegt. Das ist genau das Prinzip der StoutList.

Warum eine StoutList?

Normale verkettete Listen haben einen hohen Speicher-Overhead pro Element (Pointer). Durch die Bündelung mehrerer Elemente in einem Knoten sparst du Speicher und verbesserst die Lokalität. Das ist besonders nützlich für Echtzeitanwendungen wie Gaming-Server, die viele Spielerdaten verwalten, oder für KI-Trainingspipelines, die große Datenmengen puffern.

Grundstruktur der StoutList

Die StoutList erweitert AbstractSequentialList und verwendet Dummy-Knoten für Kopf und Ende. Ein leerer Knoten hat count = 0 und ein leeres Array. Die Knoten sind doppelt verkettet. Hier ein minimales Node-Gerüst:

private class Node {
    E[] data;
    Node prev, next;
    int count;
    @SuppressWarnings("unchecked")
    Node() {
        data = (E[]) new Object[M];
        count = 0;
    }
}

Die Methode find(int pos) ermittelt den Knoten und Offset für einen logischen Index, ohne jedes Element einzeln zu durchlaufen. Das ist essenziell für effiziente Index-Operationen.

Implementierung der add-Methoden

Das Hinzufügen am Ende (add(E item)) ist einfach: Wenn der letzte Knoten noch Platz hat, wird das Element dort eingefügt. Sonst wird ein neuer Knoten erstellt. Bei add(int pos, E item) kann ein Split nötig sein, wenn der Knoten voll ist. Die Splitt-Regel: Ein voller Knoten wird in zwei Knoten aufgeteilt, wobei der erste M/2 Elemente behält und der zweite die restlichen M/2 plus das neue Element erhält. Das sorgt dafür, dass alle Knoten außer dem letzten mindestens halb voll sind.

Trend-Beispiel: Stell dir vor, du verwaltest ein Leaderboard für ein E-Sports-Turnier (z.B. FIFAe World Cup 2026). Jeder Knoten speichert Ranglisteneinträge. Wenn ein Knoten voll ist, wird er gesplittet, um neue Spieler aufzunehmen – ähnlich wie bei einer B-Tree-Struktur.

Remove-Operationen und Merge

Beim Entfernen eines Elements kann ein Knoten unter die Mindestgrenze fallen (weniger als M/2 Elemente). Dann wird versucht, mit dem Nachbarknoten zu mergen: Entweder werden Elemente von einem Nachbarn übernommen (Borrow) oder die beiden Knoten werden zu einem zusammengelegt (Merge). Diese Regeln ähneln denen von B-Bäumen und sorgen für eine ausgeglichene Struktur.

Iterator-Implementierung

Die StoutListIterator muss die Methoden next(), previous(), add(), remove() und set() unterstützen. Der Iterator merkt sich den aktuellen Knoten und Offset. Besonders knifflig: Nach einem add oder remove kann sich die Knotenstruktur ändern, sodass der Iterator aktualisiert werden muss.

Häufige Fehler und Tipps

• NullPointerException vermeiden: Alle add-Methoden müssen null-Elemente ablehnen.
• Korrekter Split: Achte darauf, dass nach einem Split der erste Knoten genau M/2 Elemente hat (außer bei Sonderfällen).
• Iterator-Update: Bei add/remove im Iterator muss der Cursor korrekt positioniert werden.

Testen mit toStringInternal()

Die Methode toStringInternal() zeigt die interne Struktur an. Beispiel: Nach Einfügen von "A", "B", "C", "D", "E" bei M=4 erhältst du [(A, B, -, -), (C, D, E, -)]. Nutze diese Methode zum Debuggen.

Zusammenfassung

Die StoutList kombiniert die Vorteile von Arrays und verketteten Listen. Sie ist ideal für Anwendungen, die häufige Einfügungen und Löschungen erfordern, aber auch wahlfreien Zugriff benötigen – wie z.B. Texteditoren mit Undo-Funktion oder KI-Agenten, die Aktionssequenzen speichern. Mit diesem Tutorial hast du einen soliden Einstieg in die Implementierung. Viel Erfolg bei deinem Projekt!