Last updated May 7, 2003.

Linked lists are another widely-used data structure. Yet writing a linked list from scratch is an arduous, frustrating and time-consuming task. Instead of reinventing the wheel every time anew, use the STL std::list container class. Its uniform interface, generic nature and seamless integration with other STL constructs make it a superior choice to any homemade list class, as I will show in the following sections.

Creating a list object

The header <list> contains the declaration of std::list and its specialized algorithms. Our first step is to create an empty list of integers called li:

#include <list>
using std::list;
int main()
{
 list <int> li;
}

To insert a single element, use the push_back() member function:

li.push_back(1);

To remove the last element of a list, use the pop_back() member function

li.pop_back();

As opposed to push_back(), push_front() inserts an element before the list’s beginning:

li.push_front(0); // the first element is now 0, not 1

Similarly, pop_front() removes the first element of a list:

li.pop_front();

To remove a certain value from the list without indicating its exact position, use remove(). remove(n) removes all the elements that equal to n from the list:

li.remove(0); // li doesn't contain 
       //any zeros anymore

Dealing with Sequences

Up until now I have exemplified list operations that operate on a single element at a time. std::list supports sequence operations as well. These operations enable you to traverse, fill, sort and reverse multiple elements at once.

Iteration is easy. The begin() and end() member functions return iterators pointing at the list’s beginning and end, respectively. Use them to access all the list’s elements sequentially. Note that we’re using a const_iterator instead of an ordinary iterator object because the iteration process in this case doesn’t modify the list’s state:

list<int>::const_iterator it;
for(it=li.begin(); it!=li.end(); ++it)
{
 cout << *it << endl; // each element on a separate line
} 

The assign() member function fills a list with the contents of another sequence such as a vector or an array. It takes two input iterators (for further information on iterator categories, see the resources below) that mark the sequence’s beginning and end, respectively. In the following example, we fill a list with the elements of an array:

int arr[3] = {10,20,30};
li.assign( &arr[0], &arr[3]);

You can merge two lists into one. The merge() member function takes a reference to another list object:

list <int> x;
//..fill x
li.merge(x); // merge the elements of x into li

merge() merges x into li. x becomes empty after the merge operations. To erase one or more elements, use the erase() member function. This function has two overloaded versions; the first of which takes an iterator and erases the element to which it points. The second version takes two iterators that mark the beginning and the end of the sequence to be erased. Suppose you have a list of 10 elements and you want to remove all the elements but the first two. Use erase() as follows:

list<int>::it=li.begin();
++it; ++it; // advance to third element
li.erase(it, li.end()); // erase elements 3 – 10

Support for User-Defined Types

The generic nature of list enables you to define specializations, or instances, of user-defined types. For example, you may create lists of strings and Date objects like this:

#include <string>
#include "Date.h"
list<std::string> ls;
list <Date> ld;

Operations that require element comparison such as sort() and unique() use the overloaded < operator. If you intend to use any of these algorithms with lists, define a matching overloaded version of this operator for your class first:

bool operator < (const Date& d1, const Date& d2);
ld.sort(); // OK, using overloaded < operator

Note that in general, sorting a list is less efficient than sorting a vector or a queue. Therefore, if you need to sort elements frequently, you probably shouldn’t use a list in the first place. The same is true for reverse(), which is also supported:

ld.reverse();
for(it=ld.begin(); it!=ld.end(); ++it)
{
 cout << *it << endl; // descending order
}