Node-Klasse und Listenerstellung
Definieren Sie eine Node-Dataclass, erstellen Sie Listen durch manuelles Verknüpfen von Nodes und schreiben Sie insert/delete/print-Hilfsfunktionen, um Zeigeränderungen zu visualisieren.
Node-Klasse und Listenerstellung ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was ist eine verkettete Liste?
Eine verkettete Liste ist eine Folge von Knoten, wobei jeder Knoten einen Wert und einen Zeiger auf den nächsten Knoten speichert. Anders als bei Arrays liegen die Knoten verstreut im Speicher – es gibt keinen indexbasierten Zugriff in O(1). Dafür können Sie an jeder bekannten Position in O(1) Elemente einfügen und löschen, ohne andere Elemente verschieben zu müssen.
In Python stellen wir jeden Knoten mit einer kleinen Klasse dar, die val und next enthält. Durch das Verketten der Knoten entsteht die Liste; next des letzten Knotens ist None und signalisiert das Ende.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build: 1 -> 2 -> 3 -> None
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
# Traverse and print
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None')Listen aus Arrays erstellen
In Vorstellungsgesprächen erhalten Sie häufig eine Liste und sollen daraus die entsprechende verkettete Liste erstellen – oder umgekehrt. Die Hilfsfunktionen build und to_list sollten Sie sich merken: build verkettet Knoten aus einem Array, und to_list durchläuft die Liste und sammelt die Werte zur einfachen Überprüfung.
Das Erstellen einer verketteten Liste aus n Elementen benötigt O(n) Zeit und O(n) Speicher. Ein Dummy-Head-Knoten vereinfacht Randfälle, in denen sich der erste Knoten ändern kann.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
head = build([1, 2, 3, 4, 5])
print(to_list(head)) # [1, 2, 3, 4, 5]Am Head und Tail einfügen
Das Einfügen eines neuen Knotens am Head dauert O(1): Erstellen Sie den Knoten, zeigen Sie mit seinem next auf den bisherigen Head und geben Sie den neuen Knoten als Head zurück. Das Einfügen am Tail erfordert einen Durchlauf bis zum letzten Knoten (O(n)); anschließend wird der neue Knoten verknüpft.
Ein Dummy-Head beseitigt bei beiden Einfügeoperationen den Sonderfall einer leeren Liste, da dummy.next immer auf den tatsächlichen Head zeigt.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_head(head, val):
return ListNode(val, head) # O(1)
def insert_tail(head, val):
new_node = ListNode(val)
if not head:
return new_node
curr = head
while curr.next:
curr = curr.next
curr.next = new_node
return head
head = None
for v in [1, 2, 3]:
head = insert_tail(head, v)
head = insert_head(head, 0)
curr = head
while curr:
print(curr.val, end=' -> ')
curr = curr.next
print('None') # 0 -> 1 -> 2 -> 3 -> NoneEinen Knoten nach Wert löschen
Um den ersten Knoten mit einem bestimmten Wert zu löschen, verwalten Sie einen prev-Zeiger, der eine Position hinter curr liegt. Sobald curr.val == target gilt, setzen Sie prev.next = curr.next, um den Knoten zu überspringen. Ein Dummy-Head ist hier besonders hilfreich, da er den Sonderfall des Löschens des tatsächlichen Heads beseitigt – prev kann immer beim Dummy beginnen.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_val(head, target):
dummy = ListNode(0)
dummy.next = head
prev, curr = dummy, head
while curr:
if curr.val == target:
prev.next = curr.next
break
prev, curr = curr, curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
head = None
for v in [1, 2, 3, 2, 4]:
dummy2 = ListNode(v)
dummy2.next = head
head = dummy2 # build in reverse for speed
head = delete_val(head, 2)
print(to_list(head))Zeigeränderungen visualisieren
Ein häufiger Fehler besteht darin, beim Aktualisieren von Zeigern den Überblick über einen Knoten zu verlieren. Speichern Sie next immer, bevor Sie ihn überschreiben: saved = curr.next, und weisen Sie ihn anschließend neu zu. Zeichnen Sie die Liste als durch Pfeile verbundene Kästchen und simulieren Sie jede Zeigeränderung auf Papier, bevor Sie programmieren. Diese visuelle Methode verhindert versehentliche Nullzeigerfehler in Vorstellungsgesprächen.
Denken Sie daran: In Python wirkt sich das erneute Zuweisen von curr.next nicht auf curr selbst aus. Wenn Sie jedoch die Referenz auf curr.next nicht speichern, bevor Sie sie überschreiben, können Sie nicht mehr vorwärts durch die Liste laufen.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Demonstrate safe pointer update
def swap_first_two(head):
if not head or not head.next:
return head
first = head
second = head.next
# Save third before losing the reference
third = second.next
# Rewire
second.next = first
first.next = third
return second
from functools import reduce
nodes = [ListNode(i) for i in range(1, 5)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = swap_first_two(nodes[0])
curr = head
while curr:
print(curr.val, end=' ')
curr = curr.next
# 2 1 3 4Einfach oder doppelt verkettete Listen
Eine einfach verkettete Liste speichert nur einen next-Zeiger; der Durchlauf erfolgt in eine Richtung. Eine doppelt verkettete Liste speichert sowohl prev als auch next und ermöglicht dadurch einen Rückwärtsdurchlauf in O(1) sowie das Löschen in O(1), wenn eine direkte Referenz auf den Knoten vorliegt (die Schleife zur Verwaltung von prev ist nicht erforderlich).
Python's collections.deque ist als doppelt verkettete Liste implementiert, weshalb es O(1)-Operationen mit appendleft und popleft unterstützt. In Vorstellungsgesprächen implementieren Sie einfach verkettete Listen; doppelt verkettete Listen kommen beim Entwurf eines LRU-Caches vor.
class DLNode:
def __init__(self, val=0):
self.val = val
self.prev = None
self.next = None
# Build doubly linked: 1 <-> 2 <-> 3
a, b, c = DLNode(1), DLNode(2), DLNode(3)
a.next = b; b.prev = a
b.next = c; c.prev = b
# Traverse forward
curr = a
while curr:
print(curr.val, end=' <-> ')
curr = curr.next
print('None')
# Traverse backward from c
curr = c
while curr:
print(curr.val, end=' <-> ')
curr = curr.prev
print('None')Hilfsfunktionen für Länge, Tail und Ausgabe
Drei Hilfsfunktionen sollten Sie für jedes Vorstellungsgespräch zu verketteten Listen bereithalten: length(head) zählt Knoten in O(n), tail(head) gibt den letzten Knoten in O(n) zurück, und print_list(head) formatiert die Liste zur Fehlersuche. Wenn diese Funktionen bereitstehen, können Sie sich auf den eigentlichen Algorithmus konzentrieren, anstatt die Hilfslogik erneut zu implementieren.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def length(head):
count = 0
while head:
count += 1
head = head.next
return count
def tail(head):
while head and head.next:
head = head.next
return head
def print_list(head):
parts = []
while head:
parts.append(str(head.val))
head = head.next
print(' -> '.join(parts) + ' -> None')
# Build and test
nodes = [ListNode(i) for i in [10, 20, 30, 40]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = nodes[0]
print('Length:', length(head))
print('Tail:', tail(head).val)
print_list(head)Zwei-Zeiger-Aufbau bei verketteten Listen
Die Zwei-Zeiger-Technik ist für verkettete Listen ebenso wichtig wie für Arrays, allerdings sind die Zeiger hier Knoten der verketteten Liste und keine Indizes. Typische Aufbauten sind ein langsamer und schneller Zeiger (der schnelle bewegt sich doppelt so schnell) zum Finden von Mittelpunkten und Erkennen von Zyklen sowie ein Paar aus Vorgänger und aktuellem Knoten zum Löschen und Umkehren.
Initialisieren Sie beide Zeiger immer explizit und behandeln Sie die Prüfung auf das Listenende sorgfältig – fast and fast.next verhindert Nullzeigerfehler, wenn sich fast nahe am Ende befindet.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Find middle node using slow-fast pointers
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length, returns second of two middle nodes
nodes = [ListNode(i) for i in range(1, 6)]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
print(find_middle(nodes[0]).val) # 3 (middle of 1->2->3->4->5)Das Dummy-Head-Muster
Das Muster mit einem Dummy-Head (Sentinel-Knoten) ist einer der nützlichsten Kniffe bei Problemen mit verketteten Listen. Indem Sie einen Dummy-Knoten mit dem Wert 0 voranstellen, müssen Sie weder eine leere Liste noch eine Änderung am tatsächlichen Head als Sonderfall behandeln. Ihr Ergebnis ist immer dummy.next. Dieses Muster kommt beim Zusammenführen sortierter Listen, beim Entfernen des n-ten Elements vom Ende, beim Partitionieren einer Liste und in vielen weiteren Aufgaben vor.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Remove all nodes with val == target (may include head)
def remove_all(head, target):
dummy = ListNode(0)
dummy.next = head
curr = dummy
while curr.next:
if curr.next.val == target:
curr.next = curr.next.next # skip the node
else:
curr = curr.next
return dummy.next
def to_list(h):
r = []
while h:
r.append(h.val)
h = h.next
return r
nodes = [ListNode(v) for v in [1, 2, 6, 3, 4, 5, 6]]
for i in range(len(nodes) - 1):
nodes[i].next = nodes[i+1]
head = remove_all(nodes[0], 6)
print(to_list(head)) # [1, 2, 3, 4, 5]Zeit- und Speicherkomplexität
Die meisten Operationen auf verketteten Listen haben folgende Komplexitäten. Zugriff per Index: O(n) – der Durchlauf muss am Head beginnen. Einfügen/Löschen an einem bekannten Knoten: O(1) – Sie müssen lediglich die Zeiger neu verknüpfen. Einfügen/Löschen an Position k: O(k) – zunächst ist ein Durchlauf erforderlich. Suche: O(n) – im schlechtesten Fall wird die gesamte Liste durchlaufen. Der Speicherbedarf beträgt O(1) für alle Operationen direkt in der Liste (ohne zusätzliche Datenstrukturen).
Im Gegensatz dazu bieten Arrays einen Zugriff in O(1), aber das Einfügen und Löschen dauert wegen des Verschiebens O(n). Verkettete Listen sind besser geeignet, wenn häufig an beliebigen Positionen eingefügt und gelöscht wird.
Tipps für Vorstellungsgespräche zu verketteten Listen
Bevor Sie Code für eine verkettete Liste schreiben, zeichnen Sie die Liste mit Kästchen und Pfeilen. Sprechen Sie die Randfälle laut durch: leere Liste, einzelner Knoten, gerade oder ungerade Länge. Verwenden Sie einen Dummy-Head, um Randbedingungen zu vereinfachen. Prüfen Sie frühzeitig immer if not head. Verfolgen Sie Ihre Lösung nach dem Programmieren an einer Liste mit drei Knoten, damit Sie Zeigerfehler entdecken, bevor der Interviewer sie findet.
Die meisten Fehler bei verketteten Listen haben eine von drei Ursachen: Sie vergessen, next vor dem Überschreiben zu speichern, verwenden eine falsche Abbruchbedingung oder behandeln den Randfall einer Head-Änderung nicht – der Dummy-Knoten beseitigt den dritten Fall vollständig.
Kurzer Check
Testen Sie Ihr Verständnis der Konzepte von Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Eine verkettete Liste wird aus Node-Objekten mit den Feldern val und next aufgebaut, das Dummy-Head-Muster beseitigt Randfälle bei Änderungen am Head, und der Aufbau mit einem langsamen und einem schnellen Zeiger bildet die Grundlage für das Finden des Mittelpunkts und die Zykluserkennung. Als Nächstes kehren wir eine verkettete Liste um – eines der am häufigsten gestellten Zeigerprobleme.
Häufig gestellte Fragen
Ist die Lektion „Node-Klasse und Listenerstellung“ kostenlos?
Ja — der vollständige Text von „Node-Klasse und Listenerstellung“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Node-Klasse und Listenerstellung“?
Definieren Sie eine Node-Dataclass, erstellen Sie Listen durch manuelles Verknüpfen von Nodes und schreiben Sie insert/delete/print-Hilfsfunktionen, um Zeigeränderungen zu visualisieren. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Node-Klasse und Listenerstellung“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Node-Klasse und Listenerstellung
- Eine verkettete Liste umkehren
- Zykluserkennung mit Floyds Algorithmus
- Zusammenführen, Teilen und das n-te Element vom Ende finden