list: A Chain of Nodes You Can Cut and Rejoin Anywhere

Maria keeps her playlist in a vector, and she remembers the song now playing by its index. Today she wants to slip one new song in just before the current one, and another right after it. Each is one line of code. One of them costs more than she thinks, and the other quietly breaks her index. This lesson gives her a container where a position stays where it is: std::list.

Two problems with a playlist in a vector

Here is Maria's first try. Song 2 is playing, and she inserts a new song at index 1, in front of it.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    vector<string> playlist{"Intro", "Rain", "Train", "Outro"};
    size_t now = 2;
    cout << "now playing: " << playlist[now] << '\n';
    playlist.insert(playlist.begin() + 1, "Storm");
    cout << "after an insert in front of it: " << playlist[now] << '\n';
    return 0;
}

now playing: Train
after an insert in front of it: Rain

Nothing crashed, and the answer is wrong. The insert pushed "Train" from index 2 to index 3, so the saved index now names "Rain". An index says "the third box", not "this song", and boxes get renumbered. That is the first problem: a position you saved can move under you.

The second problem is the cost. An insert in the middle of a vector shifts every later element one box to the right. Module 2's lesson 02 measured the extreme case: 100,000 inserts at the front of a vector took about a third of a second. A long playlist pays that shift on every insert.

You have met the fix before. In C Module 14 lesson 04 you built a linked list by hand. It was a struct node with a value and a next pointer, one malloc per node, and a push_front that rewired a pointer. Nothing moved when you added a node. std::list is that idea with a second link in every node, and with the malloc, the links and the free written once, inside the library. So a list keeps each value where it was first put, and only links change.

The picture: a node with two links

A node is one small block on the heap that holds one value and two links. next holds the address of the node after it, and prev the address of the node before it. The list object itself, the l you declare, keeps the first node, the last node and a count. It never keeps the values side by side.

The second link is what makes the difference. With prev, a node knows its neighbour on both sides, so you can walk backwards and erase a node without first finding the one before it. On GCC 12 a node for an int asks the heap for 24 bytes: two 8-byte links, the 4-byte value and 4 bytes of padding. Lesson 05 measures that. So one value costs one node, and the list object only holds the two ends and the count.

Now watch it move. Each step below is one call on the same list. Look at which nodes change their links, which one fades when it is erased, and the node 30, which nobody touches after it arrives.

Count what moved in those six steps: nothing. Every node stayed at the address it was born at, and each call changed at most four links. So an insert or an erase in a list costs the same few steps wherever it happens, once you hold the position.

The syntax you need on day one

#include <list>

list<T> l;                    an empty list of T
l.push_back(x);               add x after the last element
l.push_front(x);              add x before the first element
l.pop_back();                 remove the last element
l.pop_front();                remove the first element
l.front()   l.back()          the first and the last element
l.size()    l.empty()         how many, and whether there are none
l.begin()   l.end()           an iterator to the first, and to past the last
++it;  --it;  *it             step forward, step back, read the element
l.insert(it, x)               add x before it; returns the new node's iterator
l.erase(it)                   remove the element at it; returns the next one
l.splice(pos, other)          move every node of other in before pos

So a list has a push and a pop at each end, and everything in the middle goes through an iterator.

No index: you walk with ++ and --

A vector finds v[2] with one sum: the first box plus two boxes. A list has no such sum, because its nodes sit wherever the heap put them. So it has no operator[] at all. Bob tries anyway.

list<int> l{10, 20, 30};
cout << l[1] << '\n';

GCC 12 stops with error: no match for 'operator[]' (operand types are 'std::__cxx11::list<int>' and 'int'). The __cxx11 in the name is just GCC's library labelling its own version of list. To reach the second element, you start at begin() and follow one link.

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l{10, 20, 30, 40};

    cout << "forward:";
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
        cout << ' ' << *it;
    }

    cout << "\nbackward:";
    list<int>::iterator it = l.end();
    while (it != l.begin()) {
        --it;
        cout << ' ' << *it;
    }

    it = l.begin();
    ++it;
    ++it;
    cout << "\nthe third one: " << *it << '\n';
    return 0;
}

forward: 10 20 30 40
backward: 40 30 20 10
the third one: 30

The backward walk starts at end(), the place after the last element, and steps back before it reads. That order matters: *l.end() is not an element. A range-for, for (int x : l), does the forward walk for you and is the usual way to read a whole list. So reaching element k costs k steps, and a list is read from one end or the other.

insert puts a node before an iterator

l.insert(it, x) makes a new node for x and links it in just before the node it points at. The picture below is step five of the widget, slowed down.

The call returns an iterator to the new node, and the old iterator is untouched. l.insert(l.end(), x) is the same as push_back, and l.insert(l.begin(), x) the same as push_front.

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l{10, 20, 30};
    list<int>::iterator it = l.begin();
    ++it;
    list<int>::iterator fresh = l.insert(it, 15);
    cout << "fresh: " << *fresh << ", it: " << *it << '\n';

    l.insert(l.end(), 40);
    l.insert(l.begin(), 5);
    cout << "list:";
    for (int x : l) {
        cout << ' ' << x;
    }
    cout << '\n';
    return 0;
}

fresh: 15, it: 20
list: 5 10 15 20 30 40

So insert always lands in front of the iterator you give it, and the iterator keeps pointing at the same element.

erase, and the it = l.erase(it) walk

l.erase(it) links the two neighbours of it to each other and frees its node. After that, it points at freed memory and must not be used. That is why erase returns an iterator to the next node: it is where your walk goes on.

Zara's sensor writes 0 when it misses a reading. She walks the list once and erases every 0.

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> readings{21, 0, 23, 0, 0, 24};

    list<int>::iterator it = readings.begin();
    while (it != readings.end()) {
        if (*it == 0) {
            it = readings.erase(it);
        } else {
            ++it;
        }
    }

    cout << "readings:";
    for (int r : readings) {
        cout << ' ' << r;
    }
    cout << " (size " << readings.size() << ")\n";
    return 0;
}

readings: 21 23 24 (size 3)

Look at the two zeros in a row. After the first is erased, it already points at the second, so the loop must not also step. That is why ++it sits in the else branch. Lesson 02 shows remove, which does this whole walk in one call. So a walk that erases is a while loop, and it advances either by erase or by ++it, never both.

Positions that survive

Here is the promise the widget showed. An insert never moves an existing node, and an erase frees only its own. So an iterator to any other element stays good: it still points at the same node, holding the same value. This program replays the widget's six calls and holds two iterators through all of them.

#include <iostream>
#include <list>
#include <string>
using namespace std;

void show(const string& call, const list<int>& l) {
    cout << call << ":";
    for (int x : l) {
        cout << ' ' << x;
    }
    cout << '\n';
}

int main() {
    list<int> l;
    l.push_back(10);
    l.push_back(20);
    l.push_back(30);
    list<int>::iterator thirty = l.end();
    --thirty;
    list<int>::iterator twenty = thirty;
    --twenty;
    show("three push_back", l);

    l.push_front(5);
    show("push_front(5)", l);
    list<int>::iterator fifteen = l.insert(twenty, 15);
    show("insert 15 before 20", l);
    l.erase(twenty);
    show("erase 20", l);

    cout << "fifteen points at " << *fifteen << ", thirty at " << *thirty << '\n';
    return 0;
}

three push_back: 10 20 30
push_front(5): 5 10 20 30
insert 15 before 20: 5 10 15 20 30
erase 20: 5 10 15 30
fifteen points at 15, thirty at 30

thirty was made before four other calls changed the list, and it still reads 30. Only twenty died, with its node, and the program never touches it again. A vector gives no such promise: an insert can reallocate and move every element, as Module 2 showed. So in a list, the only iterator an erase breaks is the one to the erased element, and an insert breaks none.

splice: moving nodes from another list

A list can do something no other container in this track can. l.splice(pos, other) takes every node out of other and links them into l before pos. No value is copied and no node is made or freed: only the links at the two seams change. Watch three pages that arrived late join a report.

The program below does the same splice, and checks that the node holding 3 is the very node it was before.

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> pages{1, 2, 6};
    list<int> late{3, 4, 5};
    list<int>::iterator three = late.begin();
    const int* where = &*three;

    list<int>::iterator pos = pages.end();
    --pos;
    pages.splice(pos, late);

    cout << "pages:";
    for (int p : pages) {
        cout << ' ' << p;
    }
    cout << "\nlate holds " << late.size() << " pages\n";
    cout << "three: " << *three << ", same node: " << (where == &*three) << '\n';
    return 0;
}

pages: 1 2 3 4 5 6
late holds 0 pages
three: 3, same node: 1

&*three is the address of the value three points at. It is the same before and after, so the node really moved between lists without moving in memory. The iterator three is still good; it now walks pages. So splice moves a whole list in a few link writes, however many nodes it holds, and lesson 02 shows its other two forms.

forward_list: the one-way cousin

std::forward_list is exactly the list you built in C: each node has a value and next, and nothing else. It lives in <forward_list>. With only one link, a node cannot reach the node before it. So there is no insert before a position: there is insert_after, which adds a node after the one you hold.

#include <forward_list>
#include <iostream>
#include <list>
using namespace std;

int main() {
    forward_list<int> f;
    f.push_front(30);
    f.push_front(10);
    forward_list<int>::iterator it = f.begin();
    f.insert_after(it, 20);

    cout << "f:";
    for (int x : f) {
        cout << ' ' << x;
    }
    cout << '\n';
    cout << "sizeof(forward_list<int>): " << sizeof(forward_list<int>) << '\n';
    cout << "sizeof(list<int>): " << sizeof(list<int>) << '\n';
    return 0;
}

f: 10 20 30
sizeof(forward_list<int>): 8
sizeof(list<int>): 24

A forward_list object is one pointer, 8 bytes, against the list's 24. It also has no size(), no push_back and no --it. Lesson 02 shows each missing call with GCC 12's message, and the rest of its operations. So reach for forward_list only when one-way walking is enough and every byte counts.

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l{20, 30};
    l.push_front(10);
    l.push_back(40);
    cout << "front " << l.front() << ", back " << l.back() << ", size " << l.size() << '\n';
    l.pop_front();
    l.pop_back();
    cout << "front " << l.front() << ", back " << l.back() << ", size " << l.size() << '\n';
    return 0;
}

front 10, back 40, size 4
front 20, back 30, size 2

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main() {
    list<string> train{"engine", "coach A", "coach B"};

    list<string>::iterator it = train.begin();
    ++it;
    train.insert(it, "dining car");
    train.push_back("guard van");

    for (it = train.begin(); it != train.end(); ++it) {
        if (*it == "coach B") {
            train.erase(it);
            break;
        }
    }

    bool first = true;
    for (const string& car : train) {
        cout << (first ? "" : " - ") << car;
        first = false;
    }
    cout << '\n';
    return 0;
}

engine - dining car - coach A - guard van

#include <iostream>
#include <list>
#include <string>
using namespace std;

int main() {
    list<string> playlist{"Intro", "Rain", "Train", "Outro"};
    list<string>::iterator now = playlist.begin();
    ++now;
    ++now;
    const string* where = &*now;
    cout << "now playing: " << *now << '\n';

    list<string>::iterator second = playlist.begin();
    ++second;
    playlist.insert(second, "Storm");

    list<string>::iterator after = now;
    ++after;
    playlist.insert(after, "Snow");

    playlist.erase(playlist.begin());

    cout << "now playing: " << *now << '\n';
    cout << "same node: " << (where == &*now) << '\n';
    cout << "playlist:";
    for (const string& song : playlist) {
        cout << ' ' << song;
    }
    cout << '\n';
    return 0;
}

now playing: Train
now playing: Train
same node: 1
playlist: Storm Rain Train Snow Outro

list<int> l{10, 20, 30};
list<int>::iterator it = l.begin();
cout << *(it + 1) << '\n';

list<int> l{1, 0, 2};
for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
    if (*it == 0) {
        l.erase(it);
    }
}

#include <iostream>
using namespace std;

int main() {
    list<int> l{10, 20};
    cout << l.size() << '\n';
    return 0;
}

list<int> l{10, 20, 30};
l.insert(1, 15);

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l{1, 2, 3};
    int passes = 0;
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
        l.insert(it, *it * 10);
        passes++;
    }
    cout << "passes: " << passes << '\n';
    for (int x : l) {
        cout << x << ' ';
    }
    cout << '\n';
    return 0;
}

#include <iostream>
#include <list>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    list<int> tasks;
    for (int i = 0; i < n; i++) {
        int x = 0;
        cin >> x;
        tasks.push_back(x);
    }

    // Walk tasks once with an iterator: erase every negative number,
    // and insert a copy right after every even one that stays.

    // Print tasks on one line, or the word empty if nothing is left.

    return 0;
}

#include <iostream>
#include <list>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    list<int> row;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        row.push_back(x);
    }

    // Walk one iterator forward from row.begin() and one backward
    // from row.end(), n / 2 steps each, comparing the two values.
    // Print yes if every pair matched, otherwise no.

    return 0;
}

#include <iostream>
#include <list>
using namespace std;

int main() {
    int n, t;
    cin >> n >> t;
    list<int> deck;
    for (int c = 1; c <= n; c++) {
        deck.push_back(c);
    }

    // Repeat t times: move the bottom half of deck into its own list,
    // then put its cards back one by one, each after a card of the top
    // half. Then print deck from top to bottom.

    return 0;
}

Next, lesson 02 goes through every operation of list and forward_list, one by one, each with its cost.