AiSD (index)

AiSD (4) - ADT LIST (lista pojedynczo powiązana)

OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie.

WPROWADZENIE

Listy powiązane składają się z szeregu elementów (węzłów) powiązanych ze sobą łączami. Węzły list powiązanych pojedynczo przechowują pewną wartość oraz zawierają łącze do następnego węzła na liście. Jedynym sposobem dostania się do konkretnego węzła jest przejście przez listę od jej samego początku. Ostatni węzeł oznacza się zgodnie z jedną przedstawionych poniżej konwencji:

• za pomocą pustego łącza, które nie wskazuje żadnego węzła,
• za pomocą węzła-atrapy,
• za pomocą łącza wskazującego pierwszy element listy (lista cykliczna).

Listy powiązane są wykorzystywane do implementacji ADT LIST, dlatego przypomnimy typowe operacje dla tego ADT.

• konstruktor tworzący pustą listę,
• testowanie, czy lista nie jest pusta [empty()],
• odczyt liczby elementów na liście [size()],
• dołączanie elementu na początek listy [push_front(item)],
• dołączanie elementu na koniec listy [push_back(item)],
• dostęp do pierwszego (lewego skrajnego) elementu [front()],
• dostęp do ostatniego (prawego skrajnego) elementu [back()],
• usunięcie elementu pierwszego [pop_front()],
• usunięcie elementu ostatniego [pop_back()],
• czyszczenie listy [clear()],

Lista pojedynczo powiązana występuje w STL jako std::forward_list.

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

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

// Szablon dla listy powiązanej pojedynczo.
template <typename T>
class SingleList {
    SingleNode<T> *head, *tail;
public:
    SingleList() : head(nullptr), tail(nullptr) {} // konstruktor
    ~SingleList(); // destruktor, tu trzeba wyczyścić węzły
    SingleList(const SingleList& other); // copy constructor
    SingleList(SingleList&& other); // move constructor NIEOBOWIAZKOWE
    SingleList& operator=(const SingleList& other); // copy assignment operator, return *this
    SingleList& operator=(SingleList&& 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(n)
    void clear(); // czyszczenie listy z elementów O(n)
    void display(); // O(n)
    void reverse(); // O(n)
};

ZADANIE 4.1

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

ZADANIE 4.2

Zmienić klasę SingleList 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).

ZADANIE 4.3

Listę powiązaną pojedynczo opisaliśmy używając pojęcia węzła, który zawiera wartość i łącze do następnego węzła. Łącze jest pojęciem abstrakcyjnym, które w języku C++ realizuje się zwykle jako wskaźnik, jednak można zaimplementować łącza jako indeksy tablicy. Zaimplementować listę powiązaną pojedynczo z wykorzystaniem indeksów tablicy.

AiSD (index)