Molemmat varastoivat sekvenssejä, mutta niillä on vastakkaiset kustannusprofiilit. Taulukko on jatkuva muisti O(1) indeksoinniksi; linkitetty lista on hajallaan olevia solmuja yhdistettynä osoittimilla, joissa on O(1) lisäys/poisto päissä mutta ilman indeksointia.
| Operaatio | Taulukko (dynaaminen) | Linkitetty lista |
|---|
| Pääsy indeksillä | O(1) | O(n) |
| Haku | O(n) | O(n) |
| Lisäys/poisto alussa | O(n) | O(1) |
| Lisäys/poisto lopussa | O(1) amortisoimatta | O(1) tail ptr:n kanssa |
| Lisäys/poisto keskellä | O(n) | O(n) haku + O(1) splice |
| Muistin kuormitus | alhainen | korkea (osoitin per solmu) |
| Välimuistin paikallisuus | erinomainen | huono |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
Käytännössä taulukot voittavat useimmiten, koska välimuistin paikallisuus ylittää Big-O erot tyypillisille kooille.
Molempien tunteminen antaa sinulle mahdollisuuden perustella valintasi haastatteluissa sokean olettamisen sijaan — ja selittää miksi "O(1) lisäys" harvoin voittaa jatkuvan taulukon.