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