STL · Lesson 39

Lists

If a vector is a row of boxes sitting side by side, a list is a chain of paper clips: each element is a small node that holds a value and a link to the next node (and the previous one). Nothing sits in one block, so inserting or removing in the middle costs almost nothing — but you can only reach an element by walking the chain from the start.

1. What is a list?

A std::list is a doubly linked list: every node points forwards to the next node and backwards to the previous one. That is the whole design, and it explains everything else. Inserting a new node means changing two links — no elements move, nothing is copied, and every other iterator stays valid. The price is that there is no jumping: to reach the tenth element you must walk through the first nine.

Lists live in the <list> header, and the full name is std::list. Like a vector, it is a template: std::list<int> holds integers and std::list<std::string> holds words. Unlike a vector, a list can grow from BOTH ends cheaply — push_front is just as fast as push_back.

Code story: We are going to build a short list of numbers, and we will add them from both ends: 20 and 30 go in at the back, 10 is pushed in at the front, and 40 goes in at the back again. Then we print the whole list. Watch the final order — it tells you which end each number entered from.

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

int main() {
    list<int> numbers;

    numbers.push_back(20);
    numbers.push_back(30);
    numbers.push_front(10);
    numbers.push_back(40);

    for (int n : numbers) {
        cout << n << " ";
    }
    return 0;
}

10 20 30 40

What just happened? The list starts empty. push_back adds a new node at the end and push_front adds one at the start — both are equally cheap because nothing is shifted. The range-based for loop walks the chain from the first node to the last, printing 10, 20, 30, 40.

2. Creating a list

Lists are created the same three ways as vectors: from a list of starting values in curly braces, with a count of default values, or with a count of copies of one value. The meaning is identical — only the container underneath is different.

Code story: Here we create three lists in the three different ways: one from the values 1, 2, 3; one with five slots that start as zero; and one with three copies of the number 9. Then we print the size of each, and print every element of the third list to prove it really holds three nines.

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

int main() {
    list<int> a = {1, 2, 3};
    list<int> b(5);       // five zeros
    list<int> c(3, 9);    // three 9s

    cout << a.size() << " " << b.size() << " " << c.size() << endl;
    for (int n : c) {
        cout << n << " ";
    }
    return 0;
}

3 5 3
9 9 9

What just happened? a starts with three values, so its size is 3. b(5) creates five integers, each defaulting to 0. c(3, 9) creates three copies of 9. The size() function counts the nodes currently in the list.

3. Adding and removing elements

This is where a list shines. Adding or removing at either end is instant, and so is inserting or erasing in the middle — once you have an iterator pointing at the spot. What you give up is random access: a list has no operator[], so you move an iterator to a position with advance (from <iterator>), which steps it forward one node at a time.

Code story: We start with the numbers 10, 20, 40 — the 30 is missing. We walk an iterator two steps forward so it points at 40, insert 30 in front of it, and then remove the first element with pop_front. Watch the list quietly change shape: no element was ever shifted or copied.

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

int main() {
    list<int> v = {10, 20, 40};

    auto it = v.begin();
    advance(it, 2);            // point at 40
    v.insert(it, 30);          // insert 30 before 40
    v.pop_front();             // remove the first element (10)

    for (int n : v) {
        cout << n << " ";
    }
    return 0;
}

20 30 40

What just happened? advance(it, 2) walks the iterator forward two nodes so it points at 40. insert adds 30 just before it by re-linking two nodes. Then pop_front drops the first node, leaving 20, 30, 40. In a vector the same insert would have shifted every later element; here only two links changed.

Table 1 — List operations at a glance

4. Iterators only — no square brackets

The biggest surprise for vector users is that a list has no operator[]. You cannot write l[2] — it is a compile error, not a runtime choice. Elements are reached through iterators: begin() points at the first node, end() just past the last, and front() and back() give the two ends directly. To move an iterator, use advance(it, n) or next(it, n) — both walk one node at a time, so reaching the middle of a long list really does take that many steps.

Code story: We have a list of four names and we want the third one. There is no way to jump to it, so we take an iterator at the front and walk it two steps forward with advance. Then we print that name, followed by the first and last names using front() and back(). Watch the three outputs: third, first, last.

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

int main() {
    list<string> names = {"Ada", "Ben", "Cid", "Dee"};

    auto it = names.begin();
    advance(it, 2);   // walk two steps forward
    cout << *it << endl;          // the third name
    cout << names.front() << endl;
    cout << names.back() << endl;
    return 0;
}

Cid
Ada
Dee

What just happened? advance(it, 2) moves the iterator from "Ada" past "Ben" to "Cid", and *it reads the value there. front() and back() are shortcuts for the two ends. Notice: advance can also take a negative number to walk backwards, because a list is doubly linked.

5. Sorting and reversing — member functions

Here is another list quirk: the free function std::sort from <algorithm> does NOT work on a list, because it needs random-access iterators that can jump. So the list provides its own member functions: l.sort() sorts in place, and l.reverse() flips the order. Both are efficient because they only re-link nodes — no values are copied around.

Code story: Four unsorted test scores sit in a list: 88, 72, 95, 64. We sort the list with its own member function sort() and print the result, then reverse the list and print again. Watch the second line come out as the first line backwards.

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

int main() {
    list<int> scores = {88, 72, 95, 64};

    scores.sort();   // member function — std::sort does not work on lists
    for (int s : scores) {
        cout << s << " ";
    }
    cout << endl;
    scores.reverse();
    for (int s : scores) {
        cout << s << " ";
    }
    return 0;
}

64 72 88 95
95 88 72 64

What just happened? scores.sort() rearranges the nodes into ascending order: 64, 72, 88, 95. Then scores.reverse() flips the chain, giving 95, 88, 72, 64. Both operations only change links, which is why they are cheap on a list and why the STL gives the list its own versions.

6. Splice — move, don't copy

The list has one trick no other container can match: splice. It moves whole nodes from one list into another by re-linking them — the values are never copied and no new memory is allocated. After the move, the source list simply has fewer nodes. This is the fastest way to combine two lists, and it is also why iterators to spliced elements stay valid: the nodes themselves never move in memory.

Code story: We have two small lists: a holds 1, 2, 3 and b holds 10, 20. One call to splice moves every node of b to the end of a. Then we print list a and ask for the size of b. Watch b become empty without a single copy.

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

int main() {
    list<int> a = {1, 2, 3};
    list<int> b = {10, 20};

    a.splice(a.end(), b);   // move all of b to the end of a

    for (int n : a) {
        cout << n << " ";
    }
    cout << endl;
    cout << "b size: " << b.size() << endl;
    return 0;
}

1 2 3 10 20
b size: 0

What just happened? a.splice(a.end(), b) takes every node of b and links it onto the end of a. List a now holds 1, 2, 3, 10, 20 and b is empty. You can also splice a single element or a range by giving iterators — the idea is the same: move the nodes, don't copy the values.

7. A list of words

Lists are not only for numbers. A std::list<std::string> is a natural fit for things that arrive in order and get edited in the middle — a playlist, a to-do list, or lines of a document. Everything you have learned works the same way: push_front, push_back, size(), the range-based loop, and the member sort() for alphabetical order.

Code story: We are building a small music playlist. It starts with two songs, and then we add one at the back and an intro at the front. Finally we print how many tracks there are and list each one on its own line. Watch the count match the list, and the intro sit at the very top.

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

int main() {
    list<string> playlist = {"Song A", "Song B"};
    playlist.push_back("Song C");
    playlist.push_front("Intro");

    cout << "Tracks: " << playlist.size() << endl;
    for (string song : playlist) {
        cout << "- " << song << endl;
    }
    return 0;
}

Tracks: 4
- Intro
- Song A
- Song B
- Song C

What just happened? The playlist starts with two songs and grows to four as songs are added at both ends — no size was ever declared, and no array bounds had to be guessed. The range-based loop visits the nodes in chain order, so the intro prints first. This pattern — build a list, then walk it — is the most common list pattern in real programs.

8. List vs vector — which one?

Now that you know both containers, here is the honest comparison. In practice, vectors win most of the time: their elements sit side by side, which is fast for the processor and lets you jump to any element instantly. Lists win when you insert and erase in the middle constantly, when you need elements to stay at the same address forever, or when you want to splice whole lists together.

Table 2 — Vector vs list

9. Common mistakes

Lists look like vectors at first glance, but the differences bite if you carry vector habits across. These five mistakes catch almost every beginner.

Table 3 — Common mistakes with lists