# 如何在 C++ 中实现一个自定义的双向链表？

2026-01-31 作者 stdcpp

双向链表（Doubly Linked List）是一种基础但功能强大的数据结构，它允许在 O(1) 时间内在任意位置插入或删除元素。C++ 标准库中提供了 std::list，但在某些场景下，我们可能需要更细粒度的控制，例如自定义节点存储、实现特定的遍历顺序或加入调试信息。下面给出一个完整、可编译的自定义双向链表实现示例，并逐步解释关键细节。

1. 设计思路

节点结构：每个节点保存数据值、指向前驱和后继的指针。
链表类：维护头尾指针、元素计数，并提供常用接口：
- push_front / push_back
- pop_front / pop_back
- insert / erase
- begin / end（返回迭代器）
迭代器：实现符合 Input/Forward 迭代器要求的自定义迭代器，支持 ++、*、==/!=。
异常安全：使用 RAII 管理内存，保证异常时不泄漏。

2. 代码实现

#include <iostream>
#include <iterator>
#include <stdexcept>
#include <initializer_list>

template<typename T>
class DoublyLinkedList {
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
        explicit Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}
    };

    Node* head_;
    Node* tail_;
    std::size_t size_;

    // Helper: link new node between a and b
    void link_between(Node* a, Node* b, Node* newNode) {
        newNode->prev = a;
        newNode->next = b;
        if (a) a->next = newNode;
        if (b) b->prev = newNode;
    }

    // Helper: unlink node
    void unlink(Node* node) {
        if (!node) return;
        if (node->prev) node->prev->next = node->next;
        if (node->next) node->next->prev = node->prev;
        if (node == head_) head_ = node->next;
        if (node == tail_) tail_ = node->prev;
        delete node;
    }

public:
    // ----------------- 迭代器 -----------------
    class Iterator {
        Node* ptr_;
    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type        = T;
        using difference_type   = std::ptrdiff_t;
        using pointer           = T*;
        using reference         = T&;

        explicit Iterator(Node* p = nullptr) : ptr_(p) {}
        reference operator*() const { return ptr_->data; }
        pointer operator->() const { return &(ptr_->data); }

        // Prefix
        Iterator& operator++() { ptr_ = ptr_->next; return *this; }
        Iterator& operator--() { ptr_ = ptr_->prev; return *this; }
        // Postfix
        Iterator operator++(int) { Iterator tmp(*this); ++(*this); return tmp; }
        Iterator operator--(int) { Iterator tmp(*this); --(*this); return tmp; }

        friend bool operator==(const Iterator& a, const Iterator& b) { return a.ptr_ == b.ptr_; }
        friend bool operator!=(const Iterator& a, const Iterator& b) { return a.ptr_ != b.ptr_; }
    };

    using iterator = Iterator;
    using const_iterator = Iterator;

    // ----------------- 构造 / 析构 -----------------
    DoublyLinkedList() : head_(nullptr), tail_(nullptr), size_(0) {}
    explicit DoublyLinkedList(std::initializer_list <T> init) : DoublyLinkedList() {
        for (const auto& v : init) push_back(v);
    }
    ~DoublyLinkedList() { clear(); }

    // ----------------- 基本接口 -----------------
    bool empty() const noexcept { return size_ == 0; }
    std::size_t size() const noexcept { return size_; }

    void clear() {
        while (head_) unlink(head_);
    }

    // 头部插入
    void push_front(const T& val) {
        Node* node = new Node(val);
        link_between(nullptr, head_, node);
        if (!tail_) tail_ = node;
        head_ = node;
        ++size_;
    }

    // 尾部插入
    void push_back(const T& val) {
        Node* node = new Node(val);
        link_between(tail_, nullptr, node);
        if (!head_) head_ = node;
        tail_ = node;
        ++size_;
    }

    // 头部删除
    void pop_front() {
        if (!head_) throw std::out_of_range("pop_front from empty list");
        unlink(head_);
        --size_;
    }

    // 尾部删除
    void pop_back() {
        if (!tail_) throw std::out_of_range("pop_back from empty list");
        unlink(tail_);
        --size_;
    }

    // ----------------- 插入与删除 -----------------
    // 在指定位置前插入
    iterator insert(iterator pos, const T& val) {
        if (pos.ptr_ == nullptr) { // 插入到尾部
            push_back(val);
            return iterator(tail_);
        }
        Node* node = new Node(val);
        link_between(pos.ptr_->prev, pos.ptr_, node);
        if (pos.ptr_ == head_) head_ = node;
        ++size_;
        return iterator(node);
    }

    // 删除指定位置
    iterator erase(iterator pos) {
        if (pos.ptr_ == nullptr) throw std::out_of_range("erase end");
        Node* next = pos.ptr_->next;
        unlink(pos.ptr_);
        --size_;
        return iterator(next);
    }

    // ----------------- 迭代器 -----------------
    iterator begin() { return iterator(head_); }
    iterator end()   { return iterator(nullptr); }
    const_iterator begin() const { return iterator(head_); }
    const_iterator end()   const { return iterator(nullptr); }

    // ----------------- 其他 -----------------
    // 打印链表（仅供调试）
    void print() const {
        for (auto it = begin(); it != end(); ++it)
            std::cout << *it << ' ';
        std::cout << '\n';
    }
};

3. 使用示例

int main() {
    DoublyLinkedList <int> list = {1, 2, 3, 4, 5};
    list.print();                 // 1 2 3 4 5 

    list.push_front(0);
    list.push_back(6);
    list.print();                 // 0 1 2 3 4 5 6 

    auto it = list.begin();
    ++it;                          // 指向 1
    list.insert(it, 99);           // 在 1 前插入 99
    list.print();                 // 0 99 1 2 3 4 5 6 

    list.erase(it);                // 删除 1
    list.print();                 // 0 99 2 3 4 5 6 

    list.pop_front();
    list.pop_back();
    list.print();                 // 99 2 3 4 5 

    return 0;
}

4. 关键点回顾

双向链表节点：持有前驱/后继指针，允许 O(1) 删除。
RAII：在 clear() 与析构函数里统一释放节点，避免泄漏。
迭代器：实现了 bidirectional_iterator_tag，支持前后遍历；符合 STL 迭代器协议，能与标准算法配合。
异常安全：所有插入操作在节点创建后立即完成链接，若后续操作抛异常，只要正确管理 delete，链表保持一致。

通过上述实现，你可以在自己的项目中自由扩展链表功能，例如添加 reverse()、sort() 或者自定义内存池，甚至将其改造成红黑树或跳表的基础结构。祝编码愉快！

发表评论取消回复