Lista

List è un contenitore di sequenza integrato in C++ che consente l’allocazione non contigua della memoria. Quando parliamo di una list, intendiamo una lista doppiamente concatenata. Esiste un altro tipo di lista chiamato forward list, che indica una lista semplicemente concatenata. 

Per chiarire tutto. 
La struttura dati vector consente l’allocazione contigua della memoria, ovvero ogni elemento si trova direttamente dopo quello precedente in memoria.
La struttura dati linked list , invece, contiene elementi costituiti da una parte dati (il valore effettivo) e da un puntatore che contiene l’indirizzo di memoria dell’elemento successivo nella lista.

In C++ esistono due tipi di liste concatenate:

• lista doppiamente concatenata - list
• lista semplicemente concatenata - forward list

La differenza principale tra la lista doppiamente concatenata e la lista semplicemente concatenata è che le liste semplicemente concatenate possono scorrere solo in avanti: ogni elemento contiene il proprio valore e l’indirizzo di memoria dell’elemento successivo. Gli elementi della lista doppiamente concatenata , invece, memorizzano le informazioni necessarie per individuare l’elemento successivo e quello precedente nella lista.

Usiamo list (lista doppiamente concatenata) e forward list (lista semplicemente concatenata) includendole nel nostro file con:

#include <list>
#include <forward_list>

Oppure includiamo semplicemente il file header bits/stdc++.h.

Forward List

Per prima cosa parleremo di forward list. Esistono molti metodi per la forward list; parleremo dei più utili.
Dichiariamo una forward list esattamente come abbiamo fatto con vector e deque.

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

Possiamo aggiungere elementi usando il metodo push_front() e rimuoverli dall’inizio usando pop_front().

flist.push_front(5);
for (int &x : flist) // stampiamo gli elementi usando un puntatore il cui valore aumenta a ogni iterazione
	cout << x << " ";
cout << endl;

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

Output:
5 1 2 3
1 2 3

Metodi di Forward List

List

Ora passiamo a list. Anche per la struttura dati list esistono molti metodi, ma vedrai quelli più utili. 
Per prima cosa, imparerai a dichiarare una list dopo averla inclusa all’inizio del file .cpp. 

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

Possiamo aggiungere elementi alla lista usando il metodo push_front() oppure push_back().
Allo stesso modo, possiamo rimuovere il primo e l’ultimo elemento usando rispettivamente i metodi pop_front() e 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

Metodi di List