inked lists are perhaps the most widely used data structure. Yet writing a linked list from scratch is an arduous task. In a previous 10-Minute Solution, you learned how to implement a linked list from scratch. A DIY solution may be useful for students and hackers who wish to study the internals of this data structure. However, in real-world production systems, using homemade lists is rarely a good idea. For starters, expensive time is wasted in debugging and optimizing them. Secondly, every programmer introduces individual variations and improvisations that turn into a maintenance nightmare. Finally, homemade solutions don’t support generic programming very well. Often, they are confined to a single datatype.



How do you avoid the unnecessary drudgery of writing a linked list from scratch while benefiting from a generic, efficient and portable list data structure?



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 or MFC list class.Step 1: Creating a List Object
The header contains the declaration of std::list and its specialized algorithms. Our first step is to create an empty list of integers called li:

#include using std::list;int main(){ list  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();

The push_front() member function 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, 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

Step 2: Dealing with Sequences
Up until now I have exemplified list operations that operate on a single element at a time. list supports sequence operations as well. These operations enable you to traverse, fill, sort and reverse a list. 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 use a const_iterator instead of a plain iterator because the iteration process in this case doesn’t modify the list:

list::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 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  x;//..fill xli.merge(x); // merge the elements of x into li

merge() merges x into li. x is empty after the merge operations. To erase one or more elements, use the erase() member function. This function has two overloaded versions. The first version 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 we have a list of 10 elements and we want to remove all the elements but the first two. We use erase() as follows:

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

Step 3: Supporting 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 #include “Date.h”list ls;list  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 (read more on overloading binary operators here):

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}