AiSD (index)

AiSD (5) - ADT LIST (lista podwójnie powiązana)

OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie.

WPROWADZENIE

Listy powiązane podwójnie mają elementy powiązane dwoma łączami: do elementu następnego (next) i do elementu poprzedniego (prev). W łatwy sposób możemy poruszać się po liście do przodu i wstecz. Ponadto przy usuwaniu węzła musimy znać tylko łącze do niego samego, podczas gdy przy listach połączonych pojedynczo potrzebne było też łącze do węzła poprzedzającego.

Lista powiązana podwójnie może być wykorzystana do implementacji std::list z biblioteki STL.

|      head                  tail             |
|       |                     |               |
|       o                     o               |
|    +-+--+-+              +-+--+-+    puste  |
| |--+ |11| +--o+-+--+-+o--+ |22| +--| łącze  |
|    +-+--+-+o--+ |33| +--o+-+--+-+           |
|               +-+--+-+                      |

// Szablon dla pojedynczego węzła listy.
template <typename T>
struct DoubleNode {
    T value;
    DoubleNode *next, *prev;
    // konstruktor domyślny
    DoubleNode() : value(T()), next(nullptr), prev(nullptr) {}
    DoubleNode(const T& item, DoubleNode *nptr=nullptr, DoubleNode *pptr=nullptr)
        : value(item), next(nptr), prev(pptr) {} // konstruktor
    ~DoubleNode() {} // destruktor
};

// Szablon dla listy powiązanej podwójnie.
template <typename T>
class DoubleList {
    DoubleNode<T> *head, *tail;
public:
    DoubleList() : head(nullptr), tail(nullptr) {}
    ~DoubleList(); // tu trzeba wyczyścić węzły
    DoubleList(const DoubleList& other); // copy constructor
    DoubleList(DoubleList&& other); // move constructor NIEOBOWIAZKOWE
    DoubleList& operator=(const DoubleList& other); // copy assignment operator, return *this
    DoubleList& operator=(DoubleList&& other); // move assignment operator, return *this NIEOBOWIAZKOWE
    bool empty() const { return head == nullptr; }
    int size() const; // O(n) bo trzeba policzyć
    void push_front(const T& item); // O(1)
    void push_front(T&& item); // O(1) NIEOBOWIAZKOWE
    void push_back(const T& item); // O(1)
    void push_back(T&& item); // O(1) NIEOBOWIAZKOWE
    T& front() const { return head->value; } // zwraca początek, nie usuwa
    T& back() const { return tail->value; } // zwraca koniec, nie usuwa
    void pop_front(); // usuwa początek O(1)
    void pop_back(); // usuwa koniec O(1)
    void clear(); // czyszczenie listy z elementów O(n)
    void display(); // O(n)
    void display_reversed(); // O(n)
};

ZADANIE 5.1

Przygotować implementację realizującą ADT LIST na bazie listy powiązanej podwójnie. Będzie to klasa DoubleList umieszczona w pliku doublelist.h. Uzupełnić plik doublelist.h, stworzyć funkcję main() i testy sprawdzające działanie interfejsu list.

ZADANIE 5.2

Zmienić klasę DoubleList przez wprowadzenie wartownika, czyli sztucznego węzła łączącego głowę i ogon listy powiązanej podwójnie. Wartownik nie przechowuje żadnych istotnych danych w polu value. W ten sposób powstaje lista cykliczna, co upraszcza wstawianie i usuwanie węzłów. W klasie DoubleList wystarczy przechowywać tylko łącze do wartownika.

|       nil       |     nil  +----------------------------+ |
|        |        |      |   |                            | |
|        o        |      o   o                            | |
|    +-+---+-+    |    +-+---+-+               +-+---+-+  | |
| +--+ | ? | +--+ | +--+ | ? | +--o+-+---+-+o--+ | B | +--+ |
| |  +-+---+-+  | | |  +-+---+-+o--+ | A | +--o+-+---+-+    |
| |     o o     | | |              +-+---+-+       o        |
| |     | |     | | |                              |        |
| +-----+ +-----+ | +------------------------------+        |

// Szablon dla listy powiązanej podwójnie z wartownikiem.
template <typename T>
class DoubleList {
    DoubleNode<T> *nil;
public:
    DoubleList(); // trzeba alokować wartownika
    ~DoubleList(); // tu trzeba wyczyścić węzły i wartownika
    bool empty() const { return nil->next == nil; }
    T& front() const { return nil->next->value; } // zwraca początek, nie usuwa
    T& back() const { return nil->prev->value; } // zwraca koniec, nie usuwa
};

template <typename T>
DoubleList<T>::DoubleList() {
    nil = new DoubleNode<T>(); // wartownik
    nil->next = nil;
    nil->prev = nil;
}

template <typename T>
void DoubleList<T>::push_front(const T& item) {
    DoubleNode<T> *node = new DoubleNode<T>(item, nil->next, nil);
    nil->next->prev = node;
    nil->next = node;
}

template <typename T>
void DoubleList<T>::pop_front() {
    assert(!empty());
    DoubleNode<T> *node = nil->next; // zapamiętujemy
    node->next->prev = node->prev; // ogólny schemat usuwania
    node->prev->next = node->next;
    // Przywracanie usuniętego węzła [Knuth]:
    // node->next->prev = node;
    // node->prev->next = node;
    delete node;
}

ZADANIE 5.3

Zmienić klasę DoubleList przez wprowadzenie atrybutu length typu int, który przechowuje aktualną długość listy powiązanej. Dzięki temu metoda size() może działać w czasie O(1), a nie O(n).

AiSD (index)