Të dyja ruajnë sekuenca, por kanë profile të kundërta të kostove. Një varg është memorie e vazhdueshme me indeksim O(1); një listë e lidhur është nodi i shpërndarë të bashkuar me tregues, me O(1) futje/fshirje në skajet por pa indeksim.
Të dyja ruajnë sekuenca, por kanë profile të kundërta të kostove. Një varg është memorie e vazhdueshme me indeksim O(1); një listë e lidhur është nodi i shpërndarë të bashkuar me tregues, me O(1) futje/fshirje në skajet por pa indeksim.
| Operacioni | Vargu (dinamik) | Lista e lidhur |
|---|
| Qasja sipas indeksit | O(1) | O(n) |
| Kërkimi | O(n) | O(n) |
| Futje/fshirje në fillim | O(n) | O(1) |
| Futje/fshirje në fund | O(1) i amortizuar | O(1) me tregues fund |
| Futje/fshirje në mes | O(n) | O(n) kërkimi + O(1) ndarje |
| Mbingarkesa memorie | e ulët | e lartë (tregues për nod) |
| Lokaliteti i memores cache | i përsosur | i dobët |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
Në praktikë vargu fiton shumicën e kohës sepse lokaliteti i memores cache tejkalon dallimet Big-O për përmasat tipike.
Përvoja e të dyja ju lejon të justifikoni zgjedhjen tuaj në interview në vend që të vazhdoni verbërisht — dhe të shpjegoni pse "futje O(1)" rrallë e mund një varg të vazhdueshëm.