List in STL | C++

Array and Vector are contiguous containers, i.e they store their data on continuous memory, thus the insert operation at the middle of vector/array is very costly (in terms of number of operation and process time) because we have to shift all the elements, linked list overcome this problem. Linked list can be implemented by using the list container. List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept internally by the association to each element of a link to the element preceding it and a link to the element following it.

They are very similar to forward_list: The main difference being that forward_list objects are single-linked lists, and thus they can only be iterated forwards, in exchange for being somewhat smaller and more efficient.

Syntax

// Created list of Integer
std::list<int> l;

// Lists with entries
std::list<int> l{1,2,3};

Member Functions

• insert
  This method, as the name suggests, inserts an element at specific position, in a list. There are 3 variations of insert(), they are as follows
  1. insert(iterator, element) : inserts element in the list before the position pointed by the iterator.
  2. insert(iterator, count, element) : inserts element in the list before the position pointed by the iterator, count number of times.
  3. insert(iterator, start_iterator, end_iterator): insert the element pointed by start_iterator to the element pointed by end_iterator before the position pointed by iterator
• void push_back (const value_type& val);
  void push_back (value_type&& val);
  Adds a new element at the end of the list container, after its current last element. The content of val is copied (or moved) to the new element.
• void push_front (const value_type& val);
  void push_front (value_type&& val);
  Inserts a new element at the beginning of the list, right before its current first element. The content of val is copied (or moved) to the inserted element.
• void pop_back();
  Removes the last element in the list container, effectively reducing the container size by one.
• void pop_front();
  Removes the first element in the list container, effectively reducing its size by one.
• bool empty() const noexcept;
  Returns whether the list container is empty (i.e. whether its size is 0).
• size_type size() const noexcept;
  Returns the number of elements in the list container.
• reference front();
  const_reference front() const;
  Returns a reference to the first element in the list container.
• reference back();
  const_reference back() const;
  Returns a reference to the last element in the list container.
• void reverse() noexcept;
  Reverses the order of the elements in the list container.
• void sort();
  template <class Compare>
  void sort (Compare comp);
  Sorts the elements in the list, altering their position within the container.

Example

#include <iostream>
#include <list>

using namespace std;

// Comparison based on length
bool compare (const std::string& first, const std::string& second)
{
  return (first.length() < second.length());
}

int main()
{
  list<int> l = {1,2,3,4,5};
  list<int>::iterator it = l.begin();           
  
  // insert 100 before 2 position, now the list is 1 100 2 3 4 5
  l.insert (it+1, 100);    
  
  list<int> new_l = {10,20,30,40};   // new list

  // insert elements from beginning of list l to end of list l before 1 position in list new_l
  // now the list new_l is 1 100 2 3 4 5 10 20 30 40  
  new_l.insert (new_l.begin(), l.begin(), l.end());
  
  l.push_back(6);
  
  // Delete element from back and front of the list
  l.pop_back();  
  l.pop_front();
  
  // Front equals back
  l.front() = l.back();
  
  // Reverse the list
  l.reverse();
  
  // Sort the list
  l.sort();

  // Sort the list based on the function
  l.sort(compare);
   
  return 0;
}