Ambele stochează secvențe, dar au profiluri de cost opuse. Un array este memoria contiguă cu indexare O(1); o listă legată este noduri dispersate unite prin pointeri, cu O(1) inserare/ștergere la capete, dar fără indexare.
Ambele stochează secvențe, dar au profiluri de cost opuse. Un array este memoria contiguă cu indexare O(1); o listă legată este noduri dispersate unite prin pointeri, cu O(1) inserare/ștergere la capete, dar fără indexare.
| Operație | Array (dinamic) | Listă legată |
|---|
| Acces prin index | O(1) | O(n) |
| Căutare | O(n) | O(n) |
| Inserare/ștergere la început | O(n) | O(1) |
| Inserare/ștergere la final | O(1) amortizat | O(1) cu tail ptr |
| Inserare/ștergere în mijloc | O(n) | O(n) căutare + O(1) splice |
| Overhead de memorie | mic | mare (pointer per nod) |
| Localitate de cache | excelentă | slabă |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
În practică, arrays câștigă de cele mai multe ori pentru că localitatea cache depășește diferențele Big-O pentru dimensiuni tipice.
Cunoscând ambele îți permite să-ți justifici alegerea la interviuri în loc să alegi orbește — și să explici de ce "inserare O(1)" rar învinge un array contiguu.