📖 本文目录

1. 📚 引言：为什么需要 list？

在 C++ 标准模板库（STL）中，list 是一种非常重要的序列式容器。与 vector 的动态数组不同，list 的底层实现是带头结点的双向循环链表。这意味着，如果你需要在序列的任意位置频繁进行插入和删除操作，list 将是你的不二之选。

🎯 本节目标

  1. 掌握 list 的介绍及使用
  2. 深入剖析 list 的底层原理及模拟实现
  3. 对比 list 与 vector，理解各自的应用场景

2. 🧐 list 的介绍

list 是 C++ STL 中一个非常灵活的容器，它的设计哲学是在常数时间内完成任意位置的插入和删除。
在这里插入图片描述

2.1 list 的核心特性

  1. 序列式容器：list 是一个序列式容器，元素按线性顺序存储。
  2. 双向迭代：list 支持前后双向迭代，这意味着你可以从容器的任意一端开始遍历。
  3. 底层结构：list 的底层是双向链表结构。每个元素（节点）都存储在互不相关的独立内存块中，节点之间通过指针（prev 和 next）连接。
  4. 与 forward_list 的区别：forward_list 是 C++11 引入的单链表，它更简单、更高效，但只能向前迭代。list 则提供了双向迭代的能力。
  5. 插入/删除效率高：与 array、vector、deque 等序列式容器相比，list 在任意位置进行插入和移除元素的执行效率更高（时间复杂度为 O(1)）。
  6. 主要缺陷：
    • 不支持随机访问：要访问 list 的第 6 个元素，你必须从已知的位置（比如头部或尾部）开始，沿着链表指针逐个遍历，时间复杂度为 O(N)。
    • 额外内存开销：每个节点除了存储数据外，还需要存储两个指针（指向前一个和后一个节点），这会带来额外的内存开销。

2.2 list 的构造函数

list 提供了多种构造函数，方便你以不同的方式初始化容器。

构造函数 接口说明
list() 构造一个空的 list
list(size_type n, const value_type& val = value_type()) 构造一个包含 n 个值为 val 的元素的 list
list(const list& x) 拷贝构造函数，构造一个与 x 相同的 list
list(InputIterator first, InputIterator last) 用 [first, last) 区间中的元素构造 list

3. 🛠️ list 的使用详解

掌握 list 的常用接口是高效编程的基础。下面我们将逐一介绍其核心功能。

3.1 list 的构造与遍历

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

int main() {
    // 1. 构造空的 list
    list<int> l1;
    cout << "l1 size: " << l1.size() << endl; // 输出: 0

    // 2. 构造包含 5 个值为 10 的元素的 list
    list<int> l2(5, 10);
    cout << "l2: ";
    for (auto e : l2) {
        cout << e << " "; // 输出: 10 10 10 10 10
    }
    cout << endl;

    // 3. 使用迭代器区间构造
    int array[] = {1, 2, 3, 4, 5};
    list<int> l3(array, array + sizeof(array) / sizeof(array[0]));
    cout << "l3: ";
    for (auto it = l3.begin(); it != l3.end(); ++it) {
        cout << *it << " "; // 输出: 1 2 3 4 5
    }
    cout << endl;

    // 4. 拷贝构造
    list<int> l4(l3);
    cout << "l4 (copy of l3): ";
    for (auto e : l4) {
        cout << e << " "; // 输出: 1 2 3 4 5
    }
    cout << endl;

    return 0;
}

3.2 list 的迭代器

迭代器可以暂时理解为一个指向容器中某个元素的指针。list 的迭代器是双向迭代器。

函数声明 接口说明
begin() / end() 返回第一个元素的迭代器 / 返回最后一个元素下一个位置的迭代器
rbegin() / rend() 返回第一个元素的 reverse_iterator，即 end 位置 / 返回最后一个元素下一个位置的 reverse_iterator，即 begin 位置

在这里插入图片描述

💡 注意：

  • begin 与 end 是正向迭代器，对迭代器执行 ++ 操作，迭代器向后移动。
  • rbegin 与 rend 是反向迭代器，对迭代器执行 ++ 操作，迭代器向前移动。
#include <iostream>
#include <list>
using namespace std;

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

    // 正向迭代器遍历
    cout << "正向遍历: ";
    for (auto it = lt.begin(); it != lt.end(); ++it) {
        cout << *it << " "; // 输出: 1 2 3 4 5
    }
    cout << endl;

    // 反向迭代器遍历
    cout << "反向遍历: ";
    for (auto rit = lt.rbegin(); rit != lt.rend(); ++rit) {
        cout << *rit << " "; // 输出: 5 4 3 2 1
    }
    cout << endl;

    return 0;
}

3.3 list 的容量操作

函数声明 接口说明
empty() 检测 list 是否为空，是返回 true，否则返回 false
size() 返回 list 中有效节点的个数

3.4 list 的元素访问

函数声明 接口说明
front() 返回 list 的第一个节点中值的引用
back() 返回 list 的最后一个节点中值的引用

3.5 list 的修改操作

list 的强大之处在于其高效的修改操作。

函数声明 接口说明
push_front(val) 在 list 首元素前插入值为 val 的元素
pop_front() 删除 list 中第一个元素
push_back(val) 在 list 尾部插入值为 val 的元素
pop_back() 删除 list 中最后一个元素
insert(position, val) 在 list 的 position 位置插入值为 val 的元素
erase(position) 删除 list 中 position 位置的元素
swap(list& x) 交换两个 list 中的元素
clear() 清空 list 中的有效元素 
#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> lt;

    // 尾部插入
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    cout << "after push_back: ";
    for (auto e : lt) cout << e << " "; // 输出: 1 2 3
    cout << endl;

    // 头部插入
    lt.push_front(0);
    cout << "after push_front: ";
    for (auto e : lt) cout << e << " "; // 输出: 0 1 2 3
    cout << endl;

    // 在第二个位置插入 10
    auto it = lt.begin();
    ++it; // 指向第二个元素
    lt.insert(it, 10);
    cout << "after insert: ";
    for (auto e : lt) cout << e << " "; // 输出: 0 10 1 2 3
    cout << endl;

    // 删除第二个元素
    it = lt.begin();
    ++it; // 指向 10
    lt.erase(it);
    cout << "after erase: ";
    for (auto e : lt) cout << e << " "; // 输出: 0 1 2 3
    cout << endl;

    // 头部删除
    lt.pop_front();
    cout << "after pop_front: ";
    for (auto e : lt) cout << e << " "; // 输出: 1 2 3
    cout << endl;

    // 尾部删除
    lt.pop_back();
    cout << "after pop_back: ";
    for (auto e : lt) cout << e << " "; // 输出: 1 2
    cout << endl;

    return 0;
}

3.6 list 的迭代器失效

⚠️ 核心概念： 迭代器失效是指迭代器所指向的节点变得无效，通常是因为该节点被删除了。

  • 插入操作：在 list 中进行插入操作时，不会导致迭代器失效。因为插入只是创建新节点并调整指针，不会影响已有节点的内存地址。
  • 删除操作：只有在删除操作时才会导致迭代器失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不受影响。

❌ 错误示例：

void TestListIterator1() {
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));

    auto it = l.begin();
    while (it != l.end()) {
        // 错误！erase() 执行后，it 所指向的节点已被删除，it 失效。
        // 对失效的迭代器执行 ++it 是未定义行为。
        l.erase(it);
        ++it;
    }
}

✅ 正确示例：

void TestListIterator() {
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));

    auto it = l.begin();
    while (it != l.end()) {
        // 正确做法：利用 erase 的返回值获取下一个有效迭代器
        // 或者使用 it = l.erase(it);
        it = l.erase(it);
    }
}

4. 🧬 list 的模拟实现

理解 list 的底层原理，最好的方式就是自己动手实现一个简化版本。

4.1 节点结构设计

list 的底层是双向链表，因此我们首先需要定义节点结构。

template<class T>
struct ListNode {
    ListNode<T>* _next; // 指向下一个节点
    ListNode<T>* _prev; // 指向前一个节点
    T _data;            // 存储的数据

    ListNode(const T& val = T())
        : _next(nullptr)
        , _prev(nullptr)
        , _data(val)
    {}
};

4.2 迭代器封装

由于 list 的节点在内存中不是连续的，我们不能使用原生指针作为迭代器。我们需要对节点指针进行封装，使其行为像指针一样（支持 *、->、++、--、!=、== 等操作）。

// 迭代器类模板
template<class T, class Ref, class Ptr>
struct ListIterator {
    typedef ListNode<T> Node;
    typedef ListIterator<T, Ref, Ptr> Self;

    Node* _node; // 指向当前节点的指针

    ListIterator(Node* node)
        : _node(node)
    {}

    // 解引用操作，返回节点数据的引用
    Ref operator*() {
        return _node->_data;
    }

    // 成员访问操作符，返回节点数据的指针
    Ptr operator->() {
        return &_node->_data;
    }

    // 前置 ++
    Self& operator++() {
        _node = _node->_next;
        return *this;
    }

    // 后置 ++
    Self operator++(int) {
        Self tmp(*this);
        _node = _node->_next;
        return tmp;
    }

    // 前置 --
    Self& operator--() {
        _node = _node->_prev;
        return *this;
    }

    // 后置 --
    Self operator--(int) {
        Self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }

    // 比较操作
    bool operator!=(const Self& l) const {
        return _node != l._node;
    }

    bool operator==(const Self& l) const {
        return _node == l._node;
    }
};

4.3 list 主体框架

template<class T>
class list {
    typedef ListNode<T> Node;
public:
    // 定义迭代器类型
    typedef ListIterator<T, T&, T*> iterator;
    typedef ListIterator<T, const T&, const T*> const_iterator;

    // 构造函数
    list() {
        _head = new Node; // 创建头结点（哨兵位）
        _head->_next = _head;
        _head->_prev = _head;
    }

    // 拷贝构造
    list(const list<T>& lt) {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
        for (const auto& e : lt) {
            push_back(e);
        }
    }

    // 赋值重载
    list<T>& operator=(list<T> lt) {
        swap(_head, lt._head);
        return *this;
    }

    // 析构函数
    ~list() {
        clear();
        delete _head;
        _head = nullptr;
    }

    // 迭代器相关
    iterator begin() {
        return iterator(_head->_next);
    }

    iterator end() {
        return iterator(_head);
    }

    const_iterator begin() const {
        return const_iterator(_head->_next);
    }

    const_iterator end() const {
        return const_iterator(_head);
    }

    // 容量
    size_t size() const {
        size_t sz = 0;
        Node* cur = _head->_next;
        while (cur != _head) {
            ++sz;
            cur = cur->_next;
        }
        return sz;
    }

    bool empty() const {
        return _head->_next == _head;
    }

    // 元素访问
    T& front() {
        return _head->_next->_data;
    }

    const T& front() const {
        return _head->_next->_data;
    }

    T& back() {
        return _head->_prev->_data;
    }

    const T& back() const {
        return _head->_prev->_data;
    }

    // 修改操作
    void push_back(const T& val) {
        insert(end(), val);
    }

    void pop_back() {
        erase(--end());
    }

    void push_front(const T& val) {
        insert(begin(), val);
    }

    void pop_front() {
        erase(begin());
    }

    // 在 pos 位置之前插入 val
    iterator insert(iterator pos, const T& val) {
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* new_node = new Node(val);

        // prev <-> new_node <-> cur
        prev->_next = new_node;
        new_node->_prev = prev;
        new_node->_next = cur;
        cur->_prev = new_node;

        return iterator(new_node);
    }

    // 删除 pos 位置的元素
    iterator erase(iterator pos) {
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* next = cur->_next;

        prev->_next = next;
        next->_prev = prev;
        delete cur;

        return iterator(next);
    }

    // 清空所有元素
    void clear() {
        Node* cur = _head->_next;
        while (cur != _head) {
            Node* next = cur->_next;
            delete cur;
            cur = next;
        }
        _head->_next = _head;
        _head->_prev = _head;
    }

    // 交换两个 list
    void swap(list<T>& lt) {
        std::swap(_head, lt._head);
    }

private:
    Node* _head; // 头结点（哨兵位），不存储有效数据
};

4.4 反向迭代器的实现

反向迭代器的 ++ 就是正向迭代器的 --，反向迭代器的 -- 就是正向迭代器的 ++。因此，我们可以通过封装正向迭代器来实现反向迭代器。

template<class Iterator>
class ReverseListIterator {
    // 注意：此处 typename 的作用是明确告诉编译器，Ref 是 Iterator 类中的类型，而不是静态成员变量
    // 否则编译器编译时就不知道 Ref 是 Iterator 中的类型还是静态成员变量
    // 因为静态成员变量也是按照  类名 ::静态成员变量名  的方式访问的
public:
    typedef typename Iterator::Ref Ref;
    typedef typename Iterator::Ptr Ptr;
    typedef ReverseListIterator<Iterator> Self;

public:
    // 构造
    ReverseListIterator(Iterator it)
        : _it(it)
    {}

    // 具有指针类似行为
    Ref operator*() {
        Iterator temp(_it);
        --temp;
        return *temp;
    }

    Ptr operator->() {
        return &(operator*());
    }

    // 迭代器支持移动
    Self& operator++() {
        --_it;
        return *this;
    }

    Self operator++(int) {
        Self temp(*this);
        --_it;
        return temp;
    }

    Self& operator--() {
        ++_it;
        return *this;
    }

    Self operator--(int) {
        Self temp(*this);
        ++_it;
        return temp;
    }

    // 迭代器支持比较
    bool operator!=(const Self& l) const {
        return _it != l._it;
    }

    bool operator==(const Self& l) const {
        return _it != l._it;
    }

    Iterator _it;
};

5. ⚖️ list 与 vector 的对比

vector 和 list 是 C++ 中最常用的两种序列式容器，它们的底层结构不同，导致其特性和应用场景也大相径庭。

特性 vector list
底层结构 动态顺序表，一段连续的内存空间 带头结点的双向循环链表
随机访问 ✅ 支持，访问任意元素效率为 O(1) ❌ 不支持，访问任意元素效率为 O(N)
插入和删除 ❌ 效率低，任意位置插入和删除需要搬移元素，时间复杂度为 O(N)。插入时可能需要增容（开辟新空间、拷贝元素、释放旧空间），进一步降低效率 ✅ 效率高，任意位置插入和删除不需要搬移元素，时间复杂度为 O(1)
空间利用率 ✅ 高，底层为连续空间，不容易造成内存碎片，缓存利用率高 ❌ 低，底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低
迭代器 原生态指针 对原生态指针（节点指针）进行封装
迭代器失效 插入元素时，可能会导致重新扩容，致使所有迭代器失效；删除时，当前迭代器需要重新赋值，否则会失效 插入元素不会导致迭代器失效；删除元素时，只会导致当前迭代器失效，其他迭代器不受影响
使用场景 需要高效存储，支持随机访问，不关心插入删除效率 大量插入和删除操作，不关心随机访问

6. 🎯 总结

list 是 C++ STL 中一个非常实用的容器，它通过双向链表结构，在任意位置的插入和删除操作上提供了无与伦比的效率。然而，它不支持随机访问的缺点也限制了它的应用场景。

  • 选择 vector：当你需要频繁地通过下标访问元素，并且插入删除操作主要发生在容器尾部时。
  • 选择 list：当你需要在容器中间位置频繁进行插入和删除操作，并且对随机访问没有要求时。

理解 list 的底层原理（节点结构、迭代器封装、哨兵位头结点）对于写出高效、健壮的 C++ 代码至关重要，也是面试中的高频考点。

7. 💡 经典面试题

1. 请简述 vector 和 list 的区别，并说明各自的应用场景。

参考答案：

  • 底层结构：vector 是动态顺序表（连续空间），list 是带头结点的双向循环链表。
  • 随机访问：vector 支持 O(1) 的随机访问，list 不支持，访问效率为 O(N)。
  • 插入删除：vector 在任意位置插入删除效率低（O(N)），且可能涉及扩容；list 在任意位置插入删除效率高（O(1)）。
  • 空间利用率：vector 空间利用率高，缓存友好；list 每个节点有额外指针开销，容易产生内存碎片。
  • 迭代器失效：vector 的插入可能导致所有迭代器失效，删除导致当前迭代器失效；list 的插入不会导致迭代器失效，删除仅导致当前迭代器失效。
  • 应用场景：vector 适用于需要高效随机访问、尾部操作多的场景；list 适用于需要大量中间插入删除、不关心随机访问的场景。

2. 为什么 list 的插入操作不会导致迭代器失效，而 vector 会？

参考答案：

  • list 的底层是链表，每个节点在堆上是独立分配的。插入操作只是创建新节点并调整相关节点的 prev 和 next 指针，不会改变已有节点的内存地址。因此，指向已有节点的迭代器依然有效。
  • vector 的底层是连续数组。当插入元素导致当前容量不足时，vector 会重新申请一块更大的内存，并将所有元素拷贝到新内存中，然后释放旧内存。这会导致所有指向旧内存的迭代器（包括 begin、end 等）全部失效。

3. 如何实现一个 list 的反向迭代器？

参考答案：
反向迭代器可以通过封装正向迭代器来实现。反向迭代器的 ++ 操作对应正向迭代器的 -- 操作，反向迭代器的 -- 操作对应正向迭代器的 ++ 操作。在解引用时，需要返回当前正向迭代器所指位置的前一个元素的值，这样才能保证反向遍历的正确性。

4. 什么是哨兵位头结点？它在 list 的实现中有什么作用？

参考答案：
哨兵位头结点（_head）是一个不存储有效数据的额外节点，它始终存在。它的 _next 指向链表的第一个有效节点，_prev 指向链表的最后一个有效节点。
作用：

  1. 简化边界处理：使得对空链表和非空链表的插入、删除操作可以统一处理，无需对首尾节点做特殊判断。
  2. 统一迭代器逻辑：使得 end() 迭代器可以指向 _head，从而让 begin() 到 end() 的遍历逻辑对空链表也成立。
# c++ # list # 面试
Logo
亚马逊云科技技术品牌专区

更多推荐

2026年量化工具选择，要跟着能力基础走

读者应理解，选择工具前要先判断自己的能力基础和当前任务。工具应该帮助自己补上当前最关键的缺口，而不是替代学习顺序本身。

avatar 亚马逊云科技技术品牌专区

近期零基础学量化，先按基础差异拆学习顺序

读者应明白，拆解学习顺序时要先看自己的基础缺口，再决定哪一段需要放慢。不同流程阶段都有不同检查任务，学习路线要能反映这些差异。

avatar 亚马逊云科技技术品牌专区

加州理工 CS367 C 语言系统编程笔记（一）

C语言是一种强大且广泛使用的编程语言，尤其在系统编程领域。本节课我们将学习C语言的基础语法，包括如何编写“Hello, World!”程序、声明变量以及使用基本数据类型。我们将通过实际的代码示例来加深理解。本节课中我们一起学习了C语言的基础语法，包括如何编写和运行一个简单的C程序、声明变量以及使用基本数据类型。我们还介绍了如何使用Shell环境来编译和运行程序。通过对比Java，你可以看到C语言在

avatar 亚马逊云科技技术品牌专区