Topic 56 of 91 9. C++ Standard Template Library (STL) Interactive Tutorial

std::list in C++: Doubly Linked Storage and List Operations

7 mins read Last updated: 26 Sep 2026 15,672 views

On This Page0 sectionsQuick jump to subtopic

Direct Answer & Core Concept

std::list is a sequence container implemented as a doubly linked list. Each node contains a data element and two pointers (prev and next). It allows $O(1)$ constant time insertion and deletion at any position once an iterator is obtained, with no reallocation or iterator invalidation.

Detailed Explanation & Mechanics

1. Doubly Linked Node Structure:

Architecture Diagram

┌──────────────┐     ┌──────────────┐     ┌──────────────┐
│ [prev|10|next]│◄───►│ [prev|20|next]│◄───►│ [prev|30|next]│
└──────────────┘     └──────────────┘     └──────────────┘

2. Dedicated List Algorithms:

std::list provides member algorithms like .sort(), .splice(), .merge(), and .reverse() because standard algorithms requiring random-access iterators (like std::sort) cannot operate on linked lists.

Runnable Code Example: std::list in C++: Doubly Linked Storage

C++20 / C++23

main.cpp

Run Online

#include <iostream>
#include <list>

int main() {
    std::list<int> taskQueue = {101, 102, 105};

    // Insert at front and back in O(1)
    taskQueue.push_front(100);
    taskQueue.push_back(106);

    // Insert in the middle without moving other elements
    auto it = taskQueue.begin();
    std::advance(it, 3); // Move to 105
    taskQueue.insert(it, 103);

    std::cout << "Task Queue: ";
    for (int t : taskQueue) std::cout << t << " ";
    std::cout << "\n";

    // Fast O(1) node splicing
    std::list<int> urgentTasks = {999};
    taskQueue.splice(taskQueue.begin(), urgentTasks);

    std::cout << "After Splicing Urgent Task: ";
    for (int t : taskQueue) std::cout << t << " ";
    std::cout << "\n";
    return 0;
}

Common C++ Technical Interview Questions & Answers

Interview Prep

Q: Does inserting or deleting an element in `std::list` invalidate other iterators?

A: No. Iterators and references to other elements remain valid because nodes are allocated individually on the heap and do not move in memory.

Q: Why doesn't `std::sort(list.begin(), list.end())` work on `std::list`?

A: `std::sort` requires RandomAccessIterator, whereas `std::list` only provides BidirectionalIterator. Use `list.sort()` instead.

Key Takeaways, Modern Best Practices & Idioms

C++ Best Practices & Production Rules

• Use std::list when frequent insertions and deletions occur in arbitrary positions and iterators must remain valid.
• Use .splice() to transfer elements between lists in $O(1)$ without copying or memory reallocations.
• Do not use std::list for small primitive elements where cache-friendly std::vector outperforms it.

Previous Topicstd::map in C++: Ordered Key-Value Storage and Member Functions

Next Topicstd::queue in C++: FIFO Data Processing and Available Methods