Programování 1 – 7. cvičení

Spojové seznamy

Cílem všech úkolů je procvičit si práci se spojovými seznamy. Pro jejich vyřešení tedy nepoužívejte jiné datové struktury (seznamy, apod.). Můžete úpravy provádět destruktivně, tedy přímo měnit prvky původního seznamu.

Pokud není uvedeno jinak, jako jeden ze vstupních parametrů dostanete první prvek seznamu a máte vrátit první prvek upraveného seznamu.

Vkládání do setřízeného seznamu

Do setřízeného seznamu vložte prvek s hodnotou xx.

Otočení seznamu

Otočte spojový seznam.

Mazání prvního výskytu

Ze seznamu vymaže prvek s hodnotou xx (první výskyt), pokud tam je.

Mazání všech výskytů

Ze seznamu vymaže všechny prvky s hodnotou xx.

Slévání (merge)

Dostanete dva setřízené spojové seznamy. Vraťte seznam, kde jsou všechny prvky obou seznamů a jsou setřízené. (Jako operace merge v merge sortu.)

Sudé a liché

Rozdělte seznam na dva seznamy. V prvním budou pouze sudé prvky, v druhém pouze liché.

Deque

Implementujte oboustrannou frontu (deque) pomocí obousměrného spojového seznamu. Operace na oboustranné frontě jsou

a všechny chceme provádět s konstantní časovou složitostí.

K zamyšlení: Proč nám nestačí jednosměrný seznam?

Řešení některých úloh

Řešení: linked_lists.py.