Lists (std::list)

Lists (std::list)

A std::list is a doubly-linked list: the data lives in separate nodes, and each node carries links to the node before and after it.

Create one

#include <list>

std::list<int> myList;

Add elements from either end

myList.push_back(20);    // add at the end
myList.push_front(2);    // add at the front

Now the list holds {2, 20}.

Reach it with a range-for

for (int n : myList) {
    std::cout << n << "\n";
}

A list has no index brackets, but the range loop hands you each value in order.

Insert in the middle

Inserting somewhere in the middle is exactly the job a linked list is good at. Give it an iterator as the spot:

auto it = myList.begin();
++it;                     // now at the second node
myList.insert(it, 5);     // put 5 just before that node

list vs vector

The trade-off: a list splices nodes cheaply anywhere, but you cannot jump to "the 7th element" directly. You walk node by node.

TL;DR

• std::list is a doubly-linked list built from nodes.
• push_front and push_back add at either end.
• insert(iterator, value) places a value at a spot you point to.
• A list cannot be indexed directly; you walk from an end.
• Use a vector for random access and a list for mid-sequence insertion.