List in C++ STL

Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions. As compared to vector, list has slow traversal, but once a position has been found, insertion and deletion are quick. 

• List containers are implemented as doubly-linked lists
• For implementing a singly linked list, we use forward_list
• Advantage :
  • Compared to other base standard sequence containers (array, vector and deque), lists perform generally better in inserting, extracting and moving elements in any position within the container.
  • sorting algorithms uses list.
• Disadvantage :
  • The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position because it has non-contiguous memory allocation. For example, to access the 6th element in a list, one has to iterate from either the beginning or the end to that position, which takes linear time.
  • It also consumes some extra memory to keep the linking information associated to each element.

Functions used with List:

Iterators:
begin : Return iterator to beginning (public member function )
end : Return iterator to end (public member function )
rbegin : Return reverse iterator to reverse beginning (public member function )
rend : Return reverse iterator to reverse end (public member function )
cbegin : Return const_iterator to beginning (public member function )
cend : Return const_iterator to end (public member function )
crbegin : Return const_reverse_iterator to reverse beginning (public member function )
crend : Return const_reverse_iterator to reverse end (public member function )

Capacity:
empty : Test whether container is empty (public member function )
size : Return size (public member function )
max_size : Return maximum size (public member function )

Element access:
front : Access first element (public member function )
back : Access last element (public member function )

Modifiers:
assign : Assign new content to container (public member function )
emplace_front : Construct and insert element at beginning (public member function )
push_front : Insert element at beginning (public member function )
pop_front : Delete first element (public member function )
emplace_back : Construct and insert element at the end (public member function )
push_back : Add element at the end (public member function )
pop_back : Delete last element (public member function )
emplace : Construct and insert element (public member function )
insert : Insert elements (public member function )
erase : Erase elements (public member function )
swap : Swap content (public member function )
resize : Change size (public member function )
clear : Clear content (public member function )

Operations:
splice : Transfer elements from list to list (public member function )
remove : Remove elements with specific value (public member function )
remove_if : Remove elements fulfilling condition (public member function template )
unique : Remove duplicate values (public member function )
merge : Merge sorted lists (public member function )
sort : Sort elements in container (public member function )
reverse : Reverse the order of elements (public member function )

Observers:
get_allocator : Get allocator (public member function )

// program to show the working of some functions of List
#include <iostream>
#include <list>
#include <iterator>
using namespace std;

//function for printing the elements in a list
void showlist(list <int> lst)
{
	list <int> :: iterator it;
	for(it = lst.begin(); it != lst.end(); ++it)
		cout << '\t' << *it;
	cout << '\n';
}

int main()
{
	list <int> tsp_list1, tsp_list2;
	for (int i = 0; i < 10; ++i)
	{
		tsp_list1.push_back(i * 2);
		tsp_list2.push_front(i * 3);
	}
	cout << "\nList 1 (tsp_list1) is : ";
	showlist(tsp_list1);
	cout << "\nList 2 (tsp_list2) is : ";
	showlist(tsp_list2);
	cout << "\ntsp_list1.front() : " << tsp_list1.front();
	cout << "\ntsp_list1.back() : " << tsp_list1.back();
	cout << "\ntsp_list1.pop_front() : ";
	tsp_list1.pop_front();
	showlist(tsp_list1);
	cout << "\ntsp_list2.pop_back() : ";
	tsp_list2.pop_back();
	showlist(tsp_list2);
	cout << "\ntsp_list1.reverse() : ";
	tsp_list1.reverse();
	showlist(tsp_list1);
	cout << "\ntsp_list2.sort(): ";
	tsp_list2.sort();
	showlist(tsp_list2);
	return 0;
}

/*
Output : 
List 1 (tsp_list1) is :     0    2    4    6    
8    10    12    14    16    18

List 2 (tsp_list2) is :     27    24    21    18    
15    12    9    6    3    0

tsp_list1.front() : 0
tsp_list1.back() : 18
tsp_list1.pop_front() :     2    4    6    8    
10    12    14    16    18

tsp_list2.pop_back() :     27    24    21    18    
15    12    9    6    3

tsp_list1.reverse() :     18    16    14    12    
10    8    6    4    2

tsp_list2.sort():     3    6    9    12    
15    18    21    24    27
*/