14.1. The list class¶

The std::list is a sequence container that stores data in nodes. Each node in a list points to the next (and previous) node in the list. Each node is a separate object that exists to encapsulate a piece of data and to allow navigation to adjacent nodes.

A more compact way to graphically represent our doubly linked list is like this:

A linked list that stores a sequence of ints can be trivially implemented using a struct:

struct node {
   int value;
   node* next;
   node* prev;
};

The struct node contains a single value it 'owns', plus pointers to adjacent nodes.

Creating a linked list from such a 'home grown' struct is not complicated, but it isn't pretty either:

// create an empty list
node* head = new node;
node* tail = new node;
head->next = tail;
tail->prev = head;

// insert node a into the list
node* a = new node;
a->value = 61;
a->next = tail;
a->prev = head;
head->next = a;
tail->prev = a;

// insert node b after node a
node* b = new node;
b->value = 62;
b->next = tail;
b->prev = a;
a->next = b;
tail->prev = b;

At this point, we have created the basic structure shown in the first list diagram. Once we have such a list, we can access all of the elements, if we have a pointer to any one of them. For example, to print all of the elements, we could:

node* p = head->next;
while (p->next != nullptr) {
  std::cout << p->value << ' ';
  p = p->next;
}

Which, given the list we created, will print 61 62 and a trailing space.

Obviously, no one would want to use such a list. Every trivial detail needs to be managed, and any program using it would be more likely to leak memory or fail suddenly due to some programming error.

The std::list class hides all the implementation details and provides a list with many convenient features:

#include <iostream>
#include <list>
using std::cout;

void print_list(const std::list<int>&);

int main () {
  std::list<int> values = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
  cout << "size: "  << values.size()
       << "\nfront: " << values.front()
       << "\nback: "  << values.back();

  cout << "\n\npush_back 13: ";
  values.push_back(13);
  cout << "\nsize: "  << values.size()
       << "\nback() " << values.back();

  print_list(list);
}

void print_list(const std::list<int>& values) {
  if (values.empty()) {
    cout << "list is empty.\n";
  } else {
    cout << "list contains:\n";
  }
  for(const int i: values) {
    cout << i << ' ';
  }
  cout << "\n\n";
}

The defining operations of a list are:

push_back: Add a new element to the end of the list.
pop_back: Remove an element from the end of the list.
back: Get the value of the element at the end of the list.
push_front: Add a new element to the beginning of the list.
pop_front: Remove an element from the beginning of the list.
front: Get the value of the element at the beginning of the list.
insert: Insert elements at a specified position in the list.
erase: Remove elements at a specified position in the list.
splice: Transfer elements from one list to another. Lists can do this without copying or moving any elements.

Operations like insert, erase, and splice are central to why std::list exists.

C++11 Feature

Checking empty() vs. checking size() == 0

Perfer writing code that expresses intent.

If you really want to know if a container is empty (or not), then call empty().

If you really want to know the number of elements in a container, then call size().

Underneath, the standard library list is not very different from the struct node above. Typical characteristics are:

Node storage on the heap (free store).
Node traversal is accomplished by following pointers from one node to the next
Access based on an index is not allowed. std::list does not implement operator[] or at() functions. This kind of access, called random access describes the ability to compute a location in memory using a starting address and an offset. Arrays and vectors support random access. Linked lists do not.

More to Explore