List in C++ (STL)

In this article we will discuss std::list usage details.

What is std::list ?

std::list is sequential STL container that is internally implemented as doubly linked list.
i.e. every element in the list is stored at a seperate memory location i.e. called node and it also contains a pointer to the previous and next node.

Vector vs List

Creating a std::list of int and pushing elements in front and back

std::list<int> listOfNumbers;

//Inserting elements at end in list
listOfNumbers.push_back(5);
listOfNumbers.push_back(6);

//Inserting elements at front in list
listOfNumbers.push_front(2);
listOfNumbers.push_front(1);

List Contents are now,
1 2 5 6

Different ways to Initialise a List

Inserting elements in the std::list

std::list has several overloaded member function insert() to insert the elements in between the list. One is,

insert(iterator_position,elem)

It allocates a new node and copy the passed element to it and then inserts that node before iterator position iterator_position and returns the position of the newly added element.

It has several other overloaded implementations i.e.



    insert(iterator_position,other_list_begin,other_list_end)
    

    etc.

    Now lets insert an element at 3rd position in the list.

    //Inserting elements in between the list using
    // insert(pos,elem) member function. Let's iterate to
    // 3rd position
    it = listOfNumbers.begin();
    it++;
    it++;
    // Iterator 'it' is at 3rd position.
    listOfNumbers.insert(it, 4);
    
    

    Now List contents will be,
    1 2 4 5 6

    C++ : How to get element by index in List

    How to search an element in std::list ?

    Iterating over a std::list of elements and display them

    // Iterating over list elements and display them
    it = listOfNumbers.begin();
    while(it != listOfNumbers.end())
    {
    	std::cout<<(*it)<<"  ";
    	it++;
    }
    std::cout<<std::endl;
    
    

    Different Ways to iterate over a std::list of objects

    Erasing elements from std::list

    std::list has two overloaded member function erase() to erase the elements in between the list. These are,

    erase(iterator_position,elem)
    

    It erases the element at the passed node and chane the left and right pointers of previous and next nodes. Also returns iterator of next node element. This opeartion takes O(1) time, as only swapping of pointers is required not like vector and deque, where other elements need to be shifted.

    It has an other overloaded implementations i.e.

    erase(other_list_begin,other_list_end)
    

    It erases the elements in given range.

    Now lets erase an element at 3rd position in the list.

    //Erasing elements in between the list using
    // erase(position) member function. Let's iterate to
    // 3rd position
    it = listOfNumbers.begin();
    it++;
    it++;
    // Iterator 'it' is at 3rd position. Now erase this element.
    listOfNumbers.erase(it);
    

    Now List contents will be,
    1 2 5 6

    Erase elements from a List using iterators

    Remove Elements from std::list while Iterating

     

    Removing elements from a std::list based on some condition

    ::remove(value) member function of std::list removes all the elements whose value is equivalent to passed value.
    ::remove_if(predicate) member function of std::list removes all the elements for which predicate(element) returns true.

    Lets remove all elements with value greater than 3.

    //Lets remove all elements with value greater than 3.
    listOfNumbers.remove_if([](int elem)
    	{
    		if(elem > 3)
    			return true;
    		else
    			return false;
    	});
    

    Now List contents will be,
    1 2

    Remove elements from std::list based on External Criterion

    Complete executable code is as follows,

    #include <iostream>
    #include <list>
    #include <iterator>
    
    
    int main()
    {
    	std::list<int> listOfNumbers;
    
    	//Inserting elements at end in list
    	listOfNumbers.push_back(5);
    	listOfNumbers.push_back(6);
    
    	//Inserting elements at front in list
    	listOfNumbers.push_front(2);
    	listOfNumbers.push_front(1);
    
    	// Iterating over list elements and display them
    	std::list<int>::iterator it = listOfNumbers.begin();
    	while(it != listOfNumbers.end())
    	{
    		std::cout<<(*it)<<"  ";
    		it++;
    	}
    	std::cout<<std::endl;
    
    
    	//Inserting elements in between the list using
    	// insert(pos,elem) member function. Let's iterate to
    	// 3rd position
    	it = listOfNumbers.begin();
    	it++;
    	it++;
    	// Iterator 'it' is at 3rd position.
    	listOfNumbers.insert(it, 4);
    
    
    	// Iterating over list elements and display them
    	it = listOfNumbers.begin();
    	while(it != listOfNumbers.end())
    	{
    		std::cout<<(*it)<<"  ";
    		it++;
    	}
    	std::cout<<std::endl;
    
    
    	//Erasing elements in between the list using
    	// erase(position) member function. Let's iterate to
    	// 3rd position
    	it = listOfNumbers.begin();
    	it++;
    	it++;
    	// Iterator 'it' is at 3rd position. Now erase this element.
    	listOfNumbers.erase(it);
    
    
    	// Iterating over list elements and display them
    	it = listOfNumbers.begin();
    	while(it != listOfNumbers.end())
    	{
    		std::cout<<(*it)<<"  ";
    		it++;
    	}
    	std::cout<<std::endl; 
    //Lets remove all elements with value greater than 3. 
    listOfNumbers.remove_if([](int elem) { if(elem > 3)
    					return true;
    				else
    					return false;
    			});
    
    	it = listOfNumbers.begin();
    	while(it != listOfNumbers.end())
    	{
    		std::cout<<(*it)<<"  ";
    		it++;
    	}
    	std::cout<<std::endl;
    
    	return 0;
    }
    
    Scroll to Top