O listă înlănțuită este o structură de date formată din noduri. Fiecare nod ține o valoare și o referință (legătură) către nodul următor. Nu ai nevoie de memorie continuă — nodurile pot fi oriunde, legate între ele.
Exemplu de nod în Python:
python.py
class Nod:
def __init__(self, valoare):
self.valoare = valoare
self.urmator = None # referinta la urmatorul nod
Tipuri:
- Listă simplu înlănțuită: fiecare nod pointează doar la următorul (parcuregi într-o singură direcție).
- Listă dublu înlănțuită: nodul are și
anterior(poți merge în ambele sensuri). - Listă circulară: ultimul nod pointează înapoi la primul.
Diferența esențială față de list: în listă înlănțuită, inserarea/ștergerea la capătul potrivit e O(1), dar accesul după index e O(n).