Node-klassen og listekonstruktion
Definer en Node-dataclass, opbyg lister ved manuelt at forbinde noder, og skriv hjælpefunktioner til insert/delete/print for at visualisere pointerændringer.
Node-klassen og listekonstruktion er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad er en lænket liste
En lænket liste er en sekvens af knuder, hvor hver knude gemmer en værdi og en peger til den næste knude. I modsætning til tabeller ligger knuderne spredt i hukommelsen — der er ingen O(1)-adgang via indeks. Til gengæld får du O(1)-indsættelse og -sletning på enhver kendt position uden at flytte elementer.
I Python repræsenterer vi hver knude med en lille klasse, der indeholder val og next. Når knuderne kædes sammen, dannes listen; den sidste knudes next er None for at markere slutningen.
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')Opret lister ud fra tabeller
I tekniske jobsamtaler får du ofte en liste og bliver bedt om at konstruere den tilsvarende lænkede liste eller omvendt. Hjælpefunktionerne build og to_list er værd at lære udenad: build kæder knuder sammen fra en tabel, og to_list gennemløber listen for at samle værdier til nem kontrol.
Det tager O(n)-tid og O(n)-plads at oprette en lænket liste fra n elementer. Brug af en knude som kunstigt hoved forenkler randtilfælde, hvor den første knude kan ændre sig.
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]Indsæt ved hoved og hale
Det tager O(1) at indsætte en ny knude ved hovedet: Opret knuden, lad dens next pege på det gamle hoved, og returnér den nye knude som hovedet. Hvis du vil indsætte ved halen, skal du gennemløbe listen til den sidste knude (O(n)) og derefter forbinde den nye knude.
En knude som kunstigt hoved fjerner specialtilfældet med en tom liste ved begge indsættelser, fordi dummy.next altid er det egentlige hoved.
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 -> NoneSlet en knude efter værdi
Hvis du vil slette den første knude med en given værdi, skal du holde en prev-peger ét trin bag curr. Når curr.val == target, skal du sætte prev.next = curr.next for at springe knuden over. En knude som kunstigt hoved er især nyttig her, fordi den fjerner specialtilfældet med at slette selve hovedknuden — prev kan altid starte ved det kunstige hoved.
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))Visualisér ændringer af pegere
En almindelig fejl er at miste overblikket over en knude, når du opdaterer pegere. Gem altid next, før du overskriver den: saved = curr.next, og tildel derefter på ny. Tegn listen som kasser forbundet med pile, og simulér hver opdatering af en peger på papir, før du skriver kode. Denne visuelle metode forhindrer utilsigtede null-pegerfejl under tekniske jobsamtaler.
Husk: I Python påvirker en ny tildeling af curr.next ikke selve curr, men hvis du mister referencen til curr.next, før du gemmer den, kan du ikke længere gennemløbe listen fremad.
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 4Enkelt- kontra dobbeltlænede lister
En enkeltlænket liste gemmer kun en next-peger; gennemløb sker i én retning. En dobbeltlænket liste gemmer både prev og next, hvilket muliggør O(1)-gennemløb bagud og O(1)-sletning, når du har en direkte reference til knuden (du behøver ikke løkken, der holder styr på prev).
Python's collections.deque er implementeret som en dobbeltlænket liste, og derfor understøtter den O(1) appendleft og popleft. Til tekniske jobsamtaler skal du implementere enkeltl?nkede lister; dobbeltl?nkede lister bruges i udformningen af LRU-caches.
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')Hjælpefunktioner til længde, hale og udskrift
Tre hjælpefunktioner, du bør have klar til enhver jobsamtale om lænkede lister: length(head) tæller knuder på O(n), tail(head) returnerer den sidste knude på O(n), og print_list(head) formatterer listen til fejlfinding. Når du har disse klar, kan du fokusere på kernealgoritmen i stedet for at implementere hjælpelogik igen.
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)Opsætning med to pegere på lænkede lister
Teknikken med to pegere er lige så vigtig for lænkede lister som for tabeller, men pegerne er knuder i den lænkede liste i stedet for indekser. Almindelige opsætninger omfatter en langsom og hurtig peger (den hurtige bevæger sig 2 gange så hurtigt) til at finde midtpunkter og opdage cyklusser samt et par bestående af en forgænger og en aktuel knude til sletning og vending.
Initialisér altid begge pegere eksplicit, og håndtér kontrollen af nulafslutningen omhyggeligt — fast and fast.next forhindrer null-pegerfejl, når fast er tæt på slutningen.
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)Mønstret med et kunstigt hoved
Mønstret med et kunstigt hoved (en vagtpostknude) er et af de mest nyttige tricks i problemer med lænkede lister. Ved at sætte en kunstig knude med værdien 0 foran behøver du aldrig et specialtilfælde for en tom liste eller en ændring af det egentlige hoved. Dit resultat er altid dummy.next. Dette mønster bruges blandt andet til at flette sorterede lister, fjerne den n-te knude fra slutningen og partitionere en liste.
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]Tids- og pladskompleksitet
De fleste operationer på lænkede lister har følgende kompleksiteter. Adgang via indeks: O(n) — du skal gennemløbe listen fra hovedet. Indsættelse/sletning ved en kendt knude: O(1) — du skal blot omforbinde pegerne. Indsættelse/sletning ved position k: O(k) — gennemløb først listen. Søgning: O(n) — i værste fald hele listen. Pladsforbruget er O(1) for alle operationer på stedet (ekstra datastrukturer er ikke medregnet).
Sammenlign det med tabeller: Tabeller giver O(1)-adgang, men O(n)-indsættelse og -sletning på grund af flytning. Lænkede lister er bedre, når indsættelser og sletninger på vilkårlige positioner forekommer ofte.
Tips til tekniske jobsamtaler om lænkede lister
Før du skriver kode til en lænket liste, skal du tegne listen visuelt med kasser og pile. Gennemgå randtilfælde højt: tom liste, én knude, lige kontra ulige længde. Brug et kunstigt hoved til at forenkle randbetingelserne. Kontrollér altid if not head tidligt. Når du har skrevet koden, skal du gennemgå din løsning på en liste med tre knuder, så du opdager pegerfejl, før intervieweren gør det.
De fleste fejl i lænkede lister kommer fra én af tre kilder: at glemme at gemme next, før du overskriver den, en forskydning på én i afslutningsbetingelsen eller manglende håndtering af randtilfældet, hvor hovedet ændres — den kunstige knude fjerner det tredje problem helt.
Hurtig kontrol
Kontrollér din forståelse af begreberne fra denne lektion i Data Structures & Algorithms — Coding Interview Prep.
Opsummering af lektionen
I denne lektion lærte du, at: en lænket liste bygges af Node-objekter med felterne val og next, mønstret med et kunstigt hoved fjerner randtilfælde, hvor hovedet ændres, og opsætningen med en langsom og en hurtig peger er grundlaget for at finde midtpunkter og opdage cyklusser. Nu går vi videre til at vende en lænket liste — et af de oftest stillede pegerproblemer.
Lær Python med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Node-klassen og listekonstruktion” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Node-klassen og listekonstruktion”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Node-klassen og listekonstruktion”?
Definer en Node-dataclass, opbyg lister ved manuelt at forbinde noder, og skriv hjælpefunktioner til insert/delete/print for at visualisere pointerændringer. Du øver dig i DSA Interview Prep med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.
Hvor lang tid tager lektionen “Node-klassen og listekonstruktion”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Node-klassen og listekonstruktion
- Vending af en linked list
- Cyklusdetektion med Floyds algoritme
- Fletning, opdeling og find den n-te fra enden