Doppelt verkettete Liste

Intermediate Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Eine doppelt verkettete Liste speichert prev und next. Damit sind Einfügen und Löschen $O(1)$, sobald der Knoten bekannt ist, weil der Vorgänger ohne Suche erreichbar ist.

Kosten: mehr Speicher und mehr Invarianten (beide Richtungen konsistent halten). Am Kopf und am Ende sind Sentinel-Knoten hilfreich.

java.util.LinkedList ist doppelt verkettet und eignet sich für häufige Einfüge-/Löschoperationen an den Enden.

Wo gebraucht

LRU-Caches (Knoten bei Zugriff nach vorn hängen), Deques, Browser-History, Texteditor-Rope-Varianten. $O(1)$ Entfernen bei bekanntem Knoten ist der Produktgrund für die doppelte Verkettung.

Vertiefung

Jeder Knoten besitzt Verweise auf Vorgänger und Nachfolger. Für benachbarte Knoten gilt als Invariante, dass Vorwärts- und Rückwärtsverweis zueinander passen. Änderungen müssen beide Richtungen aktualisieren.

Ist ein Knoten bereits bekannt, kann er lokal entfernt werden, ohne seinen Vorgänger durch Suche zu bestimmen. Der Indexzugriff bleibt jedoch linear. Ein gespeicherter Endverweis erlaubt zusätzlich konstantes Einfügen und Entfernen am hinteren Ende.

Wächter an beiden Enden reduzieren Sonderfälle. Leere und nichtleere Zustände verwenden dann dieselben vier Verweisaktualisierungen, während die Wächter selbst nie Nutzdaten darstellen.

Schwierigkeitsstufen

Vorwärts- und Rückwärtsinvarianten prüfen.
Einen bekannten inneren Knoten sicher entfernen.
Wächterknoten gegen explizite Randfallbehandlung abwägen.

Fallstricke

Nur eine Richtung zu aktualisieren erzeugt eine Struktur, die in einem Durchlauf korrekt und im Rückwärtslauf beschädigt wirkt. Entfernte Knoten sollten ausserdem von ihren Nachbarn getrennt werden.

University approvals: 0

Tasks

Question 1

Welcher Vorteil der doppelt verketteten Liste ist zentral?

Indexzugriff in O(1)

Löschen eines bekannten Knotens ohne Suche des Vorgängers

Weniger Speicher als einfach verkettet

Automatische Sortierung

Question 2

Welche Bedingung muss für benachbarte Knoten a und b gelten?

Wenn a.next == b, dann b.prev == a.

a.prev und a.next müssen denselben Knoten bezeichnen.

Jeder Knoten muss zwei Nutzdatenelemente besitzen.

Der Kopf muss sein eigener Vorgänger sein.

Question 3

Entferne einen gegebenen Knoten aus einer doppelt verketteten Liste.

Hint

Referenzen können null sein und müssen vor einem Feldzugriff geprüft werden. Die Felder heissen hier prev und next.

public class DoublyList {
  public static class DoublyNode {
    public int value;
    public DoublyNode prev;
    public DoublyNode next;
    public DoublyNode(int value) { this.value = value; }
  }
  public static void remove(DoublyNode node) {
    // TODO
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithmen und Datenstrukturen
Difficulty: Intermediate
Completed: 0 users

Creator

Best

BestBuddy