STL — Standard Template Library

Liste (list)

list<T> este o listă dublu-înlănțuită. Inserare/ștergere la orice poziție în O(1), dar acces la element arbitrar în O(n).

#include <list>
using namespace std;

list<int> l = {3, 1, 4, 1, 5};
l.push_front(0);    // adaugă la început
l.push_back(9);     // adaugă la sfârșit
l.pop_front();      // elimină primul
l.pop_back();       // elimină ultimul

for (int x : l) cout << x << " ";
// 3 1 4 1 5

Inserare la poziție

list<int> l = {1, 2, 4, 5};
auto it = l.begin();
advance(it, 2);         // avansează la poziția 2
l.insert(it, 3);        // inserează 3 înainte de poziția 2
// Rezultat: 1 2 3 4 5

	vector	list
Acces random [i]	O(1)	O(n)
push_back	O(1) amortizat	O(1)
Inserare la mijloc	O(n)	O(1) cu iterator
Folosit când	Acces frecvent	Inserări/ștergeri frecvente la mijloc