Referenzen beim Einfügen in sicherer Reihenfolge ändern
Den ersten oder einen nachfolgenden Knoten aus der Liste entfernen
Verständlich erklärt
Eine einfach verkettete Liste besteht aus Knoten. Jeder Knoten enthält Daten und eine Referenz auf seinen Nachfolger. Der Anker ist eine Referenz auf den ersten Knoten; er ist weder dessen Datenwert noch eine zusätzliche Kopie aller Knoten. In unseren Python-Modellen bezeichnet None eine fehlende Referenz: Anker = None bedeutet eine leere Liste, weiter = None das Ende. Die Reihenfolge entsteht durch die Referenzen, nicht durch alphabetische Knotennamen oder räumlich benachbarte Speicherplätze. Beim Traversieren startest du am Anker, liest die Daten und folgst weiter, bis None erreicht ist.
Zum Einfügen am Anfang verweist der neue Knoten zuerst auf den bisherigen Anker; danach wird der Anker auf den neuen Knoten gesetzt. Zum Einfügen nach einem bekannten Knoten p speicherst du zuerst den bisherigen Nachfolger in neu.weiter und setzt erst dann p.weiter auf neu. Andernfalls kann die bisherige Restliste verloren gehen oder eine Selbstreferenz entstehen. Zum Entfernen des ersten Knotens wird der Anker auf dessen Nachfolger gesetzt. Zum Entfernen nach p überspringt p.weiter den entfernten Knoten. Das beschreibt die Erreichbarkeit in der Liste, keine manuelle Speicherfreigabe in Python.
Ein Element an Position k findest du im Allgemeinen durch wiederholtes Folgen von Referenzen; anders als beim Array gibt es hier keinen direkten Indexzugriff. Einfügen nach einem bereits bekannten Vorgänger braucht dagegen nur wenige Referenzänderungen. Wir betrachten wohldefinierte Listen ohne zyklische Verweise.
Anker
Knoten
Daten
Referenz
Nachfolger
None
Traversieren
Beispiel
anker -> A [Daten: 4 | weiter: B]
B [Daten: 9 | weiter: None]
Neuen Knoten N mit Daten 6 nach A einfügen:
1. N.weiter = A.weiter # bisher B
2. A.weiter = N
Ergebnis: anker -> A(4) -> N(6) -> B(9) -> None
N wieder entfernen: A.weiter = N.weiter
Ergebnis: A(4) -> B(9) -> None
Typische Fehler
Den Anker mit dem Datenwert des ersten Knotens verwechseln
Knotennamen statt Referenzen als Reihenfolge verwenden
Beim Einfügen die Referenz auf die Restliste überschreiben
None mit dem gespeicherten Zahlenwert 0 verwechseln
Kurz zusammengefasst
Die Referenzen bestimmen die Reihenfolge. Sichere beim Einfügen zuerst den bisherigen Nachfolger und behandle den Anker sowie die leere Liste ausdrücklich.
Abi-Bezug
Zeichne vor und nach einer Operation Anker und Nachfolger. Begründe die Reihenfolge der Referenzänderungen und unterscheide Suchen vom anschließenden Einfügen.
Jetzt selbst ausprobieren
Prüfe deine Lösung automatisch. Bei Bedarf helfen dir ein Tipp und anschließend die Musterlösung.
BPE 7J21 Punkteleicht
Anker, Daten und Referenz
Noch nicht begonnen
Aufgabenstellung
Ein Anker verweist auf Knoten A. A speichert die Zahl 17 und einen Verweis auf B. Welche Aussagen sind richtig? Wähle alle richtigen Antworten.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Trenne die Frage „Was wird gespeichert?“ von „Wo geht es weiter?“.
Die Nachfolgerreferenz und nicht der Speicherabstand legt die Reihenfolge fest.
Lösung anzeigen
Der Anker verweist auf den ersten Knoten. Ein Knoten trennt Nutzdaten und Nachfolgerreferenz. Die Verkettung verlangt keine benachbarten Speicherplätze.
BPE 7J21 Punkteleicht
Referenzen statt Knotennamen verfolgen
Noch nicht begonnen
Aufgabenstellung
Es gilt anker = b. Knoten b enthält 12 und verweist auf c; c enthält 7 und verweist auf a; a enthält 20 und verweist auf None. Welche Datenwerte werden beim Traversieren gelesen? Antworte kommagetrennt, ohne Klammern.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Beginne bei dem Knoten, auf den der Anker tatsächlich verweist.
Notiere zunächst den Datenwert von b und folge dann jeweils der Nachfolgerreferenz.
Lösung anzeigen
12, 7, 20. Vom Anker b geht es über c zu a. Die alphabetische Ordnung der Knotennamen spielt keine Rolle.
BPE 7J22 Punktemittel
Vorne einen Knoten einfügen
Noch nicht begonnen
Aufgabenstellung
Die Liste enthält vom Anker aus 9 → 14 → None. Der neue Knoten N enthält 5. Nacheinander werden N.weiter = anker und anker = N ausgeführt. Welche Datenfolge entsteht? Antworte kommagetrennt.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Der bisherige erste Knoten wird nicht überschrieben.
Nach beiden Anweisungen beginnt der Weg am neuen Anker N und führt über den früheren Anfang weiter.
Lösung anzeigen
5, 9, 14. N verweist zuerst auf den bisherigen ersten Knoten. Der anschließend geänderte Anker macht N zum neuen Anfang.
BPE 7J22 Punktemittel
Beim Einfügen den Nachfolger erhalten
Noch nicht begonnen
Aufgabenstellung
p hat bereits einen Nachfolger. Ein neuer Knoten neu soll direkt nach p eingefügt werden. Welche Reihenfolge erhält die bisherige Restliste?
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Welche Referenz ist die einzige Verbindung zur bisherigen Restliste?
Lies p.weiter vor dem Überschreiben und speichere diese Referenz in neu.weiter.
Lösung anzeigen
Zuerst übernimmt neu den bisherigen Nachfolger. Erst danach verweist p auf neu. Bei umgekehrter Reihenfolge wäre p.weiter bereits neu; neu.weiter würde dann auf neu selbst zeigen.
BPE 7J22 Punktemittel
Einen mittleren Knoten überspringen
Noch nicht begonnen
Aufgabenstellung
Gegeben ist anker → A(5) → B(8) → C(13) → D(21) → None. Es wird nur A.weiter = B.weiter ausgeführt. Welche Datenwerte sind danach vom Anker aus erreichbar? Antworte kommagetrennt.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Bestimme zuerst, wohin B.weiter vor der Änderung zeigt.
Verfolge danach den Weg vom unveränderten Anker; nur die Referenz in A hat sich geändert.
Lösung anzeigen
5, 13, 21. A verweist nun direkt auf C. B wird vom Listenweg übersprungen; C und D bleiben erreichbar. Eine Aussage über sofortige Speicherfreigabe ist dafür nicht nötig.
BPE 7J22 Punktemittel
Die leere Liste erkennen
Noch nicht begonnen
Aufgabenstellung
In unserem Python-Referenzmodell zeigt der Anker einer leeren Liste auf keinen Knoten. Welcher Python-Wert steht dann in anker? Gib nur diesen Wert an.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Eine leere Liste hat keinen ersten Knoten, auch keinen Knoten mit dem Wert 0.
Gesucht ist Pythons eigener Wert für eine fehlende Referenz.
Lösung anzeigen
None kennzeichnet die fehlende Referenz. 0 könnte ein gültiger Datenwert eines vorhandenen Knotens sein und ist daher kein passender Ersatz für die Leerkennzeichnung.
BPE 7J23 Punkteanspruchsvoll
Daten einer Kette sammeln
Noch nicht begonnen
Aufgabenstellung
Implementiere listenwerte(anker). Ein Knoten ist ein Dictionary mit wert (ganze Zahl) und weiter (nächster Knoten oder None). Der Anker ist der erste Knoten oder None. Gib alle Datenwerte in Listenreihenfolge als neue Python-Liste zurück. Verändere keine Knoten. Die Kette ist endlich und enthält keine zyklischen Verweise.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Verwende eine laufende Referenz und beginne mit einer leeren Ergebnisliste.
Solange aktuell nicht None ist: wert anhängen, dann aktuell durch aktuell['weiter'] ersetzen.
Lösung anzeigen
def listenwerte(anker):
ergebnis = []
aktuell = anker
while aktuell is not None:
ergebnis.append(aktuell['wert'])
aktuell = aktuell['weiter']
return ergebnis
BPE 7J23 Punkteanspruchsvoll
Zugriff und Einfügen unterscheiden
Noch nicht begonnen
Aufgabenstellung
Du kennst bei einer einfach verketteten Liste nur den Anker. Welche Aussagen treffen zu? Wähle alle richtigen Antworten.
Ausgabe bzw. Vorschau
Noch nicht ausgeführt.
2 Tipps anzeigen
Prüfe, welche Referenzen vor dem jeweiligen Arbeitsschritt schon bekannt sind.
Vergleiche „Vorgänger erst finden“ mit „Vorgänger ist gegeben“.
Lösung anzeigen
Die Suche nach einer Position und das Einfügen an einer bereits bekannten Position sind verschiedene Arbeitsschritte. Der Listenweg benötigt Nachfolgerzugriffe; das anschließende Einfügen ändert Referenzen statt alle Daten zu verschieben.