What is STL List in C++?

A list is a sequence container in the Standard Template Library (STL) that stores elements as a doubly linked list.

Each element (called a node) contains the actual data, a pointer to the previous node, and a pointer to the next node. Unlike a vector, the elements of a list are not stored in contiguous memory.

Think of a list as a train. Each train coach is connected to the coach before and after it. You can easily attach or detach coaches without moving the others.

Why does STL List exist?

Vectors are excellent for fast random access but are inefficient when inserting or deleting elements in the middle because all subsequent elements must be shifted.

• Fast insertion
• Fast deletion
• Efficient splicing of elements
• Stable iterators after insertions and deletions (except for erased elements)

Real-world use cases

• Music playlists
• Browser history
• Undo/redo functionality
• Task scheduling
• Process management
• Navigation systems
• Text editors
• Recently used file lists

Prerequisites

• Variables and data types
• Arrays
• Loops
• Functions
• Templates
• Basic STL containers such as vector

Including the header

#include <list>

Creating a list

list<data_type> list_name;

// Example:
list<int> numbers;

Initializing a list

• list<int> l; – empty list
• list<int> l(5); – five elements initialized to 0
• list<int> l(5, 10); – five elements initialized to 10
• list<int> l = {1,2,3}; – initialize using a list

Characteristics of STL List

• Memory layout: non-contiguous
• Random access: not supported
• Fast insertion: yes
• Fast deletion: yes
• Front insertion: O(1)
• Back insertion: O(1)
• Middle insertion: O(1) (with iterator)

Common list operations

• push_back() – add element at the end
• push_front() – add element at the beginning
• pop_back() – remove last element
• pop_front() – remove first element
• insert() – insert element
• erase() – remove element
• remove() – remove all matching values
• sort() – sort the list
• reverse() – reverse the list
• merge() – merge sorted lists
• splice() – move elements between lists
• size() – number of elements
• clear() – remove all elements

How lists work

Each node contains a pointer to the previous node, the data, and a pointer to the next node.

Unlike vectors, there is no shifting of elements during insertion, no contiguous memory allocation, and access to elements requires traversing the list.

Iterating through a list

for (int value : numbers)
{
    cout << value << " ";
}

// You can also use iterators.

Example 1: Creating and displaying a list

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

int main()
{
    list<int> numbers;

    numbers.push_back(10);
    numbers.push_back(20);
    numbers.push_back(30);

    for (int num : numbers)
    {
        cout << num << " ";
    }

    return 0;
}

// Output: 10 20 30

Example 2: Using push_front() and push_back()

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

int main()
{
    list<int> values;

    values.push_front(20);
    values.push_front(10);
    values.push_back(30);
    values.push_back(40);

    for (int value : values)
    {
        cout << value << " ";
    }

    return 0;
}

// Output: 10 20 30 40

Example 3: Inserting and erasing elements

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

int main()
{
    list<int> numbers = {1, 2, 4, 5};

    auto it = numbers.begin();
    advance(it, 2);

    numbers.insert(it, 3);

    it = numbers.begin();
    advance(it, 1);

    numbers.erase(it);

    for (int value : numbers)
    {
        cout << value << " ";
    }

    return 0;
}

// Output: 1 3 4 5

Example 4: Sorting and reversing a list

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

int main()
{
    list<int> numbers = {40, 10, 30, 20};

    numbers.sort();

    numbers.reverse();

    for (int value : numbers)
    {
        cout << value << " ";
    }

    return 0;
}

// Output: 40 30 20 10

Example 5: Music playlist

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

int main()
{
    list<string> playlist;

    playlist.push_back("Song A");
    playlist.push_back("Song B");
    playlist.push_back("Song C");

    playlist.push_front("Intro");

    cout << "Playlist:\n";

    for (const string& song : playlist)
    {
        cout << song << endl;
    }

    return 0;
}

Common mistakes and pitfalls

• Using list[index]. Fix: use iterators or range-based loops
• Choosing a list for frequent random access. Fix: use std::vector instead
• Forgetting that elements are non-contiguous. Fix: understand that pointer arithmetic is not possible
• Calling sort() from <algorithm>. Fix: use the member function list.sort()
• Using std::advance() repeatedly in large lists. Fix: keep iterators when possible to avoid repeated traversal

Best practices

• Use lists when frequent insertions and deletions occur
• Prefer vectors when random access is required
• Use range-based for loops for readability
• Pass large lists by const reference to functions
• Use member functions like sort(), merge(), and splice() instead of generic algorithms where applicable
• Minimize unnecessary traversals of the list

When not to use this

• Fast random access is required (std::vector is better)
• Memory efficiency is important (lists have pointer overhead)
• Most operations involve reading rather than inserting or deleting
• CPU cache performance matters, since list nodes are not stored contiguously
• The collection size is small and insertions are infrequent

Summary

• STL List in C++ is implemented as a doubly linked list
• Elements are stored in non-contiguous memory
• Lists provide fast insertion and deletion at any position when you already have an iterator
• Random access using indexes is not supported
• Common operations include push_back(), push_front(), insert(), erase(), remove(), sort(), reverse(), merge(), and splice()
• Use std::list when frequent modifications are more important than random access
• Prefer std::vector for most general-purpose sequence storage

Frequently asked questions

What is the difference between a vector and a list?

A vector stores elements in contiguous memory and supports fast random access. A list stores elements as a doubly linked list, providing efficient insertions and deletions but no direct index-based access.

Can I access list elements using an index?

No. std::list does not support the [] operator. Use iterators or range-based loops to traverse the list.

Why does std::list have its own sort() function?

Since list elements are not stored contiguously, generic algorithms like std::sort() cannot be used. std::list::sort() is specifically designed for linked lists.

What is the time complexity of inserting into a list?

Insertion is O(1) when you already have an iterator pointing to the insertion position. Finding that position, however, may take O(n).

When should I use std::list instead of std::vector?

Use std::list when your application performs frequent insertions and deletions in the middle of the container. For most other cases, especially when random access and cache efficiency matter, std::vector is usually the better choice.