Lista

Lista to wbudowany kontener sekwencyjny C++, który umożliwia nieciągłą alokację pamięci. Mówiąc o liście, mamy na myśli listę dwukierunkową. Istnieje też inny typ listy, nazywany listą jednokierunkową (forward list). 

Aby wszystko było jasne: 
Struktura danych vector umożliwia ciągłą alokację pamięci, co oznacza, że każdy element znajduje się w pamięci bezpośrednio za poprzednim elementem.
Natomiast struktura danych linked list zawiera elementy składające się z części przechowującej dane (właściwą wartość) oraz wskaźnika zawierającego adres pamięci następnego elementu na liście.

W C++ istnieją dwa typy list wiązanych:

• lista dwukierunkowa - list
• lista jednokierunkowa - forward list

Główna różnica między listą dwukierunkową a listą jednokierunkową polega na tym, że listy jednokierunkowe umożliwiają iterowanie tylko w przód, co oznacza, że każdy element ma własną wartość i adres pamięci następnego elementu. Elementy listy dwukierunkowej przechowują natomiast informacje o tym, jak znaleźć następny i poprzedni element listy.

Korzystamy z list (listy dwukierunkowej) i forward list (listy jednokierunkowej), dołączając je do pliku za pomocą:

#include <list>
#include <forward_list>

Możemy też po prostu dołączyć plik nagłówkowy bits/stdc++.h.

Lista jednokierunkowa

Najpierw omówimy listę jednokierunkową. Ma ona wiele metod, a my omówimy te najbardziej przydatne.
Deklarujemy forward list dokładnie tak samo jak vector i deque.

forward_list<int> flist = {1, 2, 3};

Możemy dodawać elementy za pomocą metody push_front(), a usuwać je z początku za pomocą pop_front().

flist.push_front(5);
for (int &x : flist) // wypisujemy elementy za pomocą wskaźnika, którego wartość zwiększa się przy każdej iteracji
	cout << x << " ";
cout << endl;

flist.pop_front();
for (int &x : flist)
	cout << x << " ";

Output:
5 1 2 3
1 2 3

Metody listy jednokierunkowej

Lista

Następna jest lista. Struktura danych list ma również wiele metod, ale poznasz te najbardziej przydatne. 
Najpierw dowiesz się, jak zadeklarować listę po dołączeniu jej na początku pliku .cpp. 

list<int> list1 = {1, 2, 3};

Możemy dodawać elementy do listy za pomocą metody push_front() lub push_back().
Podobnie możemy usuwać pierwszy i ostatni element za pomocą odpowiednio metod pop_front() i pop_back().

list1.push_back(4);
list1.push_front(0);
for (int &x : list1)
	cout << x << " ";
cout << endl;

list1.pop_front();
list1.pop_back();
for (int &x : list1)
	cout << x << " ";

Output:
0 1 2 3 4
1 2 3

Metody listy