13.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\0.
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 list<int>&);
int main () {
std::list<int> list = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
cout << "size: " << list.size();
cout << "\nfront: " << list.front();
cout << "\nback: " << list.back();
cout << "\n\npush_back 13: ";
list.push_back(13);
cout << "\nsize: " << list.size();
cout << "\nback() " << list.back();
print_list(list);
return 0;
}
void print_list(const std::list<int>& list) {
if (list.empty()) {
cout << "list is empty.\n";
} else {
cout << "list contains:\n";
}
for(const int i: list) {
cout << i << " ";
}
cout << "\n\n";
}
The defining operations of a std::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.
Note
empty() vs. size() == 0
In most containers, calling size() is constant time.
That is it takes the same amount of time regardless of the number items in the container.
Not so for lists.
There are situations where a list cannot determine the size without traversing the range and counting them.
In general, never assume size() is as efficient as empty().
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().
See Effective STL, for more details[1].
Underneath, the standard library list is not very different from the struct node above.
The primary characteristics are:
All data is stored on the heap
Node traversal is accomplished by following pointers from one node to the next
Access based on an index is not allowed. 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