C++ 双向链表完整实现：从节点到迭代器设计

概述

这是一个完整的模板类 yyq::list 的实现，模仿 C++ 标准库中的 std::list。作为 STL 中最经典的双向链表容器，list 的实现展示了 C++ 模板编程、迭代器设计、链表操作和内存管理的核心技术。本文将完整分析所有代码，包括被注释的部分，不遗漏任何细节。

一、整体架构与设计

1.1 命名空间与头文件保护

namespace yyq { // 链表实现 }

• 使用自定义命名空间 yyq 避免与标准库冲突
• 模板类设计，支持任意类型的元素
• #pragma once 防止头文件重复包含

1.2 链表节点设计

template <class T> struct list_node {
    T _data; // 存储的数据
    list_node<T>* _next; // 指向下一个节点
    list_node<T>* _prev; // 指向前一个节点
    // 构造函数
    list_node(const T& data = T()) :_data(data), _next(nullptr), _prev(nullptr) {}
};

详细分析：

1. 模板结构体：支持任意类型的数据
2. 双向指针：_next 和 _prev 实现双向链接，支持双向遍历
3. 默认构造函数：
   • 使用 T() 作为默认值，支持内置类型和自定义类型
   • T() 对于内置类型是零初始化，对于自定义类型调用默认构造函数
4. 成员初始化列表：高效初始化成员变量
5. 命名约定：使用下划线前缀 _data、_next、_prev，常见于成员变量命名

二、迭代器设计（核心部分）

代码展示了迭代器设计的完整演进过程，分为三个阶段：

2.1 第一阶段：两个独立的迭代器类（被注释的初始设计）

这部分代码被注释掉，展示了最初的实现思路：

2.1.1 普通迭代器 list_iterator<T>

template<class T> struct list_iterator {
    typedef list_node<T> Node;
    typedef list_iterator<T> Self;
    // 类成员变量，list 迭代器本质是链表节点的指针
    Node* _node;
    // 构造函数
    list_iterator(Node* node) :_node(node) {}
    // 不用写拷贝构造，浅拷贝足够了
    // 析构也不用写了
    T& operator*() { return _node->_data; // 返回非常量引用 }
    T* operator->() { return &_node->_data; // 返回非常量指针 }
    // 简化一下，类型名字有点长
    typedef list_iterator<T> Self;
    // list_iterator<T> operator++()
    Self& operator++() // 前置++
    { _node = _node->_next; return *this; }
    Self operator++(int) // 后置++
    { Self temp = *this; _node = _node->_next; return temp; }
    Self& operator--() // 前置--
    { _node = _node->_prev; return *this; }
    Self operator--(int) // 后置--
    { Self temp = *this; _node = _node->_prev; return temp; }
    bool operator==(const Self& s)const { return _node == s._node; }
    bool operator!=(const Self& s)const { return _node != s._node; }
};

2.1.2 const 迭代器 list_const_iterator<T>

template<class T> struct list_const_iterator {
    typedef list_node<T> Node;
    typedef list_const_iterator<T> Self;
    // 类成员变量，list 迭代器本质是链表节点的指针
    Node* _node;
    // 构造函数
    list_const_iterator(Node* node) :_node(node) {}
    // 不用写拷贝构造，浅拷贝足够了
    // 析构也不用写了
    const T& operator*() { return _node->_data; // 返回常量引用 }
    const T* operator->() { return &_node->_data; // 返回常量指针 }
    // 简化一下，类型名字有点长
    typedef list_iterator<T> Self;
    // list_iterator<T> operator++()
    Self& operator++() // 前置++
    { _node = _node->_next; return *this; }
    Self operator++(int) // 后置++
    { Self temp = *this; _node = _node->_next; return temp; }
    Self& operator--() // 前置--
    { _node = _node->_prev; return *this; }
    Self operator--(int) // 后置--
    { Self temp = *this; _node = _node->_prev; return temp; }
    bool operator==(const Self& s)const { return _node == s._node; }
    bool operator!=(const Self& s)const { return _node != s._node; }
};

2.1.3 第一阶段设计的详细分析：

1. 代码重复问题：
   • 两个类几乎完全相同，只有 operator* 和 operator-> 的返回类型不同
   • list_iterator 返回 T& 和 T*
   • list_const_iterator 返回 const T& 和 const T*
   • 其他所有代码（构造函数、自增自减、比较操作符）都完全相同
2. 设计思想：
   • 迭代器本质上是指向链表节点的指针
   • 通过操作符重载提供类似指针的语法
   • Self 类型别名简化代码编写
3. 优缺点：
   • 优点：逻辑清晰，分别处理常量和非常量迭代器
   • 缺点：代码重复严重，违反 DRY 原则（Don't Repeat Yourself）

2.2 第二阶段：改进的单一模板迭代器

这是当前使用的实现，解决了代码重复问题：

template<class T, class Ref, class Ptr>
struct list_iterator {
    typedef list_node<T> Node;
    typedef list_iterator<T, Ref, Ptr> Self;
    // 类成员变量，list 迭代器本质是链表节点的指针
    Node* _node;
    // 构造函数
    list_iterator(Node* node) :_node(node) {}
    // 不用写拷贝构造，浅拷贝足够了
    // 析构也不用写了
    Ref operator*() { return _node->_data; // Ref 可能是 T&或 const T& }
    Ptr operator->() { return &_node->_data; // Ptr 可能是 T*或 const T* }
    // 简化一下，类型名字有点长
    typedef list_iterator<T, Ref, Ptr> Self;
    // list_iterator<T> operator++()
    Self& operator++() // 前置++
    { _node = _node->_next; return *this; }
    Self operator++(int) // 后置++
    { Self temp = *this; _node = _node->_next; return temp; }
    Self& operator--() // 前置--
    { _node = _node->_prev; return *this; }
    Self operator--(int) // 后置--
    { Self temp = *this; _node = _node->_prev; return temp; }
    bool operator==(const Self& s)const { return _node == s._node; }
    bool operator!=(const Self& s)const { return _node != s._node; }
};

2.2.1 第二阶段设计的详细分析：

1. 模板参数设计：
   • T：元素类型
   • Ref：解引用操作符的返回类型（引用）
   • Ptr：箭头操作符的返回类型（指针）
2. 类型别名系统：

// 在 list 类中的定义
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;

• iterator：传递 T& 和 T*，返回非常量引用和指针
• const_iterator：传递 const T& 和 const T*，返回常量引用和指针

3. 优势：
   • 代码复用：一个模板实现两种迭代器
   • 编译时多态：通过模板参数决定行为
   • 类型安全：编译时检查类型一致性
4. 设计模式：
   • 这是模板元编程的典型应用
   • 通过模板参数实现策略模式

2.3 迭代器操作符的详细分析

2.3.1 解引用操作符 operator*()

Ref operator*() { return _node->_data; }

• 返回节点数据的引用
• Ref 模板参数决定是常量引用还是非常量引用
• 使得 *it 可以访问或修改元素值

2.3.2 箭头操作符 operator->()

Ptr operator->() { return &_node->_data; }

• 返回指向节点数据的指针
• Ptr 模板参数决定是常量指针还是非常量指针
• 使得 it->member 可以访问结构体/类成员

2.3.3 自增操作符

前置自增：

Self& operator++() {
    _node = _node->_next; // 移动到下一个节点
    return *this; // 返回当前对象的引用
}

• 修改自身状态
• 返回引用，支持链式调用

后置自增：

Self operator++(int) {
    Self temp = *this; // 保存当前状态
    _node = _node->_next; // 移动到下一个节点
    return temp; // 返回原来的状态
}

• 参数 int 仅用于区分前置和后置版本
• 返回临时对象，不能链式调用
• 性能略低于前置版本

2.3.4 自减操作符

实现原理与自增类似，只是移动方向相反。

2.3.5 比较操作符

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

• 比较底层节点指针
• 都是 const 成员函数，支持 const 对象比较
• 简单高效，时间复杂度 O(1)

三、链表类实现

3.1 成员变量

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

详细分析：

1. 哨兵节点设计：
   • _head 指向一个不存储有效数据的节点
   • 链表为空时：_head->_next == _head 且 _head->_prev == _head
   • 简化边界条件处理，避免空指针检查
2. 大小维护：
   • 维护 _size 变量使 size() 操作为 O(1)
   • 否则需要遍历链表计算大小，时间复杂度 O(n)

3.2 迭代器访问函数

3.2.1 begin() 和 end()

iterator begin() {
    iterator it(_head->_next); // 第一个有效元素
    return it;
}
iterator end() {
    iterator it(_head); // 哨兵节点作为结束位置
    return it;
}

代码中的三种等价写法（注释中展示）：

// 写法 1：显式创建临时对象（当前使用的写法）
iterator it(_head->_next);
return it;
// 写法 2：返回匿名对象
return iterator(_head->_next);
// 写法 3：依赖隐式类型转换（单参数构造函数）
return _head->_next; // 编译器自动转换为 iterator

3.2.2 const 版本的 begin() 和 end()

const_iterator begin()const {
    const_iterator it(_head->_next);
    return it;
}
const_iterator end()const {
    const_iterator it(_head);
    return it;
}

• 用于 const 对象
• 返回 const_iterator，只读访问

3.3 初始化函数

void empty_init() {
    _head = new Node; // 创建哨兵节点
    _head->_next = _head; // 指向自己
    _head->_prev = _head; // 指向自己
    _size = 0; // 大小为 0
}

• 所有构造函数的基础
• 创建自循环的哨兵节点
• 注意：哨兵节点的 _data 使用默认构造函数初始化

3.4 构造函数

3.4.1 默认构造函数

list() { empty_init(); }

• 创建一个空链表
• 只有哨兵节点

3.4.2 初始化列表构造函数

list(initializer_list<T> il) {
    empty_init();
    for (auto& e : il) {
        push_back(e); // 逐个添加元素
    }
}

支持现代 C++ 语法：

yyq::list<int> lst = {1, 2, 3, 4, 5}; // 初始化列表

3.4.3 拷贝构造函数

list(const list<T>& lt) {
    empty_init();
    for (auto& e : lt) {
        push_back(e); // 深拷贝每个元素
    }
}

详细分析：

1. 深拷贝：创建新节点复制数据
2. 使用范围 for 循环：依赖迭代器支持
3. 时间复杂度：O(n)，n 为源链表大小
4. 异常安全：如果 push_back 抛出异常，已分配的资源需要清理

3.5 赋值操作符

3.5.1 交换函数

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

• 使用 std::swap 交换指针和大小
• 效率高，不涉及元素复制

3.5.2 赋值操作符（现代实现）

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

拷贝并交换技法详细分析：

1. 参数 lt 是值传递，自动调用拷贝构造函数
2. 交换当前对象和 lt 的资源
3. lt 离开作用域时自动析构，释放原资源
4. 异常安全：如果拷贝构造失败，不会修改当前对象
5. 自赋值安全：参数是值传递，不会影响自赋值

3.6 析构函数

~list() {
    clear(); // 删除所有有效节点
    delete _head; // 删除哨兵节点
    _head = nullptr;
}

详细分析：

1. 先调用 clear() 删除所有数据节点
2. 再删除哨兵节点
3. 将指针置为 nullptr 避免悬空指针
4. 注意：对于自定义类型，会调用每个元素的析构函数

3.7 清空链表

void clear() {
    // iterator it = begin();
    auto it = begin();
    while (it != end()) {
        it = erase(it); // 返回下一个迭代器
    }
}

详细分析：

1. 使用 auto：简化类型声明
2. 安全删除方式：使用 erase 的返回值更新迭代器
3. 避免迭代器失效：直接使用 erase(it) 会使 it 失效
4. 时间复杂度：O(n)，n 为链表大小

四、链表操作实现

4.1 插入操作

4.1.1 通用插入函数

iterator insert(iterator pos, const T& x) {
    Node* newnode = new Node(x); // 创建新节点
    Node* cur = pos._node; // 当前位置节点
    Node* prev = cur->_prev; // 前一个节点
    // 连接新节点
    newnode->_next = cur;
    cur->_prev = newnode;
    newnode->_prev = prev;
    prev->_next = newnode;
    ++_size; // 更新大小
    return newnode; // 返回指向新节点的迭代器
}

连接步骤详细分析：

1. newnode->_next = cur：新节点的 next 指向当前位置
2. cur->_prev = newnode：当前位置的 prev 指向新节点
3. newnode->_prev = prev：新节点的 prev 指向前一个节点
4. prev->_next = newnode：前一个节点的 next 指向新节点

返回值：返回指向新插入元素的迭代器，符合 STL 规范

4.1.2 被注释的 push_back 实现

//void push_back(const T& x)
//{
//    Node* newnode = new Node(x);
//    Node* tail = _head->_prev; // 当前尾节点
//
//    tail->_next = newnode;
//    newnode->_prev = tail;
//
//    newnode->_next = _head;
//    _head->_prev = newnode;
//
//    ++_size;
//}

详细分析：

1. 直接实现：不依赖 insert
2. 效率：可能比 insert(end(), x) 略高（少一次函数调用）
3. 代码复用：当前实现使用 insert(end(), x)，更简洁
4. 逻辑：在哨兵节点前插入，即链表尾部

4.1.3 头部插入

void push_front(const T& x) {
    insert(begin(), x); // 在开始位置插入
}

4.1.4 尾部插入

void push_back(const T& x) {
    insert(end(), x); // 在结束位置前插入
}

注意：插入到 end() 位置实际上是在哨兵节点前插入，即链表尾部

4.2 删除操作

4.2.1 通用删除函数

iterator erase(iterator pos) {
    assert(pos != end()); // 不能删除哨兵节点
    Node* next = pos._node->_next;
    Node* prev = pos._node->_prev;
    // 跳过要删除的节点
    prev->_next = next;
    next->_prev = prev;
    delete pos._node; // 释放节点内存
    --_size; // 更新大小
    return next; // 返回下一个有效迭代器
}

详细分析：

1. 断言检查：确保不删除哨兵节点
2. 连接调整：
   • prev->_next = next：前一个节点跳过当前节点
   • next->_prev = prev：后一个节点跳过当前节点
3. 内存释放：delete 节点，调用元素析构函数
4. 返回值：返回下一个有效迭代器，避免迭代器失效

4.2.2 被注释的 erase 实现

//void erase(iterator pos)
//{
//    Node* cur = pos._node;
//    Node* prev = cur->_prev;
//    Node* next = cur->_next;
//
//    prev->_next = next;
//    next->_prev = prev;
//
//    delete cur;
//    cur = nullptr;
//
//    --_size;
//}

对比分析：

1. 没有返回值：调用者无法知道删除后的下一个有效位置
2. 迭代器失效：调用后 pos 失效，但调用者不知道
3. 当前实现更好：返回下一个迭代器，更安全

4.2.3 头部删除

void pop_front() {
    erase(begin()); // 删除第一个元素
}

4.2.4 尾部删除

void pop_back() {
    // erase(end()._node->_prev);
    erase(--end()); // 删除最后一个元素
}

两种写法：

1. erase(--end())：使用迭代器操作
2. erase(end()._node->_prev)：直接访问节点指针

4.3 容量相关函数

size_t size()const { return _size; // 直接返回存储的大小 }
bool empty()const { return _size == 0; // 检查大小是否为 0
    // 或者：return _head->_next == _head; }

详细分析：

1. O(1) 复杂度：维护 _size 变量
2. 注释中的替代方案：_head->_next == _head 检查链表是否为空
3. const 成员函数：可以用于 const 对象

五、辅助函数

5.1 通用容器打印函数

template<class Container>
void print_container(const Container& con) {
    // 方法 1：使用迭代器
    typename Container::const_iterator it = con.begin();
    while (it != con.end()) {
        cout << *it << " ";
        ++it; // 修正：原代码这里缺少++it，会导致死循环
    }
    cout << endl;
    // 方法 2：使用范围 for 循环
    for (auto e : con) {
        cout << e << " ";
    }
    cout << endl;
}

详细分析：

1. 模板函数：可以打印任何支持迭代器的容器
2. typename 关键字：
   • 必须使用，告诉编译器 Container::const_iterator 是一个类型
   • 因为 Container 是模板参数，编译器不知道 const_iterator 是类型还是静态成员
3. Bug 修复：原代码 while 循环中缺少 ++it，会导致死循环，此处已修正
4. 两种遍历方式：
   • 传统迭代器遍历
   • 范围 for 循环（依赖容器的 begin() 和 end()）
5. 通用性：可以用于 yyq::list、yyq::vector 等任何 STL 兼容容器

六、设计模式与编程技巧

6.1 哨兵节点模式

• 目的：简化边界条件处理
• 实现：创建不存储数据的头节点
• 优点：统一插入删除逻辑，避免空指针检查

6.2 拷贝并交换惯用法

• 目的：实现异常安全的赋值操作
• 实现：参数值传递 + swap
• 优点：自动处理自赋值，异常安全

6.3 模板元编程

• 目的：代码复用，编译时多态
• 实现：迭代器模板参数化
• 优点：消除代码重复，类型安全

6.4 RAII（资源获取即初始化）

• 目的：自动管理资源
• 实现：构造函数分配，析构函数释放
• 优点：避免资源泄漏

七、存在的问题与改进建议

7.1 存在的问题

1. 异常安全性不足：
   • new 可能失败，抛出 std::bad_alloc
   • 插入操作中如果 new 失败，应保持链表不变
2. 缺少移动语义支持（C++11）：
   • 移动构造函数
   • 移动赋值运算符
   • emplace 操作
3. 迭代器安全性：
   • 缺少迭代器有效性验证
   • 多线程环境不安全
4. 功能不完整：
   • 缺少反向迭代器
   • 缺少 sort、merge、unique 等算法
   • 缺少 resize、assign 等方法

7.2 改进建议

7.2.1 异常安全改进

iterator insert(iterator pos, const T& x) {
    Node* newnode = nullptr;
    try {
        newnode = new Node(x); // 可能抛出异常
    } catch (...) {
        // 如果 new 失败，链表保持不变
        throw; // 重新抛出异常
    }
    // ... 连接操作（不会抛出异常）
    return iterator(newnode);
}

7.2.2 添加移动语义支持

// 移动构造函数
list(list&& other) noexcept : _head(other._head), _size(other._size) {
    other._head = nullptr;
    other._size = 0;
}
// 移动赋值运算符
list& operator=(list&& other) noexcept {
    if (this != &other) {
        clear();
        delete _head;
        _head = other._head;
        _size = other._size;
        other._head = nullptr;
        other._size = 0;
    }
    return *this;
}
// emplace 操作
template <typename... Args>
iterator emplace(iterator pos, Args&&... args) {
    Node* newnode = new Node(T(std::forward<Args>(args)...));
    // ... 连接操作
    return iterator(newnode);
}

7.2.3 添加反向迭代器

typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
reverse_iterator rbegin() {
    return reverse_iterator(end());
}
reverse_iterator rend() {
    return reverse_iterator(begin());
}
const_reverse_iterator rbegin() const {
    return const_reverse_iterator(end());
}
const_reverse_iterator rend() const {
    return const_reverse_iterator(begin());
}

八、教学价值与学习要点

8.1 数据结构学习

• 双向链表的基本操作
• 哨兵节点的优势与应用
• 链表与数组的性能对比

8.2 C++ 模板编程

• 类模板与函数模板
• 模板参数推导
• 模板元编程技巧

8.3 STL 设计思想

• 迭代器模式
• 容器与算法的分离
• 泛型编程哲学

8.4 现代 C++ 特性

• 异常安全编程
• RAII 原则
• 移动语义

九、总结

这个 yyq::list 实现是一个优秀的教学范例，它完整展示了：

1. 从简单到复杂的演进过程：
   • 初始的两个独立迭代器类
   • 改进的模板化迭代器
   • 展示了代码重构和优化的思路
2. 完整的功能实现：
   • 链表节点的创建与连接
   • 迭代器的完整实现
   • 基本操作的实现
   • 拷贝控制和资源管理
3. 现代 C++ 编程实践：
   • 模板编程
   • 异常安全考虑
   • 代码复用技巧
4. STL 兼容性设计：
   • 标准的迭代器接口
   • 容器约定的方法
   • 与算法协同工作

虽然与标准库的 std::list 相比还有差距，但作为一个教学实现，它完美展示了双向链表和迭代器的核心原理，是学习 C++ 容器设计和模板编程的优秀范例。通过分析这个实现，可以深入理解 STL 的设计哲学和实现细节。