Struktury danych/Implementacje w C++/Listy

Lista jednokierunkowa

Generyczna implementacja wskaźnikowa

template <typename Type>
// Implementacja listy jednokierunkowej.
class List {
    struct Node { 
    // Zagnieżdżona klasa pomocnicza.
    Type  value;
        Node* next;
        Node(Type d) {      // Konstruktor jednoargumentowy.
            value = d;      // Przypisanie wartości podczas konstrukcji.
            next = nullptr;
        }
    };

    Node* head; // Wskaźnik do głowy listy.
    Node* tail; // Wskaźnik do ogona listy.

public:
    List();  // Konstruktor listy.
    ~List(); // Destruktor listy.

    void insert(Type data); // Dodaje do listy w czasie O(1).
    void remove(int n);     // Usuwa n-ty element listy.
    Type find(int n);       // Zwraca wartosc z n-tego elementu listy.
    void clear();           // Usuwa wszystkie elementy z listy.
    void display();         // Funkcja wypisująca całą listę, elementy oddzielone spacją.
};


template <typename Type>
List<Type>::List() {
    head = nullprt;
    tail = nullptr;
}

template <typename Type>
List<Type>::~List() {
    Node* temp = head;
        while (temp != tail) {    // Do momentu kiedy nie natrafimy na ogon.
            head = temp->next;    // Podmieniamy head na następny element.
            delete temp;          // Usuwamy węzeł, na który wskazuje zmienna pomocnicza.
            temp = head;          // Idziemy dalej aż nie natrafimy na ogon.
	}
    delete tail;                  // Usuwamy węzeł, na który wskazuje ogon.
}

template <typename Type>
void List<Type>::insert(Type data){
    if (head != nullprt) {        // W przypadku gdy mamy jakieś elementy w liście.
        Node* temp = new Node(data);
        if (temp == nullprt) 
            throw "Błąd alokacji pamięci, przy dodawaniu elementu do listy!";
        tail->next = temp;
        tail = temp;
    }
    else {
        head = new Node(data);
        tail = head;
    }
}

template <typename Type>
void List<Type>::remove(int n) {
    Node* temp = head;
    Node* prev = nullptr;
        for (int i=0; i<n; ++i){  // W pętli będziemy szukać elementu do usuniecia.
            if (temp != nullptr) {
	        prev = temp;
	        temp = temp->next;	
	    }
	    else
                throw "Lista jest krótsza niż argument w remove!";
	}

    // Przepinamy tutaj wskaźnik do następnego elementu poprzedniego rekordu listy
    // na ten, na który wskazywał element, który mamy usunąć
    // następnie go usuwamy.
    prev->next = temp->next;
    delete temp;
}

template <typename Type>
Type List<Type>::find(int n) {
    Node* temp = head;
    for (int i=0; i<n; ++i) {   // W pętli będziemy szukać elementu do usuniecia.
        if (temp != nullptr)
	    temp = temp->next;	
        else
            throw "Lista jest krótsza niż argument w remove!";
    }
    return temp->value;
}

template <typename Type>
void List<Type>::clear() {
    Node* temp = head;
    while (temp != tail) {     // Do momentu kiedy nie natrafimy na ogon.
        head = temp->next;     // Podmieniamy head na następny element.
        delete temp;           // Usuwamy węzeł, na który wskazuje zmienna pomocnicza.
        temp = head;           // Idziemy dalej aż nie natrafimy na ogon.
    }
    delete tail;               // Usuwamy węzeł, na który wskazuje ogon.
	
    head = nullptr;
    tail = nullptr;
}

template <typename Type>
void List<Type>::display() {
    Node* i = head;
    while (i!=nullptr) {
        std::cout << i->wartosc << " ";
        i=i->next;
    }
    std::cout << std::endl;
}