Třetím úkolem začíná série úkolů, během níž budete implementovat oboustranně zřetězený spojový seznam (viz 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í zde.

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.

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.

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 <-------------------------
 

Pro tento úkol žádné hlavičky ze standardní knihovny nedoporučujeme.

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.