BPC-ALD_Zpracované_otazky_ke_zkousce
Níže je uveden pouze náhled materiálu. Kliknutím na tlačítko 'Stáhnout soubor' stáhnete kompletní formátovaný materiál ve formátu PDF.
Musíme mít uložený ukazatel na první uzel, a v posledním uzlu je ukazatel NULL.
Edit: uzel seznamu obsahuje hodnotu prvku a ukazatel na místo v paměti kde je ulozen další prvek.
0xF2 0xA1 0x04
0xF2
->
24
0xA1
->
1724
0x04
->
3
NULL
2. Uveďte srovnání časové složitosti práce s lineárním seznamem a polem při: (+++)
a) získání hodnoty prvku na daném indexu. Pro pole je časová složitost pro operaci získání hodnoty prvku na daném indexu výrazně lepší (O(1)) než pro
lineární seznám (O(n)
), protože prvky pole jsou v paměti ukládány striktně za sebou a stačí tedy jednoduše
zadat index prvku -
přímý přístup pomocí indexu. Zatímco u lineárního seznamu nemáme přístup k
jednotlivým uzlům a musíme vždy projít “celý” seznam (buď od konce nebo od začátku) až po hledaný uzel.
(Tuto věc řeší obousměrný seznam).
b) odebrání prvku z daného indexu.
V lineárním seznamu je potřeba doiterovat k danému uzlu, ten “zničit” a svázat jeho “předchůdce” a
“následníka”. V poli jsme schopni se dostat na daný prvek ihned, ale po odstranění prvku musíme všechny
následující prvky posunout o jednu pozici směrem k počátku, chceme-li zachovat pořadí prvků v poli (nevýhoda
pole -