C++ STL: list (Complete Guide)

List in STL is another storage container that allows us to store data sequentially. It helps in efficiently inserting and deleting elements bidirectionally. It is implemented as linear doubly LinkedList in memory. Unlike vectors, they allow non-contiguous memory allocation. Lists are included in #include <list> header file.

List Declaration

Syntax:

list<data_type> name{initial_values};

data_type: data type of the elements to be stored in the list

initial_values: optional parameter which initializes the list with the given values

Example:

list < int > l; //initializes a list of size 0 which stores integer values 
list < int > l { 1, 2, 3 } //initializes a list with values 1,2,3

Functions on lists

• push_back(element): It pushes the value at the end of the list.
  Time Complexity: O(1) 
  Parameters: the element which is to be inserted
  Return type: void
   
• push_front(element): It adds a new element to the front of the list.
  Time Complexity: O(1) 
  Parameters: the element which is to be inserted
  Return type: void
   
• pop_back(): It deletes the last element of the list.
  Time Complexity: O(1) 
  Parameters: None
  Return type: void
   
• pop_front(): It deletes the first element of the list.
  Time Complexity: O(1) 
  Parameters: None
  Return type: void
   
• front(): It returns the first element of the list.
  Parameters: None
  Return type: the first element of the list
   
• back(): It returns the last element of the list.
  Parameters: None
  Return type: last element of the list
   
• begin(): It returns an iterator pointing to the first element of the list.
  Parameters: None
  Return type: iterator
   
• end(): It returns an iterator pointing to the last element of the list.
  Parameters: None
  Return type: iterator
   
• clear(): It deletes all the elements from the list.
  Parameters: None
  Return type: void
   
• empty(): It tells us whether the list is empty or not.
  Parameters: None
  Return type: boolean, true if the list is empty else false
   
• reverse(): It reverses the list.
  Parameters: None
  Return type: void
   
• merge(list_name): It merges two sorted lists.
  Parameters: list_name to be merged
  Return type: None

#include<iostream>
#include<list>
using namespace std;

void print(list < int > l) {
  list < int > ::iterator itr;
  for (itr = l.begin(); itr != l.end(); ++itr)
    cout << * itr << ' ';
  cout << '\n';
}

int main() {
  list < int > l;
  for (int i = 0; i < 5; ++i) {
    l.push_back(i);
  }
  print(l);
  cout << "First element " << l.front() << '\n';
  cout << "Last element " << l.back() << '\n';
  l.pop_front();
  print(l);
  l.pop_back();
  print(l);
  return 0;
}

Output

0 1 2 3 4 
First element 0
Last element 4
1 2 3 4 
1 2 3 

Copying one list to another

list < int > list2 = list1; //copies list1 into list2	

Any change in list2 will not affect list1. The time complexity of this operation is O(N) where N is the size of the list1. The same can be done using reference but it will not create a copy, it will contain a reference to the original list.

list < int > & list2 = list1; //list2 references list1

Inserting elements into a list

The insert() function is used to add elements at any position in a list.

Syntax:

insert(pos, no_of_elements, element);

where,

pos: Iterator pointing to the position where the element is to be inserted.

no_of_elements: Number of elements to insert. Default is 1.

element: The element which is to be inserted. 

list < int > ::iterator it = l.begin();
l.insert(it, 5); // inserts 5 at 1st position

Deleting elements from the list

The erase() function is used to delete a single element or a range of elements from a list. 

Syntax:

listName.erase(iterator pos) //to delete a single element

listName.erase(iterator first, iterator last) // to delete a range of elements

where,

pos: Iterator pointing to the position of the element to be deleted.

first: Iterator pointing to the position of the first element in the range to be deleted.

last: Iterator pointing to the position of the last element in the range to be deleted. The last element doesn't get deleted.

list < int > ::iterator itr = l.begin();
l.erase(itr);
itr1 = demoList.begin();
itr2 = demoList.begin();
itr2++;
l.erase(itr1, itr2);