Oba ukládají sekvence, ale mají opačné profily nákladů. Pole je souvislá paměť s indexováním O(1); spojovaný seznam je rozptýlené uzly spojené ukazateli, s vkládáním/mazáním O(1) na koncích, ale bez indexování.
Oba ukládají sekvence, ale mají opačné profily nákladů. Pole je souvislá paměť s indexováním O(1); spojovaný seznam je rozptýlené uzly spojené ukazateli, s vkládáním/mazáním O(1) na koncích, ale bez indexování.
Knihovna IT otázek k pohovoru s podrobnými odpověďmi — od Junior po Senior.
Přispět| Operace | Pole (dynamické) | Spojovaný seznam |
|---|
| Přístup podle indexu | O(1) | O(n) |
| Hledání | O(n) | O(n) |
| Vkládání/mazání na začátku | O(n) | O(1) |
| Vkládání/mazání na konci | O(1) amortizovaně | O(1) s tail ptr |
| Vkládání/mazání uprostřed | O(n) | O(n) hledání + O(1) splice |
| Režie paměti | nízká | vysoká (ukazatel na uzel) |
| Lokalita mezipaměti | výborná | slabá |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
V praxi pole vyhrávají ve většině případů, protože lokalita mezipaměti převažuje rozdíly Big-O pro typické velikosti.
Znalost obou vám umožňuje zdůvodnit svou volbu v pohovorech namísto slepého předpokladu — a vysvětlit proč "O(1) vkládání" zřídka překonává souvislé pole.