Modelul conceptual de listă

O listă este o colecție ordonată de valori: elementele au poziții și se pot repeta. În $[4,7,4]$, primul și ultimul element sunt egale, dar ocupă locuri diferite. Modelul de listă descrie ce operații dorim: acces la poziție, adăugare, ștergere și parcurgere. Implementarea concretă poate fi un tablou, o listă Python sau o structură înlănțuită, cu costuri diferite.

O listă este un model abstract: o colecție ordonată de elemente, în care ordinea contează și valorile se pot repeta. Modelul spune ce operații sunt disponibile: accesul la un element, adăugarea, inserarea pe o poziție, ștergerea și parcurgerea. Nu spune cum este memorată lista. Implementarea concretă poate fi un tablou, o listă Python (un tablou redimensionabil) sau o structură înlănțuită, cu costuri diferite pentru aceleași operații. Distincția dintre model și implementare se păstrează în toate lecțiile despre structuri de date.

Tipul de acces diferențiază structurile. Accesul direct găsește un element după poziție, într-un singur pas, indiferent de poziție: v[3] într-un tablou. Accesul secvențial pornește de la primul element și urmează pe rând legăturile până la elementul dorit, deci costă mai mult cu cât poziția este mai îndepărtată: așa se întâmplă într-o listă înlănțuită. Două cazuri particulare restrâng accesul: stiva permite operații numai la un capăt (LIFO, ultimul intrat este primul ieșit), iar coada adaugă la un capăt și scoate de la celălalt (FIFO, primul intrat este primul ieșit).

Exemplul 1 — operațiile de bază pe o listă Python.

valori = [4, 7, 4]
valori.append(9)
print(valori[1], len(valori))

După adăugare lista este [4, 7, 4, 9]; poziția 1 conține 7, iar lungimea este 4. Se afișează 7 4. Elementele 4 de pe pozițiile 0 și 2 sunt egale, dar ocupă locuri diferite, deci ambele se păstrează: o listă admite repetiții. Adăugarea la capăt este operația obișnuită, iar valori.insert(0, 1) produce [1, 4, 7, 4, 9] și mută spre dreapta toate cele patru elemente existente.

Exemplul 2 — costul accesului. Într-un tablou cu elementele $4,7,9$, expresia v[1] dă 7 imediat, fără parcurgere. Într-o listă înlănțuită cu aceleași elemente trebuie pornit de la primul nod și urmată legătura către al doilea; pentru al $k$-lea element se fac $k-1$ salturi. În schimb, inserarea unui element după un nod cunoscut costă într-o listă înlănțuită un număr constant de operații, pe când într-un tablou cere mutarea elementelor de după poziția respectivă. Alegerea implementării depinde deci de operația cea mai frecventă.

Exemplul 3 — stiva și coada ca liste restrânse. Dacă elementele $A$, $B$, $C$ sunt adăugate în această ordine, într-o stivă prima valoare scoasă este $C$, iar într-o coadă este $A$. Aceeași colecție de trei valori are deci două ordini de scoatere, în funcție de modelul ales. Pentru problemele de forma „ultima alegere se anulează prima” (parantezele, apelurile de funcții) se potrivește stiva; pentru cele de forma „se servește în ordinea sosirii” (parcurgerea în lățime) se potrivește coada.

Exemplul 4 — ștergerea. Ștergerea după poziție se face cu del valori[1], iar ștergerea după valoare cu valori.remove(4). Din lista [4, 7, 4, 9], instrucțiunea del valori[1] elimină 7 și mută spre stânga elementele de după el, deci rămâne [4, 4, 9]. Din lista [4, 7, 4], instrucțiunea valori.remove(4) elimină numai prima apariție a valorii 4 și lasă [7, 4]. Modelul de listă cere deci să precizezi ce ștergi: o poziție sau o valoare, iar cu valori repetate cele două operații nu dau același rezultat.

Greșeli frecvente

• Greșit: într-o listă, o valoare repetată se păstrează o singură dată.
  Corect: lista păstrează fiecare apariție, pe pozițiile ei.
• Greșit: lista și tabloul sunt același lucru.
  Corect: lista este un model abstract; tabloul este una dintre implementările posibile.
• Greșit: accesul la al treilea element costă la fel în orice implementare.
  Corect: într-un tablou este direct, într-o listă înlănțuită cere parcurgere.

Înainte și după