De ce contează?
Imagineaza-ti un tren: fiecare vagon stie doar care e vagonul din fata lui si
care e cel din spate. Ca sa adaugi un vagon nou la mijloc nu muti tot trenul —
desfaci doua carlige si prinzi vagonul nou intre ele. Dar daca te intreb „care e
al saptelea vagon?", nu ai cum sa-l arati instant: trebuie sa mergi de la
locomotiva si sa numeri vagon cu vagon. Exact asa functioneaza std::list.
Ce este
std::list este o listă dublu înlănțuită gata făcută din STL. Fiecare element
trăiește într-un nod separat, împrăștiat în memorie, iar nodurile sunt legate
între ele prin pointeri: fiecare știe cine e vecinul din stânga și cine e cel din
dreapta. Spre deosebire de vector, unde toate elementele stau lipite unul după
altul, aici „lipirea" e doar logică, prin legături.
Diferența asta schimbă complet ce e ieftin și ce e scump. La vector, accesul
a[i] e instant, dar o inserare la mijloc cere mutarea întregului sufix. La
list e fix invers: nu poți sări direct la poziția i, dar dacă ții deja un
iterator spre un element, inserezi sau ștergi acolo în O(1) — doar rescrii două
legături.
std::list nu are operator de indexare — nu există l[i]. Singurul mod de a
ajunge la al i-lea element e să pornești de la capăt și să urmărești legăturile,
adică O(n). În schimb, insert și erase cu un iterator deja poziționat sunt
O(1): reconectezi doar vecinul din stânga cu cel din dreapta, fără să muți nimic.