Beide slaan reeksen op, maar ze hebben tegengestelde kostprofielen. Een array is aaneensluitend geheugen met O(1)-indexering; een linked list bestaat uit verspreide nodes verbonden door pointers, met O(1) invoegen/verwijderen aan de uiteinden maar zonder indexering.
| Bewerking | Array (dynamisch) | Linked list |
|---|
| Toegang via index | O(1) | O(n) |
| Zoeken | O(n) | O(n) |
| Invoegen/verwijderen aan het begin | O(n) | O(1) |
| Invoegen/verwijderen aan het eind | O(1) amortized | O(1) met tail ptr |
| Invoegen/verwijderen in het midden | O(n) | O(n) zoeken + O(1) splice |
| Geheugenoverhead | laag | hoog (pointer per node) |
| Cache-localiteit | uitstekend | slecht |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
In de praktijk winnen arrays meestal omdat cache-localiteit Big-O verschillen voor typische grootten overschaduwt.
Beiden kennen stelt je in staat om je keuze in interviews te rechtvaardigen in plaats van blind de standaard te kiezen — en uit te leggen waarom "O(1) invoegen" zelden een aaneensluitende array verslaat.