Verkettete Liste

Anleitung

Implementiere eine doppelt verkettete Liste.

Wie ein Array ist eine verkettete Liste eine einfache lineare Datenstruktur. Mit verketteten Listen lassen sich mehrere gängige Datentypen implementieren, zum Beispiel Warteschlangen, Stacks und assoziative Arrays.

Eine verkettete Liste ist eine Sammlung von Datenelementen, die Knoten genannt werden. In einer einfach verketteten Liste enthält jeder Knoten einen Wert und eine Verknüpfung zum nächsten Knoten. In einer doppelt verketteten Liste enthält jeder Knoten zusätzlich eine Verknüpfung zum vorherigen Knoten.

Du schreibst eine Implementierung einer doppelt verketteten Liste. Implementiere einen Node, der einen Wert und Zeiger auf den nächsten und den vorherigen Knoten enthält. Dann implementierst du eine List, die Verweise auf den ersten und den letzten Knoten speichert und eine array-ähnliche Schnittstelle zum Hinzufügen und Entfernen von Elementen bietet:

• push (fügt einen Wert am Ende ein);
• pop (entfernt den Wert am Ende);
• shift (entfernt den Wert am Anfang).
• unshift (fügt einen Wert am Anfang ein);

Damit deine Implementierung einfach bleibt, decken die Tests keine Fehlerfälle ab. Genauer gesagt: pop oder shift werden nie auf einer leeren Liste aufgerufen.

Lies mehr über verkettete Listen auf Wikipedia.