Listen und Felder
- Wie lässt sich „Listen und Felder“ mit einem Modell erklären?
- Ist die Anweisung für jede Person eindeutig und endet der Ablauf sicher?
- Wie kann ich meine Lösung testen und verständlich dokumentieren?
Doppelt verkettete Liste
In einer doppelt verketteten Liste enthält jedes Listenelement jeweils einen Verweis zum Vorgänger und zum Nachfolger in der Liste. Durch diese Verweise reihen sich die Listenelemente zu einer Liste.
Bei einer einfach verketteten Liste enthält jedes Listenelement nur einen Verweis zum Nachfolger in der Liste. Hierbei gestaltet sich jedoch das Einfügen und Entfernen von Listenelementen als schwieriger. Daher werden in der Praxis meist doppelt verkettete Listen verwendet.
Die Listenelemente, hier bezeichnet als Knoten, enthalten folgende Informationen:
- ein Datenelement data,
- einen Verweis pred auf den vorhergehenden Knoten in der Liste (predecessor - Vorgänger),
- einen Verweis succ auf den nachfolgenden Knoten in der Liste (successor - Nachfolger),.
Der Datentyp des Attributs data ist hier zunächst als Typ-Parameter Type angegeben. Wenn du später eine Liste erzeugst, gibst du den tatsächlichen Datentyp der Listenelemente an, also zum Beispiel Integer oder String.
Liste implementieren: Version 1
Im Prinzip sieht eine Liste mit drei Knoten folgendermaßen aus:
Der erste Knoten der Liste ist mit init bezeichnet. Er dient als Einstieg in die Liste. Am Anfang der Liste kannst du Knoten besonders einfach einfügen oder entfernen. In der Mitte der Liste dagegen ist dies insofern schwieriger, als dass du dich erst entlang der Nachfolger-Verweise vom Anfang bis zur Mitte vorarbeiten musst. Damit du auch am Ende der Liste mit wenig Aufwand Knoten einfügen und entfernen kannst, bezeichnest du den letzten Knoten der Liste mit last.
Im Prinzip kannst du eine doppelt verkettete Liste so implementieren. Die Implementierung ist aber wenig elegant, weil für das Einfügen und Entfernen von Knoten mehrere Fallunterscheidungen erforderlich sind, je nachdem, ob dies am Anfang, am Ende oder irgendwo in der Mitte der Liste geschieht.
Das Hauptproblem aber ist: Wie implementierst du eine leere Liste? Eine Liste kann leer sein, also kein Listenelement enthalten.
Stell dir vor, du führst eine Liste von Bestellungen. Wenn eine Bestellung hereinkommt, wird sie in die Liste eingefügt. Wenn eine Bestellung ausgeführt ist, wird sie aus der Liste entfernt. Wenn alle Bestellungen ausgeführt sind, ist die Liste leer – sie soll aber weiter existieren, für den Fall, dass wieder eine Bestellung hereinkommt.
Liste implementieren: Version 2
Du implementierst eine doppelt verkettete Liste in sehr eleganter Weise, wenn du die Knoten init und last quasi als Pseudo-Knoten realisierst: Knoten, die kein Datenelement enthalten, sondern nur dazu da sind, den Anfang und das Ende der Liste zu markieren.
Die leere Liste sieht dann so aus:
Wenn du eine Liste neu erzeugst, ist sie zunächst leer, sie enthält noch keinen Eintrag, sondern besteht nur aus den Pseudo-Knoten init und last.
Das Einfügen und Entfernen von Knoten kommt ohne Fallunterscheidungen aus. Schau dir die folgende Implementierung einmal an. Was beim Einfügen eines Knotens passiert, ist im Anschluss daran noch einmal gezeigt.
Knoten in die Liste einfügen
Mit der Methode add fügst du einen neuen Knoten am Ende der Liste ein. Hierzu änderst du die Verweise zwischen den Knoten last und last.pred so, dass sich der neue Knoten node dazwischen einreiht.
Die Liste durchlaufen
Du durchläufst die Liste von vorne bis hinten mithilfe eines Iterators. Der Iterator enthält einen Verweis auf das aktuelle Objekt, bezeichnet als Cursor-Objekt. Mit der Funktion next gibt er das aktuelle Objekt zurück und schaltet zum nächsten Objekt weiter. Die Funktion hasNext gibt true zurück, solange noch weitere Objekte kommen, ansonsten gibt sie false zurück.
Iterator nutzen
Um den Iterator nutzen zu können, änderst du noch zwei Dinge an der Klasse LinkedList:
- Du ergänzt die Kopfzeile der Klasse:
- Und du fügst die Methode iterator ein:
Dann kannst du im Hauptprogramm mit einer For-Each-Schleife die Liste durchlaufen. Am besten fügst du in die Klasse LinkedList die folgende Main-Methode ein, um einen kurzen Test durchzuführen:
Liste implementieren Version 3: Zirkuläre Liste
Besonders elegant implementierst du eine doppelt verkettete Liste, indem du sie zu einem Kreis zusammen biegst. Dann übernimmt der Knoten init gleichzeitig die Rolle des Knotens last. Der Knoten last wird nicht mehr gebraucht.
Die leere Liste als zirkuläre Liste
In dieser Implementierung besteht die leere Liste nur aus dem Pseudo-Knoten init. Dieser verweist mit den Verweisen predecessor und successor auf sich selbst.
Im Konstruktor der Liste erzeugst du den Knoten init mit den entsprechenden Verweisen.
Knoten einfügen
In ähnlicher Weise wie in der Implementierung Version 2 fügst du mit der Methode add einen neuen Knoten am Ende der Liste ein.
Die Methode add funktioniert auch zu Beginn, wenn die Liste noch leer ist und nur aus dem Knoten init besteht.
Zum Üben
Nun bist du am Zug:
- Ändere die Implementierung von Version 2 entsprechend ab, dass eine zirkuläre Liste entsprechend Version 3 entsteht.
- Ändere den Iterator entsprechend ab, dass er die zirkuläre Liste durchläuft.
- Verwende die ungeänderte Main-Funktion, um deine Implementierung zu testen.
Wenn alles funktioniert und du noch Lust dazu hast, leite die Klassen Queue und Stack mit entsprechenden Änderungen von deiner neuen Klasse LinkedList ab.
Erklärung von Serlo Education e. V., lizenziert unter CC BY-SA 4.0 – Original bei Serlo, CC BY-SA 4.0, übernommen am 2026-09-03.
Schlau Fassung
Listen und Felder Ein Feld (Array) hat feste Länge und erlaubt den direkten Zugriff über einen Index. Eine Liste wächst dynamisch, ihre Elemente verweisen aufeinander.
Listen und Felder ist in der Informatik kein isolierter Merksatz. Entscheidend ist, welche Daten oder Zustände am Anfang vorliegen, nach welcher Regel sie verarbeitet werden und wie sich das Ergebnis überprüfen lässt. Auf das dritte Element eines Feldes greift man sofort zu; in einer verketteten Liste hangelt man sich vom Anfang durch.
Beim Bearbeiten trennst du deshalb Beobachtung und Vermutung: Zuerst beschreibst du, was tatsächlich eingegeben, gespeichert, übertragen oder ausgegeben wird. Danach begründest du mit Fachbegriffen, warum der Ablauf so funktioniert.
Drei Bausteine, die du sicher können musst
Jeder Schritt ist ohne Raten ausführbar.
Der Ablauf erreicht nach endlich vielen Schritten ein Ende.
Eingabe und erwartetes Ergebnis prüfen einen bestimmten Weg.
Ausgearbeitetes Beispiel
Ausgangslage: Auf das dritte Element eines Feldes greift man sofort zu; in einer verketteten Liste hangelt man sich vom Anfang durch.
- Modell festlegen: Benenne Eingaben, gespeicherte Werte und die gewünschte Ausgabe.
- Regel anwenden: Formuliere die Verarbeitung so genau, dass eine andere Person jeden Schritt wiederholen kann.
- Ergebnis prüfen: Vergleiche die beobachtete Wirkung mit einer vorher notierten Erwartung und untersuche mindestens einen Randfall.
Begründung: Ein Feld (Array) hat feste Länge und erlaubt den direkten Zugriff über einen Index. Eine Liste wächst dynamisch, ihre Elemente verweisen aufeinander. Dadurch wird nicht nur das Ergebnis, sondern auch sein Zustandekommen nachvollziehbar.
So gehst du informatisch vor
Fachbegriffe in eigenen Worten
- Eindeutigkeit
- Jeder Schritt ist ohne Raten ausführbar.
- Endlichkeit
- Der Ablauf erreicht nach endlich vielen Schritten ein Ende.
- Testfall
- Eingabe und erwartetes Ergebnis prüfen einen bestimmten Weg.
Aufgaben
- StartBegriffe sichern: Erkläre „Listen und Felder“ in mindestens vier Sätzen und verwende zwei Begriffe aus dem Glossar.
Musterlösung
Ein Feld (Array) hat feste Länge und erlaubt den direkten Zugriff über einen Index. Eine Liste wächst dynamisch, ihre Elemente verweisen aufeinander. Auf das dritte Element eines Feldes greift man sofort zu; in einer verketteten Liste hangelt man sich vom Anfang durch. Eine vollständige Antwort benennt zusätzlich Eingabe oder Ausgangszustand, Verarbeitung und überprüfbares Ergebnis. - OrdnenModell bilden: Zerlege das Beispiel der Seite in Ausgangslage, Regel, Ergebnis und Test.
Musterlösung
Ausgangslage: die im Beispiel genannten Daten oder Geräte. Regel: der beschriebene Verarbeitungsschritt. Ergebnis: die sichtbare Wirkung. Test: ein normaler Fall und ein bewusst veränderter Randfall. - AnwendenSelbst lösen: Schreibe einen Algorithmus, der eine Figur vom Start durch ein 4-mal-4-Feld zum Ziel führt, ohne ein Hindernis zu berühren.
Musterlösung
Eine korrekte Lösung nennt Startposition und Blickrichtung und gibt jeden Schritt oder jede geprüfte Bedingung eindeutig an. - FehlersucheDiagnose: Verändere im Beispiel genau eine Voraussetzung. Sage vorher, welche Wirkung du erwartest, und begründe sie.
Lösungshinweis
Eine gute Lösung benennt die veränderte Voraussetzung, den betroffenen Verarbeitungsschritt und eine beobachtbare Ausgabe. Mehrere Dinge gleichzeitig zu ändern erlaubt keine eindeutige Ursache. - TransferNeuer Zusammenhang: Finde ein zweites Beispiel aus Schule oder Alltag und erkläre Gemeinsamkeit sowie Unterschied.
Lösungshinweis
Nutze dieselben Fachbegriffe, aber übertrage sie auf andere Daten, Geräte oder Regeln. Der Unterschied muss fachlich relevant sein und darf nicht nur den Namen betreffen. - ProfiVertiefung: Kürze eine lange Befehlsfolge durch eine Schleife und erkläre, warum beide Fassungen dasselbe leisten.
Lösungshinweis
Suche zuerst den kleinsten Abschnitt, der unverändert mehrfach vorkommt, und bestimme danach die Wiederholungszahl.
Weiterführende Aufgaben
Abgabe in fünf Teilen
- Ziel: Ein Satz, der messbar sagt, was funktionieren soll.
- Plan: Skizze, Ablaufplan, Tabelle oder Pseudocode.
- Produkt: Programm, Modell, Untersuchung oder dokumentierter Versuch.
- Tests: Normalfall, Randfall und mindestens ein absichtlich provozierter Fehler.
- Reflexion: Gefundener Fehler, vorgenommene Verbesserung und nächster sinnvoller Schritt.
Bewertungsraster für Partnerfeedback
- Fachlich richtig und mit passenden Begriffen erklärt
- Plan und Ergebnis stimmen sichtbar überein
- Tests sind reproduzierbar dokumentiert
- Quellen, Bilder und fremde Hilfen sind angegeben