===== Úkol 3 ===== Třetím úkolem začíná série úkolů, během níž budete implementovat oboustranně zřetězený spojový seznam (viz [[https://en.wikipedia.org/wiki/Doubly_linked_list|Wikipedia]]) ve stylu standardní knihovny. Jedná se o strukturu ''list'', která pro každý obsažený prvek alokuje strukturu ''list::node''. Samotná struktura ''list'' obsahuje ukazatel ''head'', který ukazuje na první prvek v seznamu (front), naopak ukazatel ''tail'' ukazuje na poslední prvek v seznamu (back). Pokud má seznam pouze jeden prvek, pak ''head'' i ''tail'' ukazují na ten samý objekt. Pokud seznam nemá žádné prvky, ''head'' i ''tail'' jsou nastaveny na ''nullptr''. struct list { struct node { double val; node* prev; node* next; }; node* head = nullptr; node* tail = nullptr; size_t size = 0; }; Ve struktuře ''list::node'' se také nachází dva ukazatele, ''prev'' a ''next''. Ukazatel ''next'' vždy ukazuje na další (následující) prvek v seznamu, ''prev'' na předchozí. Pokud je prvek prvním prvkem v seznamu, ''prev'' je nastaven na ''nullptr''. Pokud je prvek posledním prvkem v seznamu, ''next'' je nastaven na ''nullptr''. Potřebné hlavičkové soubory a testy ke stažení {{:courses:a7b36pjc:ukoly:small3.zip|zde}}. ==== Co odevzdat? ==== Jeden nebo více ''.cpp'' souborů, které implementují funkce deklarované v souboru ''list.hpp'' tak, aby testy procházely a neztrácela se paměť. Při práci na úkolu soubor ''list.hpp'' neměňte. ===== Rady ===== Doporučujeme o listu přemýšlet a pohybovat se v něm podobně jako ve stromu, to jest jako v sérii uzlů. Prakticky to znamená, že by se člověk při průchodech neměl orientovat dle velikosti, ale dle struktury -- začátek se pozná dle ''prev == nullptr'', konec se pozná dle ''next == nullptr''. Ostatní uzly jsou jednoduše někde uprostřed; není důležité, kde přesně. Stejně tak doporučujeme vždy aktualizovat ukazatele prvků v listu, i v případě, že to není striktně potřeba. Pokud tedy například smažete aktuálně poslední uzel v listu, tak krom přesunutí ukazatele ''tail'' byste měli aktualizovat i ''next'' ukazatel předposledního (nově posledního) uzlu listu. ==== Přístup ke smazané paměti ==== Dávejte si pozor na přístup ke smazané paměti, protože jakmile jednou kus paměti uvolníte, všechna data v ní jsou pro vás ztracena. To znamená, že například při mazání listu je potřeba nejdříve přesunout hlavu a pak až smazat první prvek. Malá ilustrace (node je celá struktura reprezentující uzel v listu a šipky jsou ukazatele): Začneme se správně zkonstruovaným listem, který má 4 prvky. head | | _____V__ ________ ________ ________ / node | / node | / node | / node | |------ | |------ | |------ | |------ | | value | | value | | value | | value | | next | -->| next | -->| next | -->| next | --| |-- | prev |<-- | prev |<-- | prev |<-- | prev | | | |-------- |-------- |-------- |-------- | ----------------------> nullptr <------------------------- Pokud smažeme uzel, na který ukazuje head, dostaneme se do tohoto stavu: head | | _____V__ ________ ________ ________ / nod/ | / node | / node | / node | |\--/-- | |------ | |------ | |------ | | \/lue | | value | | value | | value | | /\xt | | next | -->| next | -->| next | --| |/pre\ |<-- | prev |<-- | prev |<-- | prev | | |-------- |-------- |-------- |-------- | nullptr <-------------------------- A z něho už nemůžeme pokračovat s mazáním, protože nemůžeme přistoupit k hodnotě ''head.next''. Správně musíme nejdříve posunout hlavu: head | | ________ ____V___ ________ ________ / node | / node | / node | / node | |------ | |------ | |------ | |------ | | value | | value | | value | | value | | next | -->| next | -->| next | -->| next | --| |-- | prev |<-- | prev |<-- | prev |<-- | prev | | | |-------- |-------- |-------- |-------- | ----------------------> nullptr <------------------------- A pak teprve můžeme smazat první uzel. head | | _______ ______V_ ________ ________ / nod/ | / node | / node | / node | |\--/--| |------ | |------ | |------ | | \/lue| | value | | value | | value | | /\xt | | next | -->| next | -->| next | --| |/pre\ | |- | prev |<-- | prev |<-- | prev | | |------- | |-------- |-------- |-------- | --------> nullptr <------------------------- ==== Užitečné hlavičky ==== Pro tento úkol žádné hlavičky ze standardní knihovny nedoporučujeme. ==== Potíže s leaky a odevzdávacím systémem ==== V minulém semestru byl s tímto úkolem problém, že pokud vám neprocházel některý test, pak vám Valgrind hlásil únik paměti i tam, kde není. Pro tento semestr jsme to opravili, nicméně je možné, že jsme nějaký případ nepodchytili.