C++ list双向链表解析：标准库使用与模拟实现详解

摘要
本文详细介绍了C++标准库中的list类模板，包括其双向链表结构、常用接口（如构造函数、迭代器、容量和元素操作），以及模拟实现list的核心数据结构。重点讲解了list的特性和使用技巧，以及需要警惕的迭代器失效问题。

---

一、标准库中的list类模板

list是C++标准模板库（STL）中的一个重要序列容器。

核心特性：

• 序列式容器：list支持在常数时间内在任意位置进行插入和删除操作，并且可以双向迭代。
• 底层结构：其底层实现为一个双向链表。每个元素存储在一个独立的节点中，节点内包含指向前后元素的指针。在源码实现中，通常包含一个哨兵节点，构成一个双向循环链表。
• 与forward_list对比：forward_list是C++11引入的单向链表，只能向前迭代，因此更简单、内存开销更小。
• 优势与劣势：相比于array、vector、deque等序列容器，list在任意位置插入和移除元素的效率更高，尤其适合需要频繁调换元素位置的排序算法。其主要缺陷是不支持随机访问（即通过下标直接访问），访问任意元素都需要从起点开始线性遍历，时间复杂度为O(N)。此外，链式结构需要额外的空间来存储节点指针。

注意：使用list类时，必须包含头文件#include <list>，其命名空间为std。

二、list类的常用接口

构造函数

list提供了多种构造函数：

• list(): 构造一个空的list。
• list(size_type n, const value_type& val = value_type()): 构造一个包含n个元素的list，每个元素的值都是val。
• list(const list& x): 拷贝构造函数。
• list(InputIterator first, InputIterator last): 使用迭代器区间[first, last)中的元素来构造list。

int main()
{
    list<int> L1; // (1) 空list
    list<int> L2(5, 2); // (2) 构造5个值为2的list
    list<int> L3(L2); // (4) 拷贝构造L2

    string s("abcd");
    list<int> L4(s.begin(), s.end()); // (3) 使用迭代器区间构造

    // (6) C++11 列表初始化
    list<int> L5{ 1,2,3,4 };
    list<int> L6 = { 1,2,3,4 }; // 与L5等价
    return 0;
}

容量操作函数

函数	功能说明
resize	调整list的size。
empty	检测list是否为空。
size	返回有效节点的个数。
max_size	返回容器理论上可容纳的最大元素数量。
clear	清空所有有效元素。

int main()
{
    string s("abcd");
    list<int> L(s.begin(), s.end());
    cout << L.size() << endl;
    cout << L.empty() << endl;
    return 0;
}

访问及遍历操作函数

函数	功能说明
front	访问第一个元素。
back	访问最后一个元素。
begin / end	返回指向第一个元素的迭代器 / 返回指向最后一个元素下一位置（尾后）的迭代器。
rbegin / rend	返回指向最后一个元素的逆向迭代器 / 返回指向第一个元素前一个位置的逆向迭代器。

int main()
{
    string s("abcd");
    list<char> L(s.begin(), s.end());
    cout << L.front() << endl; // 输出 'a'
    cout << L.back() << endl;  // 输出 'd'
    return 0;
}

遍历是使用容器的基础操作，通常需要借助迭代器来完成，这与学习算法与数据结构中遍历链表的思路一脉相承。

int main()
{
    string s("abcd");
    list<int> L(s.begin(), s.end()); 

    // 正向遍历
    list<int>::iterator it = L.begin();
    while(it != L.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // 反向遍历
    list<int>::reverse_iterator rit = L.rbegin();
    while (rit != L.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    return 0;
}

---

增删查改操作

函数	功能说明
push_front	在头部插入元素。
pop_front	删除头部元素。
push_back	在尾部插入元素。
pop_back	删除尾部元素。
assign	用新内容替换当前所有元素。
insert	在指定位置（迭代器）插入元素。
erase	删除指定位置（迭代器）的元素。
swap	交换两个list的内容。
find	查找元素（由<algorithm>提供，非成员函数）。

int main()
{
    list<int>L, L1;
    L.push_back(2);
    L.push_back(3);
    L.push_front(1);
    L.insert(L.begin(), 0);
    L.erase(--L.end());
    L.pop_back();
    L.pop_front();

    L1.push_back(10);
    L.swap(L1);

    L.clear();
    return 0;
}

其他特有成员函数

list作为链表，提供了一些基于其结构优势的特有操作：	函数	功能说明
splice	将其他list中的元素移动到当前list的指定位置。
remove	移除所有值等于给定值的元素（erase是通过迭代器删除）。
remove_if	移除所有满足谓词条件的元素。
unique	删除连续的重复元素。
merge	合并两个已排序的list。
sort	对元素进行排序（list有自己的排序成员函数）。
reverse	逆置链表中元素的顺序。

迭代器失效问题

迭代器失效是指迭代器所指向的节点变得无效，最常见的情况是该节点被删除了。

• 插入操作：在list中插入新元素通常不会导致已有迭代器失效。
• 删除操作：删除元素会使指向被删除节点的迭代器失效。其他位置的迭代器不受影响。

int main()
{
    list<int> L;
    L.push_back(1);
    L.push_back(2);
    L.push_back(3);
    L.push_back(4);

    auto pos = ++L.begin(); // pos指向第二个元素 ‘2’
    L.erase(pos); // 删除pos指向的节点

    // pos迭代器已失效，其指向的节点已被释放，不能再对其进行操作
    // ++pos; // 错误行为
    // *pos;  // 错误行为
    return 0;
}

理解迭代器失效的机制，是正确、安全使用C++标准库容器（STL）的关键之一。

---

三、list的模拟实现

通过模拟实现，可以深入理解list双向链表的工作原理、迭代器的封装思想以及模板编程的技巧。

核心结构：

1. 节点类 __list_node：封装数据、前驱和后继指针。
2. 迭代器类 __list_iterator：封装节点指针，通过重载运算符模拟指针行为，实现遍历。
3. 容器类 list：管理哨兵头节点，提供对外接口。

namespace mylist
{
    // 1. 节点类模板
    template<class T>
    struct __list_node
    {
        __list_node(const T& data = T())
            :_prev(nullptr)
            , _next(nullptr)
            , _data(data)
        {}

        __list_node<T>* _prev;
        __list_node<T>* _next;
        T _data;
    };

    // 2. 迭代器类模板 (支持const和非const)
    template<class T, class Ref, class Ptr>
    struct __list_iterator
    {
        typedef __list_iterator<T, Ref, Ptr> self;
        typedef __list_node<T> Node;
        Node* _node;

        __list_iterator(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; // 应返回tmp
        }

        // 比较
        bool operator != (const self& it) const
        {
            return _node != it._node;
        }
        bool operator == (const self& it) const
        {
            return _node == it._node;
        }
    };

    // 3. list类模板
    template<class T>
    class list
    { 
        typedef __list_node<T> Node;
    public:
        typedef __list_iterator<T, T&, T*> iterator;
        typedef __list_iterator<T, const T&, const T*> const_iterator; 

        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); }

    private:
        Node* _head;

    public:
        // 构造函数
        list()
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
        }

        // 拷贝构造（传统写法）
        list(const list<T>& L)
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
            for (const auto& i : L)
            {
                push_back(i);
            }
        }

        // 迭代器区间构造
        template<class InputIterator>
        list(InputIterator first, InputIterator last)
        {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
            while (first != last)
            {
                push_back(*first);
                ++first;
            }
        }

        // 赋值运算符重载（现代写法）
        list<T>& operator=(list<T> L)
        {
            std::swap(_head, L._head);
            return *this;
        }

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

        // 容量与元素操作
        void clear()
        {
            auto it = begin();
            while (it != end())
            {
                it = erase(it);
            }   
        }

        void push_back(const T& x)
        {
            insert(end(), x);
        }
        void push_front(const T& x)
        {
            insert(begin(), x);
        }
        void pop_back()
        {
            erase(--end());
        }
        void pop_front()
        {
            erase(begin());
        }

        // 核心插入操作
        iterator insert(iterator pos, const T& x)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;

            Node* newnode = new Node(x);
            newnode->_prev = prev;
            newnode->_next = cur;

            prev->_next = newnode;
            cur->_prev = newnode;

            return newnode; // 单参构造函数支持隐式转换
        }

        // 核心删除操作
        iterator erase(iterator pos)
        {
            assert(pos != end()); // 不能删除哨兵位头节点

            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* next= cur->_next;

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

            delete cur; 
            return next; // 返回被删除元素的下一个位置
        }

        size_t size()
        {
            size_t sz = 0;
            iterator it = begin();
            while (it != end())
            {
                ++it;
                ++sz;
            }
            return sz;
        }

        bool empty()
        {
            return begin() == end();
        }
    };
}