Abu saugo sekų, bet jie turi priešingus kaštų profilius. Masyvas yra tolydi atmintis su O(1) indeksavimu; susietasis sąrašas yra išsklaidyti mazgai, sujungti rodyklėmis, su O(1) įterpimo/šalinimo galuose, bet be indeksavimo.
Abu saugo sekų, bet jie turi priešingus kaštų profilius. Masyvas yra tolydi atmintis su O(1) indeksavimu; susietasis sąrašas yra išsklaidyti mazgai, sujungti rodyklėmis, su O(1) įterpimo/šalinimo galuose, bet be indeksavimo.
| Operacija | Masyvas (dinaminis) | Susietasis sąrašas |
|---|
| Prieiga pagal indeksą | O(1) | O(n) |
| Paieška | O(n) | O(n) |
| Įterpimas/šalinimas pradžioje | O(n) | O(1) |
| Įterpimas/šalinimas pabaigoje | O(1) amortizuota | O(1) su tail rodykle |
| Įterpimas/šalinimas viduryje | O(n) | O(n) paieška + O(1) jungimas |
| Atminties pridėjimas | mažas | aukštas (rodyklė per mazgą) |
| Cache vietos tingumiškumas | puikus | prastas |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
Praktikoje masyvai pergali daugumoje atvejų, nes cache vietos tingumiškumas pranoksta Big-O skirtumus tipiniais dydžiais.
Žinant abu leidžia jums pagrįsti savo pasirinkimą pokalbiuose, o ne aklo pasirinkimo – ir paaiškinti kodėl "O(1) įterpimas" retai pergali tęstinį masyvą.