C++ list 容器完全指南：双向链表的高效插入与删除

#include <iostream>
using namespace std;
 
struct ListNode
{
    int _data;         // 数据
    ListNode* _prev;   // 指向前一个节点
    ListNode* _next;   // 指向后一个节点
    ListNode(int v) : _data(v), _prev(nullptr), _next(nullptr) {}
};
 
int main()
{
    // 造一个空的"带头循环"骨架：哨兵自身首尾相连 = 空表
    ListNode sentinel(0);        // 哨兵头，数据字段无效
    sentinel._prev = &sentinel;
    sentinel._next = &sentinel;  // 空表特征：_prev == _next == &sentinel
 
    // 往尾部依次插入两个数据节点
    ListNode n1(10);             // 第 1 个数据节点
    n1._prev = sentinel._prev;   // 前驱指向哨兵
    n1._next = &sentinel;        // 后继指向哨兵
    sentinel._prev = &n1;        // 哨兵的前驱 = n1
    sentinel._next = &n1;        // 哨兵的后继 = n1（它成为 begin()）
 
    ListNode n2(20);             // 第 2 个数据节点
    n2._prev = sentinel._prev;   // 前驱指向 n1
    n2._next = &sentinel;        // 后继指向哨兵
    n1._next = &n2;              // n1 后继 = n2
    sentinel._prev = &n2;        // 哨兵前驱 = n2（它是最后一个）
 
    // 此刻：begin() == sentinel._next(即 n1)，end() == &sentinel（哨兵）
    cout << "首节点: " << sentinel._next->_data << '\n';   // 10
    cout << "尾节点: " << sentinel._prev->_data << '\n';   // 20
    cout << "尾节点 _next 又指回哨兵: "
         << (sentinel._prev->_next == &sentinel ? "是(成环)" : "否") << '\n'; // 是(成环)
    cout << "若这是空表 sentinel._prev==sentinel._next==&sentinel: "
         << "从上面注释看即可" << '\n';
    return 0;
}

#include <list>
#include <vector>
#include <utility>
#include <string>
#include <iostream>
using namespace std;
 
void show(const string& tip, const list<int>& l)
{
    cout << tip;
    for (auto& x : l) cout << ' ' << x;
    cout << '\n';
}
 
int main()
{
    // 1. 默认构造：一个空的 list，里面一个元素都没有
    list<int> l1;
 
    // 2. 指定元素个数和初值：5 个都等于 3 的元素
    list<int> l2(5, 3);
 
    // 3. 只给个数、不给定值：n 个默认值（对 int 就是 0）
    //    注意 empty 括号里那个值在 C++11 之前必须显式写，
    //    C++11 起才能省略，省略时用 T() 填充
    list<int> l3(4);              // 4 个 0
 
    // 4. 拷贝构造：用 l2 的内容造一个新的 list（深拷贝，互不影响）
    list<int> l4(l2);
 
    // 5. 用一段连续的迭代器区间 [first, last) 构造
    vector<int> v{ 7, 8, 9 };
    list<int> l5(v.begin(), v.end());   // 跨容器初始化，这是允许的
 
    // 6. 直接用一堆值初始化（C++11 新增的初始化列表语法）
    list<int> l6{ 10, 20, 30, 40 };
 
    // 7. 移动构造（C++11 新增）：把 l6 的资源"抢"过来，l6 被掏空
    list<int> l7(move(l6));
 
    // 8. assign：给一个已经存在的 list 重新装满内容（会清空旧的）
    list<int> l8;
    l8.assign(3, 9);              // 装 3 个 9
    l8.assign(l5.begin(), l5.end()); // 用 l5 的区间重装
 
    show("l2:", l2);      //  3 3 3 3 3
    show("l3:", l3);      //  0 0 0 0
    show("l5:", l5);      //  7 8 9
    show("l6:", l6);      //  （空，因为被移动走了）
    show("l7:", l7);      //  10 20 30 40
    show("l8:", l8);      //  7 8 9
    return 0;
}

#include <list>
#include <iostream>
using namespace std;
 
int main()
{
    list<int> l{ 1, 2, 3, 4 };
 
    cout << "是否为空: " << l.empty() << endl;     // 0 表示非空
    cout << "元素个数: " << l.size() << endl;      // 4
    cout << "最大容量: " << l.max_size() << endl;  // 实现相关，一般是个超大数
 
    cout << "头元素: " << l.front() << endl;       // 1
    cout << "尾元素: " << l.back() << endl;        // 4
 
    // front()/back() 返回的是引用，可以直接改
    l.front() = 100;       // 把头元素改成 100
    l.back() = 400;        // 把尾元素改成 400
    cout << "改后头元素: " << l.front() << endl;   // 100
    cout << "改后尾元素: " << l.back() << endl;    // 400
 
    cout << "清空前 size: " << l.size() << endl;   // 4
    l.clear();             // 清空所有数据节点，但哨兵保留
    cout << "clear 后 size: " << l.size()
         << " empty: " << l.empty() << endl;       // 0  1
 
    // clear 之后链表还能继续用，哨兵还在
    l.push_back(7);
    cout << "clear 后还能插入: " << l.front() << endl; // 7
    return 0;
}

#include <list>
#include <iterator>
#include <iostream>
using namespace std;
 
int main()
{
    list<int> l{ 10, 20, 30, 40 };
 
    // 正向遍历：从第一个元素走到 end()（哨兵）之前
    for (auto it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";   // 解引用得到当前节点的数据
    }
    cout << endl;             // 输出：10 20 30 40
 
    // 反向遍历：rbegin() 从最后一个元素开始，++ 朝头方向走
    for (auto it = l.rbegin(); it != l.rend(); ++it)
    {
        cout << *it << " ";
    }
    cout << endl;             // 输出：40 30 20 10
 
    // 算法库 <iterator> 里两个对双向迭代器友好的工具
    // advance：把迭代器"挪动 n 步"。list 没有 +n，只能线性走
    auto pos = l.begin();
    advance(pos, 2);                // 走到第 3 个(0 基)，即 30
    cout << "advance 后指向: " << *pos << endl;  // 30
 
    // distance：两个迭代器的距离。对 list 同样要线性算
    cout << "begin到end距离: "
         << distance(l.begin(), l.end()) << endl; // 4
 
    // 范围 for（C++11 起）。本质就是 begin()/!=/++(*)/end 的语法糖
    for (auto& x : l) x *= 10;      // 通过引用原地放大 10 倍
    for (auto& x : l) cout << x << " ";
    cout << endl;                   // 100 200 300 400
    return 0;
}

#include <list>
#include <utility>
#include <iostream>
using namespace std;
 
void print(const list<int>& l)
{
    // 注意：这里是 for 范围循环，std::list 只支持顺序访问，不能随机下标
    for (auto& x : l)
        cout << x << " ";
    cout << endl;
}
 
int main()
{
    list<int> l;
 
    l.push_back(3);    // 尾部插入 3
    l.push_back(4);    // 尾部插入 4
    l.push_front(2);   // 头部插入 2
    l.push_front(1);   // 头部插入 1
    print(l);          // 输出：1 2 3 4
 
    // insert：在指定位置之前插入元素
    auto it = l.begin();   // 指向第一个元素 1
    ++it;                  // 指向第二个元素 2
    l.insert(it, 99);      // 在 2 前面插入 99 -> 1 99 2 3 4
    print(l);              // 输出：1 99 2 3 4
 
    // erase：删除指定位置（迭代器指向的位置）的元素
    auto del = l.begin();  // 指向 1
    l.erase(del);          // 删掉 1
    print(l);              // 输出：99 2 3 4
 
    // C++11 起 erase 返回被删元素的下一个元素的迭代器
    auto nextIt = ++l.begin();   // 指向 2
    nextIt = l.erase(nextIt);    // 删除 2，返回指向 3 的迭代器
    print(l);                    // 输出：99 3 4
    cout << "erase 返回值指向: " << *nextIt << endl; // 3
 
    // swap：交换两个 list 的内部指针，O(1)，不拷贝任何元素
    list<int> m{ 100, 200 };
    l.swap(m);
    print(l);            // 输出：100 200
    print(m);            // 输出：99 3 4
 
    // emplace_back（C++11）：原地构造，省一次临时对象拷贝/移动
    list<pair<int, int>> pl;
    pl.emplace_back(1, 2);         // 直接在尾节点上构造 pair
    cout << "emplace: " << pl.front().first << ',' << pl.front().second << endl; // 1,2
 
    l.pop_front();   // 头删，删 100 -> 剩 200
    l.pop_back();    // 尾删，删 200 -> 空
    print(l);        // 输出：（空）
    return 0;
}

#include <list>
#include <iostream>
using namespace std;
 
int main()
{
    list<int> l{ 1, 2, 3, 4, 5 };
 
    auto it = l.begin();
    while (it != l.end())
    {
        l.erase(it);   // 错误：erase 后 it 指向的节点已被删除
        ++it;          // 错误：it 已经失效，对失效迭代器 ++ 是未定义行为
    }
    return 0;
}

#include <list>
#include <iostream>
using namespace std;
 
int main()
{
    list<int> l{ 1, 2, 3, 4, 5 };
 
    // 方式一：erase(it++)，前缀森林之王
    auto it = l.begin();
    while (it != l.end())
    {
        // 先让 it 自增到下一个节点，再把自增前的老值传给 erase
        // 这样哪怕 erase 把老节点删了，it 已经指向安全的下一个节点
        l.erase(it++);
    }
    cout << "清空后 size = " << l.size() << endl;  // 0
 
    // 方式二（C++11 起）：利用 erase 的返回值
    list<int> m{ 6, 7, 8 };
    auto p = m.begin();
    while (p != m.end())
        p = m.erase(p);      // 让 p 等于被删元素的下一个位置
    cout << "m 也空了 size = " << m.size() << endl; // 0
    return 0;
}

#include <list>
#include <iostream>
using namespace std;
 
void print(const char* tag, const list<int>& l)
{
    cout << tag << ":";
    for (auto& x : l) cout << ' ' << x;
    cout << endl;
}
 
int main()
{
    // 用法 1：整表转移，O(1)。dst 被 src 全部节点塞满，src 变空
    list<int> src{ 100, 200, 300 };
    list<int> dst{ 1, 2, 3 };
    dst.splice(dst.begin(), src);   // 把 src 整体插到 dst.begin() 之前
    print("dst", dst);              // 100 200 300 1 2 3
    print("src", src);              // （空）
 
    // 用法 2：单元素转移，O(1)。还能把"自己"的节点挪个位置！
    list<int> a{ 1, 2, 3, 4 };
    auto pos = a.begin(); ++pos;      // 指向 2
    a.splice(pos, a, --a.end());      // 把 a 的末尾元素 4 挪到 2 之前
    print("a", a);                    // 1 4 2 3
 
    // 用法 3：转移一段区间 [first,last)。跨容器时线性 O(N)
    list<int> e{ 1, 2, 3, 4, 5 };
    list<int> f{ 90 };
    auto first = e.begin(); ++first;                 // 指向 2
    auto last = e.begin();
    for (int i = 0; i < 4; ++i) ++last;              // 指向 5
    f.splice(f.end(), e, first, last);               // 把 e 的 [2,3,4) 移到 f
    print("e", e);                                   // 1 5
    print("f", f);                                   // 90 2 3 4
    return 0;
}

#include <list>
#include <functional>
#include <iostream>
using namespace std;
 
void print(const list<int>& l, const char* name)
{
    cout << name << ": ";
    for (auto& x : l)
        cout << x << " ";
    cout << endl;
}
 
int main()
{
    list<int> l{ 5, 2, 8, 1, 9, 3, 7 };
 
    // list 自己的排序（归并），默认升序
    l.sort();
    print(l, "升序");            // 升序: 1 2 3 5 7 8 9
 
    // 传一个比较规则（greater<int> 表示降序）
    l.sort(greater<int>());
    print(l, "降序");            // 降序: 9 8 7 5 3 2 1
 
    // 自定义类型的排序：给类型重载 <，或传 lambda/仿函数
    l.sort([](int a, int b) { return a % 10 < b % 10; });
 
    // 注意：std::sort(l.begin(), l.end()) 会编译失败，
    // 因为 list 迭代器不满足随机访问要求
    return 0;
}

#include <list>
#include <iostream>
using namespace std;
 
void print(const list<int>& l, const char* name)
{
    cout << name << ": ";
    for (auto& x : l) cout << x << " ";
    cout << endl;
}
 
int main()
{
    list<int> l{ 1, 2, 2, 3, 2, 4 };
 
    l.remove(2);       // 删除所有等于 2 的元素
    print(l, "remove"); // 输出：1 3 4
 
    // remove_if：按谓词删除，留一个条件来自定义
    list<int> m{ 1, 2, 3, 4, 5, 6 };
    m.remove_if([](int x) { return x % 2 == 0; });  // 删除所有偶数
    print(m, "remove_if");   // 输出：1 3 5
    return 0;
}

#include <list>
#include <iostream>
using namespace std;
 
void print(const list<int>& l, const char* name)
{
    cout << name << ": ";
    for (auto& x : l) cout << x << " ";
    cout << endl;
}
 
int main()
{
    // 相邻重复都被合并，只剩每组第一个
    list<int> a{ 1, 1, 2, 3, 3, 3, 4 };
    a.unique();
    print(a, "a");     // 输出：1 2 3 4
 
    // 注意"相邻"陷阱：这两个 2 中间隔着 3，unique 不去动它们
    list<int> b{ 1, 1, 2, 3, 3, 3, 2, 5, 5 };
    b.unique();
    print(b, "b");     // 输出：1 2 3 2 5
 
    // "先 sort 再 unique" 才是全局去重的正道
    list<int> c{ 3, 1, 2, 3, 1, 3 };
    c.sort();          // 1 1 2 3 3 3
    c.unique();        // 1 2 3
    print(c, "c");     // 输出：1 2 3
 
    // unique 带谓词版本：自定义"视为重复"的规则
    list<int> d{ 1, 2, 12, 23, 3, 2, 51, 1, 2, 2 };
    d.unique([](int x, int y) { return (x % 10) == (y % 10); });
    print(d, "d");     // 相邻且个位相同才去重
    return 0;
}

#include <list>
#include <iostream>
using namespace std;
 
void print(const list<int>& l, const char* name)
{
    cout << name << ": ";
    for (auto& x : l)
        cout << x << " ";
    cout << endl;
}
 
int main()
{
    list<int> a{ 1, 3, 5 };
    list<int> b{ 2, 4, 6 };
 
    // 两个 list 都必须是有序的
    a.merge(b);        // 有序合并到 a，b 被掏空
    print(a, "a");     // a: 1 2 3 4 5 6
    print(b, "b");     // b: （空）
    return 0;
}

#include <list>
#include <vector>
#include <iterator>
#include <type_traits>
#include <iostream>
using namespace std;
 
int main()
{
    typedef list<int>::iterator Lit;
    typedef vector<int>::iterator Vit;
 
    // iterator_traits 里藏着每个迭代器的"能力标签"
    typedef iterator_traits<Lit>::iterator_category LitTag;   // bidirectional_iterator_tag
    typedef iterator_traits<Vit>::iterator_category VitTag;   // random_access_iterator_tag
 
    // 编译期判定，是类型就返回 1，否则 0
    cout << "list 迭代器是 双向迭代器:  "
         << is_same<LitTag, bidirectional_iterator_tag>::value << endl;  // 1
    cout << "vector 迭代器是 随机访问:  "
         << is_same<VitTag, random_access_iterator_tag>::value << endl;  // 1
    cout << "list 迭代器是 随机访问:    "
         << is_same<LitTag, random_access_iterator_tag>::value << endl;  // 0
    return 0;
}

#include <cstddef>
#include <iostream>
using namespace std;
 
// ---------- 节点 ----------
template <class T>
struct Node
{
    T _data;          // 数据
    Node* _prev;      // 前驱
    Node* _next;      // 后继
    Node(const T& v = T()) : _data(v), _prev(nullptr), _next(nullptr) {}
};
 
// ---------- 迭代器：核心就是握着 Node* _cur ----------
template <class T>
struct ListIterator
{
    typedef ListIterator<T> Self;
    Node<T>* _cur;                          // 一个指向节点的指针
 
    ListIterator(Node<T>* cur) : _cur(cur) {}
 
    T&   operator*()  { return _cur->_data; }       // 解引用 = 取当前节点数据
    T*   operator->() { return &_cur->_data; }      // -> 访问成员
    Self&   operator++()      { _cur = _cur->_next; return *this; }  // ++ 就是沿 next 走
    Self    operator++(int)   { Self t(*this); _cur = _cur->_next; return t; }
    Self&   operator--()      { _cur = _cur->_prev; return *this; }  // -- 沿 prev 走
    bool    operator==(const Self& o) const { return _cur == o._cur; }
    bool    operator!=(const Self& o) const { return _cur != o._cur; }
};
 
// ---------- 极简 list ----------
template <class T>
class MyList
{
    typedef Node<T> NodeT;
    typedef ListIterator<T> iterator;
    NodeT* _head;     // 哨兵头，不存有效数据
    std::size_t _size;
public:
    MyList()
    {
        _head = new NodeT();           // 开辟哨兵
        _head->_prev = _head->_next = _head;  // 空表：哨兵自指成环
        _size = 0;
    }
    ~MyList() { clear(); delete _head; }
 
    iterator begin() { return iterator(_head->_next); } // 第一个数据节点
    iterator end()   { return iterator(_head); }        // 哨兵
    std::size_t size()  const { return _size; }
    bool        empty() const { return _size == 0; }
 
    void clear()
    {
        NodeT* cur = _head->_next;
        while (cur != _head) { NodeT* nx = cur->_next; delete cur; cur = nx; }
        _head->_prev = _head->_next = _head;
        _size = 0;
    }
 
    void push_front(const T& val) { insert(begin(), val); }
    void push_back(const T& val)
    {
        NodeT* n = new NodeT(val);
        n->_prev = _head->_prev;             // 新节点前驱 = 原尾
        n->_next = _head;                    // 新节点后继 = 哨兵
        _head->_prev->_next = n;             // 原尾的后继 = 新节点
        _head->_prev = n;                    // 哨兵前驱 = 新节点
        ++_size;
    }
 
    void pop_front() { erase(begin()); }
 
    // 在 pos 之前插入，返回指向新节点的迭代器 —— 只改四行指针，O(1)
    iterator insert(iterator pos, const T& val)
    {
        NodeT* n = new NodeT(val);
        NodeT* p = pos._cur->_prev;          // 定位 pos 的前驱
        n->_prev = p;
        n->_next = pos._cur;
        p->_next = n;
        pos._cur->_prev = n;
        ++_size;
        return iterator(n);
    }
 
    // 删除 pos 指向的节点，返回它的下一个 —— 也是四行指针，O(1)
    iterator erase(iterator pos)
    {
        NodeT* cur = pos._cur;
        NodeT* ret = cur->_next;
        cur->_prev->_next = cur->_next;
        cur->_next->_prev = cur->_prev;
        delete cur;
        --_size;
        return iterator(ret);
    }
};
 
int main()
{
    MyList<int> l;
    l.push_back(30);
    l.push_back(40);
    l.push_front(10);
    l.push_front(5);              // 5 10 30 40
    for (auto it = l.begin(); it != l.end(); ++it) cout << *it << ' ';
    cout << endl;                 // 5 10 30 40
 
    auto pos = l.begin(); ++pos;  // 指向 10
    l.insert(pos, 99);            // 5 99 10 30 40
 
    l.erase(l.erase(l.begin()));  // 先删 5，再删 99（返回值即下一个）→ 10 30 40
 
    for (auto it = l.begin(); it != l.end(); ++it) cout << *it << ' ';
    cout << "size=" << l.size() << endl;   // 10 30 40 size=3
    return 0;
}

#include <iostream>
using namespace std;
 
// 极其简化的反向迭代器思路（示意，只看包装关系）
template<class Iterator>
class ReverseListIterator
{
public:
    typedef ReverseListIterator<Iterator> Self;
 
    ReverseListIterator(Iterator it) : _it(it) {}
 
    // 关键：解引用时"后退一步"再取，所以 *rbegin() 能拿到最后一个元素
    // *反向迭代器 = *(正向迭代器往前退一格)
    auto operator*() const
    {
        Iterator tmp(_it);   // 拿一个正向迭代器的副本
        --tmp;               // 退一步
        return *tmp;         // 再解引用
    }
 
    // 反向迭代器的 ++ = 正向迭代器的 --（往前走）
    Self& operator++() { --_it; return *this; }
    // 反向迭代器的 -- = 正向迭代器的 ++（往回走）
    Self& operator--() { ++_it; return *this; }
 
    bool operator!=(const Self& o) const { return _it != o._it; }
 
private:
    Iterator _it;   // 内部装的其实是"正向迭代器"
};
 
int main()
{
    cout << "反向迭代器 = 正向迭代器 + 操作符号反转" << endl;
    return 0;
}