...
Eroare Algoritmi și structuri de date · Stive, cozi și liste înlănțuite

Ștergerea din lista înlănțuită nu șterge primul nod (capul listei)

Pe scurt

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

Greșit
PYTHON
curent = cap
while curent.urm:
    if curent.urm.val == val:
        curent.urm = curent.urm.urm
    else:
        curent = curent.urm
return cap
Corect
PYTHON
santinela = Nod(0, cap)
curent = santinela
while curent.urm:
    if curent.urm.val == val:
        curent.urm = curent.urm.urm
    else:
        curent = curent.urm
return santinela.urm

Santinela face din cap un nod obișnuit, cu un anterior. Noul cap e ce urmează după santinelă.

2Rezultatul funcției nu e folosit

Greșit
PYTHON
sterge(cap, 7)
afiseaza(cap)
Corect
PYTHON
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ă

Greșit
PYTHON
if cap.val == val:
    cap = cap.urm
Corect
PYTHON
while cap and cap.val == val:
    cap = cap.urm

Dacă primele două noduri au valoarea, un singur if îl lasă pe al doilea. Fără santinelă, ai nevoie de while.

Repară tu

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].

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
[1, 2]
Indiciu

Pune un nod santinelă înaintea capului, parcurge de la el și returnează santinela.urm.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.