std::list or doubly link list c++

List (doubly link list)

List comes under sequential container and it does not use continuous memory to store element, it is used when number of element are large in number and secondly insertion and deletion operation can be happened anywhere frequently.

Key points:

• It supports Bi-directional (like push_back() and push_front()).
• Good performance for insert and deletion at beginning and middle as well end (no need to move element).
• Does not support random access (Need to iterate from first element or last element).

Header filer: #include<list>

When we will use list:

• when we want to insert and delete element without moving existing element.
• when insert and deletion can be happened at anywhere (at beginning, middle or last).
• Number of element are very huge (that cannot be fit in continuous memory)

Disadvantage:

• list has information about predecessor and successor so it take more memory per element as compare to vector.
• Transverse is slower than vector (vector use continuous memory so directly jump to any element).
• No Random Access.

Source code of std::list with example:

/*
Program: STL list
Author: Alpha Master
Date: 15 September 2021
*/

//Header File
#include<iostream>
#include<list>

//Display function the show the content of list
void display(std::list<int>& lst)
{
    //using iterate to transverse the list and display the content
    std::list<int>::iterator itr;
    for(itr = lst.begin(); itr != lst.end(); itr++)
    {
        std::cout<<*itr<<" ";
    }
    std::cout<<std::endl;
}
int main()
{
    std::cout<<"STL List"<<std::endl;

   //Create empty list object
    std::list<int> lst;
    std::cout<<"size:"<<lst.size()<<std::endl;
 
    //Add element in vector at end 
    lst.push_back(1);
    lst.push_back(2);
    lst.push_back(3);
    lst.push_back(4);
    lst.push_back(5);
    std::cout<<"size:"<<lst.size()<<std::endl;
    
    //display content
    display(lst);

    //Add element at begining
    lst.push_front(11);
    lst.push_front(12);
    
    //display
    display(lst);

    return 0;
}

Output:

STL List
size:0
size:5
1 2 3 4 5 
12 11 1 2 3 4 5