Båda lagrar sekvenser, men de har motsatta kostnadsprofiler. En array är sammanhängande minne med O(1) indexering; en länkad lista är spridda noder sammanfogade med pekare, med O(1) insert/delete i ändar men utan indexering.
Båda lagrar sekvenser, men de har motsatta kostnadsprofiler. En array är sammanhängande minne med O(1) indexering; en länkad lista är spridda noder sammanfogade med pekare, med O(1) insert/delete i ändar men utan indexering.
| Operation | Array (dynamisk) | Länkad lista |
|---|
| Åtkomst per index | O(1) | O(n) |
| Sökning | O(n) | O(n) |
| Insert/delete i början | O(n) | O(1) |
| Insert/delete i slutet | O(1) amorterad | O(1) med slutpekare |
| Insert/delete i mitten | O(n) | O(n) sökning + O(1) sammankoppling |
| Minneskostnad | låg | hög (pekare per nod) |
| Cache-lokalitet | utmärkt | dålig |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
I praktiken vinner arrays de flesta gånger eftersom cache-lokalitet överskuggar Big-O skillnader för typiska storlekar.
Att kunna båda låter dig motivera ditt val i intervjuer istället för att blint välja standard — och förklara varför "O(1) insert" sällan slår en sammanhängande array.