C++ list

📜 C++ list (Doubly Linked List)

std::list is a doubly linked list container in the C++ STL.
It allows fast insertion and deletion anywhere in the list, but does not support random access.

🔹 1. Why Use list?

  • Fast insert/delete in the middle (O(1) with iterator)

  • No reallocation or shifting of elements

  • Stable iterators (remain valid after insert/erase elsewhere)

❌ Not good for:

  • Index-based access

  • Cache-friendly traversal

  • Sorting with random access

🔹 2. Include Header

#include <list>

🔹 3. Declaring a List

std::list<int> l;
std::list<int> l = {1, 2, 3};

With size/value:

std::list<int> l(5); // 5 elements (0)
std::list<int> l(5, 10); // 5 elements (10)

🔹 4. Adding Elements

l.push_back(10); // add at end
l.push_front(5); // add at beginning

🔹 5. Accessing Elements

list has no [] or at().

cout << l.front(); // first
cout << l.back(); // last

🔹 6. Traversing a List

Range-based loop

for (int x : l) {
cout << x << " ";
}

Iterator

for (auto it = l.begin(); it != l.end(); ++it) {
cout << *it << " ";
}

🔹 7. Removing Elements

l.pop_back(); // remove last
l.pop_front(); // remove first

Remove by value:

l.remove(10); // removes all 10s

Remove with condition:

l.remove_if([](int x){ return x % 2 == 0; });

🔹 8. Insert & Erase Using Iterator

auto it = l.begin();
advance(it, 1); // move iterator
l.insert(it, 99); // insert before it
l.erase(it); // erase at it

🔹 9. Size & State

l.size();
l.empty();
l.clear();

🔹 10. Sorting a List

std::sort ❌ does NOT work with list.

✔ Use built-in list::sort():

l.sort(); // ascending
l.sort(greater<int>()); // descending

🔹 11. Reversing a List

l.reverse();

🔹 12. Merging Two Sorted Lists

list<int> a = {1, 3, 5};
list<int> b = {2, 4, 6};

a.merge(b); // both must be sorted

🔹 13. list vs vector

Featurelistvector
MemoryNon-contiguousContiguous
AccessNo random accessO(1) random
Insert/Delete (middle)O(1)O(n)
Cache friendly❌✔
IteratorsStableMay invalidate

🔹 14. Time Complexity

OperationComplexity
Insert/Delete (with iterator)O(1)
SearchO(n)
Access first/lastO(1)
SortO(n log n)

❌ Common Mistakes

l[0]; // ❌ invalid
sort(l.begin(), l.end()); // ❌ invalid

📌 Summary

  • std::list = doubly linked list

  • Fast insert/delete anywhere

  • No random access

  • Use list::sort() and list::reverse()

  • Best when frequent middle operations are needed

You may also like...