std::list 与 std::forward_list

一、概念

• std::list：双向循环链表（带哨兵头节点），每个节点存储 data + prev + next 三个指针。
• std::forward_list（C++11）：单向链表，更省内存、更快，但没有反向遍历、没有 size()（O(1)）。

二、底层结构与 Node

// libstdc++ 的 _List_node
template <typename T>
struct _List_node {
    _List_node* _M_next;   // prev
    _List_node* _M_prev;   // next
    T  _M_data;            // 实际数据
};

list 本身持有一个哨兵节点（header/dummy node），不存数据，用来统一空表与常规处理（首尾元素都有真实前后节点，简化插入删除逻辑）。

三、list vs vector vs deque

维度	list	vector	deque
存储	节点不连续	连续	分段连续
随机访问	O(n) ❌	O(1)	O(1) 略慢
头/尾插删	O(1)	头 O(n)	头尾 O(1)
任意位置插入/删除	O(1)（已知迭代器）	O(n)	O(n)
缓存命中	差	极好	较好
空间开销	每节点 2 指针 + 可能对齐填充	最小（仅容量浪费）	map 指针 + 段
插入是否失效迭代器	不失效（仅删除目标失效）	扩容全失效	见 deque 篇

四、高频问答

Q1. 什么场景用 list？

• 需要大量中间插入/删除且不常随机访问；
• 希望在任意位置插入/删除时不使其它迭代器、引用失效（list 的 splice 等操作保持其它迭代器有效）。

Q2. 迭代器失效？

• 只有被 erase 的那个元素的迭代器/引用/指针失效；其余全部有效。这是 list 相比 vector 的一大优势。
• 注意：list::erase 后可以用返回的迭代器继续遍历。

Q3. sort 是稳定排序吗？stable？

• std::list::sort() 是稳定排序（相比 std::sort 不稳定）。底层实现为归并排序（自底向上迭代式归并），因为链表无法随机访问，不适合快排。

Q4. list 为什么不提供 operator[] / at / 随机访问迭代器？

因为链表节点在内存中不连续，无法 O(1) 跳转到第 k 个节点；只能提供「双向迭代器」。

Q5. splice / merge / remove_if / unique？

• splice：把一段链表结点转接到另一个 list（O(1)，不拷贝数据，只是改指针）。这是 list 独有、面试常考的高级操作。
• merge：合并两个已排序链表（前提两表已有序）。
• remove_if / unique：按谓词删除 / 去重（删除相邻重复）。

五、手写双向链表要点

面试「手写 list」通常降级为「手写双向链表」，重点：插入/删除时的 4 个指针操作与顺序、不悬空、用哨兵简化边界。

template <typename T>
struct Node {
    T data;
    Node* prev;
    Node* next;
    Node(const T& d, Node* p = nullptr, Node* n = nullptr)
        : data(d), prev(p), next(n) {}
};

template <typename T>
class LinkedList {
public:
    LinkedList() { head_ = tail_ = nullptr; sz_ = 0; }

    ~LinkedList() { while (head_) { Node<T>* nx = head_->next; delete head_; head_ = nx; } }

    void push_front(const T& v) {
        Node<T>* nd = new Node<T>(v, nullptr, head_);
        if (head_) head_->prev = nd;
        else tail_ = nd;          // 空表时首尾一致
        head_ = nd;
        ++sz_;
    }
    void push_back(const T& v) {
        Node<T>* nd = new Node<T>(v, tail_, nullptr);
        if (tail_) tail_->next = nd;
        else head_ = nd;
        tail_ = nd;
        ++sz_;
    }
    // 在 pos 之后插入
    void insert_after(Node<T>* pos, const T& v) {
        Node<T>* nd = new Node<T>(v, pos, pos->next);
        if (pos->next) pos->next->prev = nd;
        else tail_ = nd;           // pos 是尾节点
        pos->next = nd;
        ++sz_;
    }
    void erase(Node<T>* pos) {
        if (pos->prev) pos->prev->next = pos->next;
        else head_ = pos->next;     // 删的是头
        if (pos->next) pos->next->prev = pos->prev;
        else tail_ = pos->prev;     // 删的是尾
        delete pos;
        --sz_;
    }
    size_t size() const { return sz_; }
private:
    Node<T>* head_;
    Node<T>* tail_;
    size_t sz_;
};

手写要点（追问点）

1. 删除时记得维护 head/tail 指针：删头则更新 head，删尾则更新 tail。
2. 插入/删除都涉及前后两个节点共 4 个指针连接，注意顺序（先接新节点再改旧，或反之，都要保证不会中途丢链表）。
3. 用 new/delete 逐节点分配即可；若手写部分析构/复制构造，需完整实现（或禁拷贝）。
4. 真实的 std::list 用哨兵头节点统一空表处理且不持有 size（C++11 前 list 的 size 是 O(n)），面试时说明即可。