template<typenameType>// Implementacja listy jednokierunkowej.classList{structNode{// Zagnieżdżona klasa pomocnicza.Typevalue;Node*next;Node(Typed){// 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.voidinsert(Typedata);// Dodaje do listy w czasie O(1).voidremove(intn);// Usuwa n-ty element listy.Typefind(intn);// Zwraca wartosc z n-tego elementu listy.voidclear();// Usuwa wszystkie elementy z listy.voiddisplay();// Funkcja wypisująca całą listę, elementy oddzielone spacją.};template<typenameType>List<Type>::List(){head=nullprt;tail=nullptr;}template<typenameType>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.deletetemp;// Usuwamy węzeł, na który wskazuje zmienna pomocnicza.temp=head;// Idziemy dalej aż nie natrafimy na ogon.}deletetail;// Usuwamy węzeł, na który wskazuje ogon.}template<typenameType>voidList<Type>::insert(Typedata){if(head!=nullprt){// W przypadku gdy mamy jakieś elementy w liście.Node*temp=newNode(data);if(temp==nullprt)throw"Błąd alokacji pamięci, przy dodawaniu elementu do listy!";tail->next=temp;tail=temp;}else{head=newNode(data);tail=head;}}template<typenameType>voidList<Type>::remove(intn){Node*temp=head;Node*prev=nullptr;for(inti=0;i<n;++i){// W pętli będziemy szukać elementu do usuniecia.if(temp!=nullptr){prev=temp;temp=temp->next;}elsethrow"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;deletetemp;}template<typenameType>TypeList<Type>::find(intn){Node*temp=head;for(inti=0;i<n;++i){// W pętli będziemy szukać elementu do usuniecia.if(temp!=nullptr)temp=temp->next;elsethrow"Lista jest krótsza niż argument w remove!";}returntemp->value;}template<typenameType>voidList<Type>::clear(){Node*temp=head;while(temp!=tail){// Do momentu kiedy nie natrafimy na ogon.head=temp->next;// Podmieniamy head na następny element.deletetemp;// Usuwamy węzeł, na który wskazuje zmienna pomocnicza.temp=head;// Idziemy dalej aż nie natrafimy na ogon.}deletetail;// Usuwamy węzeł, na który wskazuje ogon.head=nullptr;tail=nullptr;}template<typenameType>voidList<Type>::display(){Node*i=head;while(i!=nullptr){std::cout<<i->wartosc<<" ";i=i->next;}std::cout<<std::endl;}