Informatică Programare
Diferenta intre array si lista inlantuita
Diferența dintre un array și o listă înlănțuită este că array-ul stochează elemente într-o zonă continuă de memorie cu acces rapid, în timp ce lista înlănțuită leagă elemente prin pointeri, oferind flexibilitate la inserări și ștergeri. Array-ul are dimensiune fixă, lista poate crește dinamic.
Array (vector)
- Acces la elemente Acces direct prin index în timp constant O(1). Exemplu: int arr[5] = {1,2,3,4,5}; cout << arr[2]; afișează 3.
- Dimensiune Dimensiune fixă, stabilită la declarare. Nu poate fi redimensionat ușor.
- Memorie Elementele sunt stocate contiguu, ceea ce permite caching eficient.
Listă înlănțuită
- Structură Fiecare nod conține date și un pointer către următorul nod. Exemplu în C++: struct Nod { int val; Nod* next; };
- Inserare/Ștergere Operații rapide O(1) la început sau sfârșit, dar lente O(n) pentru căutare.
- Memorie Elementele sunt dispersate în memorie, legate prin pointeri, ceea ce consumă memorie suplimentară.
Comparație practică
- Viteză Array-ul e mai rapid la acces, lista la modificări frecvente.
- Utilizare Folosește array pentru date statice (ex: notele unei clase), listă pentru cozi sau stive dinamice.
- Exemplu numeric Pentru 1000 de elemente, accesul la mijloc: array face 1 operație, lista poate face până la 1000.
Alege array când știi dimensiunea și ai nevoie de acces rapid, listă când inseri și ștergi des.