Begge gemmer sekvenser, men de har modsatrettede omkostningsprofiler. Et array er sammenhængende hukommelse med O(1) indeksering; en linkeret liste er spredte noder forbundet af pegere, med O(1) indsættelse/sletning i enderne men uden indeksering.
Begge gemmer sekvenser, men de har modsatrettede omkostningsprofiler. Et array er sammenhængende hukommelse med O(1) indeksering; en linkeret liste er spredte noder forbundet af pegere, med O(1) indsættelse/sletning i enderne men uden indeksering.
| Operation | Array (dynamisk) | Linkeret liste |
|---|
| Adgang efter indeks | O(1) | O(n) |
| Søgning | O(n) | O(n) |
| Indsættelse/sletning i starten | O(n) | O(1) |
| Indsættelse/sletning i enden | O(1) amortiseret | O(1) med tail ptr |
| Indsættelse/sletning i midten | O(n) | O(n) søgning + O(1) splice |
| Hukommelsesomkostning | lav | høj (pointer pr. node) |
| Cache-lokalitet | fremragende | dårlig |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
I praksis vinder arrays det meste af tiden, fordi cache-lokalitet overgår Big-O-forskelle for typiske størrelser.
At kende begge dele lader dig retfærdiggøre dit valg i interviews i stedet for blindt at antage — og forklare hvorfor "O(1) indsættelse" sjældent slår et sammenhængende array.