从零开始实现 C++ 双向链表：深入理解链表底层原理

前言：

在 C++ 标准库中，std::list 是一种非常常用的数据结构，其底层采用了双向链表的实现。在实际开发中，双向链表是一种具有灵活插入和删除操作的数据结构，尤其适合那些需要频繁操作非连续内存数据的场景。本文将通过一个手动实现的双向链表类 list 来讲解双向链表的底层结构和实现原理。

1. 主要数据结构

在链表的实现中，节点是最基本的元素，每个节点存储数据以及指向前后节点的指针。为了支持双向操作，链表的每个节点都有两个指针，分别指向前驱节点和后继节点。下面的 list_node 是一个模板类，存储泛型类型 T 的数据。

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

    // 构造函数
    list_node(const T& x = T())
     : _data(x)
     , _next(nullptr)
     , _prev(nullptr) {}
};

2. 迭代器的实现

在链表的操作中，迭代器是至关重要的，它提供了与链表元素交互的机制。通过迭代器，用户可以像使用数组指针一样访问链表的元素。我们实现了 list_iterator 模板类，用于模拟标准库的迭代器。它不仅支持对节点的访问，还支持前后移动和增减操作。

template <class T, class Ref, class Ptr>
struct list_iterator {
    typedef list_node<T> Node;
    typedef list_iterator<T, Ref, Ptr> self;
    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--() {
        _node = _node->_prev;
        return *this;
    }

    // 后置++，移动到下一个节点，返回之前的状态
    self operator++(int) {
        self tmp(*this);
        _node = _node->_next;
        return tmp;
    }

    // 后置--，移动到上一个节点，返回之前的状态
    self operator--(int) {
        self tmp(*this);
        _node = _node->_prev;
        return tmp;
    }

    bool operator!=(const self& s) { return _node != s._node; }
    bool operator==(const self& s) { return _node == s._node; }
};

迭代器主要提供以下功能：

operator* 和 operator->：实现解引用操作，返回当前节点的数据。
operator++ 和 operator–：支持迭代器的前进和后退。
operator!= 和 operator==：支持迭代器的比较，判断是否到达链表末尾。
通过实现这些运算符，我们可以像操作指针一样操作链表中的元素。

3. 链表的实现

接下来，我们实现链表的主体类 list。这是一个模板类，可以存储任意类型的数据，并提供一些常见的链表操作。

3.1 基本结构

首先，我们在链表类中定义一个哨兵节点 _head，这个节点没有实际的数据作用，它的存在是为了简化链表的边界处理。通过让哨兵节点的 _next 和 _prev 指向自己，可以避免处理链表为空时的特殊情况。

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;  // 常量迭代器

    // 构造函数
    list() {
        empty_init();
    }

    // 拷贝构造函数
    list(const list<T>& lt) {
        empty_init();
        for (auto& e : lt) {
            push_back(e);
        }
    }

    // 赋值操作符
    list<T>& operator=(list<T> lt) {
        swap(lt);
        return *this;
    }

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

private:
    Node* _head;   // 哨兵节点
    size_t _size;  // 链表的大小

    // 初始化空链表
    void empty_init() {
        _head = new Node();
        _head->_next = _head;
        _head->_prev = _head;
        _size = 0;
    }
};

在 list 的实现中，除了常见的构造、析构函数，我们还实现了拷贝构造函数和赋值操作符。这确保了链表在被拷贝时能够正确复制内容。

3.2 链表的插入与删除

在双向链表中，插入和删除操作是其核心功能。我们通过 insert 函数将新元素插入到链表的指定位置。它首先获取要插入位置前后的节点，然后重新设置这些节点的指针，使新节点正确链接到链表中。

iterator insert(iterator pos, const T& val) {
    Node* cur = pos._node;
    Node* newnode = new Node(val);
    Node* prev = cur->_prev;

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

    newnode->_next = cur;
    cur->_prev = newnode;
    ++_size;

    return iterator(newnode);
}

对于删除操作，我们通过 erase 函数实现。erase 函数移除指定位置的节点，并将该节点前后的节点重新连接。

iterator erase(iterator pos) {
    assert(pos != end());

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

    prev->_next = next;
    next->_prev = prev;
    delete del;
    --_size;

    return iterator(next);
}

3.3 其他成员函数

我们还实现了链表的其他常用操作，如 push_back 和 push_front，用于在链表尾部和头部插入元素。pop_back 和 pop_front 则用于删除尾部和头部的元素。

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

这些操作都依赖于 insert 和 erase 函数，实现起来相对简单。

4. 迭代器操作与遍历链表

我们为链表提供了 begin() 和 end() 函数，用于获取链表的起始和结束迭代器。通过这些迭代器，用户可以遍历整个链表，访问每个元素。

iterator begin() {
    return iterator(_head->_next);
}

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

可以通过以下代码遍历链表的元素：

list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);

for (auto it = lt.begin(); it != lt.end(); ++it) {
    cout << *it << " ";
}
// 输出: 1 2 3

5. 拷贝构造与赋值运算符

我们实现了拷贝构造函数和赋值运算符，通过它们可以确保链表被正确复制。赋值运算符通过 swap 函数交换两个链表的内部结构，从而实现高效的赋值。

list<T>& operator=(list<T> lt) {
    swap(lt);
    return *this;
}

void swap(list<T>& tmp) {
    std::swap(_head, tmp._head);
    std::swap(_size, tmp._size);
}

6. 总结

本文从底层实现的角度详细讲解了如何手动实现一个双向链表容器 list。我们设计了双向链表的数据结构，通过节点、迭代器、基本的插入、删除操作，最终实现了一个功能完整的链表容器。以下是本文的主要内容回顾：

1.双向链表节点设计：每个节点存储数据元素，同时通过两个指针 _prev 和 _next 链接到前一个和后一个节点。这种设计使得我们可以在链表中进行双向遍历，并支持 O(1) 时间复杂度的插入和删除操作。

2.迭代器的实现：为了让链表可以像标准库中的容器一样被遍历，我们实现了 list_iterator。通过运算符重载，用户可以使用迭代器访问链表元素，进行正向和反向遍历。迭代器操作封装了链表内部的指针操作，使链表的使用更加简洁直观。

3.链表类的实现：

1. 插入和删除：我们实现了常见的 insert 和 erase 操作，它们负责在指定位置插入新元素或移除已有元素。双向链表的优势在于，我们可以在常数时间内完成这些操作，而无需像数组那样需要移动后续元素。
2. push_back 和 push_front：为了方便用户插入元素，我们提供了头部和尾部的插入操作，分别对应在链表的首位插入新元素。
3. pop_back 和 pop_front：链表的首尾删除操作也被封装在这两个函数中，方便用户快速删除首尾元素。

4.迭代器操作与遍历：通过 begin() 和 end() 函数，我们可以使用 C++ 标准的范围遍历方式遍历链表的所有元素。这使得链表容器的使用方式与 C++ 标准库中的其他容器一致，降低了使用门槛。

5.拷贝构造与赋值运算符：为了确保链表可以被正确拷贝，我们实现了拷贝构造函数和赋值操作符。在赋值操作中，我们通过 swap 函数实现高效的资源交换，避免了复杂的手动赋值操作。