Lista jednokierunkowa Generyczna implementacja wskaźnikowa template // 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 List::List() { head = nullprt; tail = nullptr; }
template List::~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 void List::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 void List::remove(int n) { Node* temp = head; Node* prev = nullptr; for (int i=0; inext;
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 Type List::find(int n) { Node* temp = head; for (int i=0; inext; else throw "Lista jest krótsza niż argument w remove!";
return temp->value; }
template void List::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 void List::display() { Node* i = head; while (i!=nullptr) { std::cout wartosc next;
std::cout << std::endl; }