Ștergerea din lista înlănțuită nu șterge primul nod (capul listei)
Bucla verifică mereu curent.urm, deci nu ajunge niciodată să compare capul listei. Pune un nod fals (santinelă) înaintea capului: santinela = Nod(0, cap), parcurge de la ea și returnează santinela.urm.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Ca să ștergi un nod dintr-o listă simplu înlănțuită, ai nevoie de nodul dinaintea lui: anterior.urm = anterior.urm.urm. De aceea bucla tipică pornește de la cap și verifică curent.urm.val. Capul nu are însă un nod înaintea lui, deci nu e verificat niciodată.
Rezultatul: dacă primul nod (sau primele câteva) are valoarea de șters, rămâne în listă. Python nu dă nicio eroare. O a doua greșeală frecventă e să ștergi capul corect, dar să returnezi tot variabila veche cap, care încă indică spre nodul șters.
Soluția standard e un nod santinelă (dummy): un nod fals pus înaintea capului. Acum capul are un „anterior” ca orice alt nod, codul nu mai are cazuri speciale, iar noul cap e santinela.urm.
De ce apare: cauzele frecvente
1Bucla nu verifică și capul
curent = cap
while curent.urm:
if curent.urm.val == val:
curent.urm = curent.urm.urm
else:
curent = curent.urm
return capsantinela = Nod(0, cap)
curent = santinela
while curent.urm:
if curent.urm.val == val:
curent.urm = curent.urm.urm
else:
curent = curent.urm
return santinela.urmSantinela face din cap un nod obișnuit, cu un anterior. Noul cap e ce urmează după santinelă.
2Rezultatul funcției nu e folosit
sterge(cap, 7)
afiseaza(cap)cap = sterge(cap, 7)
afiseaza(cap)Dacă primul nod a fost șters, capul s-a schimbat. Variabila veche indică încă spre nodul eliminat.
3Caz special scris doar o dată
if cap.val == val:
cap = cap.urmwhile cap and cap.val == val:
cap = cap.urmDacă primele două noduri au valoarea, un singur if îl lasă pe al doilea. Fără santinelă, ai nevoie de while.
Repară eroarea, direct în pagină
Funcția sterge(cap, cod) elimină toate comenzile cu un anumit cod dintr-o listă înlănțuită. Testul cu assert pică: comanda 7 de la începutul listei rămâne. Repar-o ca să afișeze [1, 2].
class Nod:
def __init__(self, val, urm=None):
self.val = val
self.urm = urm
def sterge(cap, cod):
curent = cap
while curent.urm:
if curent.urm.val == cod:
curent.urm = curent.urm.urm
else:
curent = curent.urm
return cap
def in_lista(cap):
rez = []
while cap:
rez.append(cap.val)
cap = cap.urm
return rez
cap = Nod(7, Nod(1, Nod(7, Nod(2))))
rez = in_lista(sterge(cap, 7))
assert rez == [1, 2], f'comenzi gresite: {rez}'
print(rez)[1, 2]
Indiciu
Pune un nod santinelă înaintea capului, parcurge de la el și returnează santinela.urm.
Reparația
class Nod:
def __init__(self, val, urm=None):
self.val = val
self.urm = urm
def sterge(cap, cod):
santinela = Nod(0, cap)
curent = santinela
while curent.urm:
if curent.urm.val == cod:
curent.urm = curent.urm.urm
else:
curent = curent.urm
return santinela.urm
def in_lista(cap):
rez = []
while cap:
rez.append(cap.val)
cap = cap.urm
return rez
cap = Nod(7, Nod(1, Nod(7, Nod(2))))
rez = in_lista(sterge(cap, 7))
assert rez == [1, 2], f'comenzi gresite: {rez}'
print(rez)De ce merge
Bucla compara doar curent.urm.val, adică nodul de după cel curent, deci primul nod nu era verificat niciodată și rezultatul era [7, 1, 2]. Santinela pusă înaintea capului face ca și primul nod să aibă un anterior, deci e șters exact ca celelalte. Funcția returnează santinela.urm, care e noul cap: nodul 1.
Alte forme ale mesajului
AttributeError: 'NoneType' object has no attribute 'urm'
Cum o eviți pe viitor
Folosește un nod santinelă în orice operație care poate schimba capul listei: ștergere, inserare la început, inversare, interclasare. Returnează mereu noul cap și atribuie-l la apel (cap = f(cap)). Testează cu valoarea de șters pe prima poziție, pe primele două poziții și cu o listă formată doar din ea.
Întrebări frecvente
Santinela nu consumă memorie în plus?
Un singur nod, indiferent de lungimea listei. În schimb elimini toate cazurile speciale pentru cap.
Ce se întâmplă dacă se șterge tot?
Cu santinelă, santinela.urm devine None, adică lista goală, fără niciun cod în plus.
Erori înrudite
AttributeError: 'NoneType' object has no attribute 'urm' Ai ajuns la capătul listei înlănțuite (nodul curent e None) și ai cerut încă .urm sau .val. Verifică nodul înainte de acces: while curent and curent.urm:, iar la doi pași (rapid.urm.urm) verifică ambii pași. Inversarea listei înlănțuite pierde noduri (curent.urm suprascris înainte de avans) Ai schimbat curent.urm = anterior înainte să salvezi următorul nod, iar apoi curent = curent.urm te duce înapoi, nu înainte. Salvează întâi urmator = curent.urm, abia apoi întoarce legătura și avansează cu curent = urmator. Parcurgerea listei înlănțuite nu se mai oprește (lipsește curent = curent.urm) În bucla while curent: ai uitat să avansezi cu curent = curent.urm (sau avansezi doar pe o ramură a unui if), așa că nodul curent nu se schimbă și bucla rulează la nesfârșit; editorul o oprește după limita de timp. Avansează pe fiecare drum prin buclă. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
