Begge lagrer sekvenser, men de har motsatte kostnadsprofiler. En array er sammenhengende minne med O(1)-indeksering; en lenket liste er spredte noder forbundet av pekere, med O(1) innsetting/sletting ved endene men uten indeksering.
Begge lagrer sekvenser, men de har motsatte kostnadsprofiler. En array er sammenhengende minne med O(1)-indeksering; en lenket liste er spredte noder forbundet av pekere, med O(1) innsetting/sletting ved endene men uten indeksering.
| Operasjon | Array (dynamisk) | Lenket liste |
|---|
| Tilgang etter indeks | O(1) | O(n) |
| Søk | O(n) | O(n) |
| Innsetting/sletting ved begynnelsen | O(n) | O(1) |
| Innsetting/sletting ved slutten | O(1) amortisert | O(1) med tail ptr |
| Innsetting/sletting i midten | O(n) | O(n) søk + O(1) splice |
| Minneoverhead | lav | høy (peker per node) |
| Cache-lokalitet | utmerket | dårlig |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
I praksis vinner arrays mesteparten av tiden fordi cache-lokalitet oppveier Big-O-forskjeller for typiske størrelser.
Å kjenne begge lar deg rettferdiggjøre valget ditt i intervjuer i stedet for å velge blindt — og forklare hvorfor "O(1) innsetting" sjelden slår en sammenhengende array.