The container std::list<T> represents a linked list in memory. Schematically, it looks like this:

Notice that each node in the list contains pointers to its "next" and "previous" nodes, so this is a doubly linked list. The benefit of a doubly linked list is that its iterators can move both forwards and backwards through the list--that is, std::list<T>::iterator is a bidirectional iterator (but it is not random-access; getting to the nth element of the list still requires O(n) time).

std::list supports many of the same operations as std::vector, except for those operations that require random access (such as operator[]). It can afford to add member functions for pushing and popping from the front of the list, since pushing and popping from a list doesn't require expensive move operations.

In general...