C++ 手写 List 容器实战：双向链表原理与源码实现

C++ 手写 List 容器实战：双向链表原理与源码实现 | 极客日志

结构部分	功能说明
哨兵头节点	不存储有效数据，仅作为操作锚点，统一空/非空链表的插入、删除逻辑，无需额外判断边界。例如：尾插时无需检查'是否为第一个节点'，直接通过头节点的前驱指针定位尾节点，简化代码逻辑。
数据节点	每个节点含_prev（前驱指针）、_next（后继指针）、_data（数据域），支持双向遍历。既可以从当前节点向前追溯前驱节点，也能向后访问后继节点，为迭代器的++/--操作提供底层支持。
循环特性	尾节点_next 指向头节点，头节点_prev 指向尾节点，形成闭环。例如：遍历到尾节点后，通过_next 可直接回到头节点；获取尾节点无需遍历整个链表，只需访问_head->_prev，提升尾操作效率。

特性	List（双向链表）	vector（动态数组）
插入删除效率	任意位置 O(1)（仅需调整节点前驱/后继指针，无需移动其他元素）。例如：在链表中间插入新节点时，只需修改目标位置前后节点的_prev 和_next 指针，操作耗时与链表长度无关。	中间位置 O(N)（插入/删除后需搬移后续所有元素）；尾端操作（无扩容时）接近 O(1)。例如：在数组第 5 位插入元素，需将第 5 位及之后的所有元素向后移动 1 位，元素越多耗时越长。
随机访问	不支持（需从表头/表尾遍历，时间复杂度 O(N)）。无法通过'容器名 [下标]'直接访问元素，必须通过迭代器逐步移动（++/--）才能定位目标位置。	支持（基于原生指针偏移，时间复杂度 O(1)）。可通过'容器名 [下标]'或 at(下标) 直接访问元素，例如 vec[3] 能瞬间定位到第 4 个元素，无需遍历。
迭代器失效	仅被删除节点的迭代器失效，其他迭代器（指向未删除节点的）仍有效。例如：删除链表中第 3 个节点后，指向第 2、4 个节点的迭代器可正常使用。	插入元素时：若触发扩容（原有内存空间不足），所有迭代器、指针、引用均失效；若未触发扩容，仅插入位置之后的迭代器失效。删除元素时，删除位置之后的迭代器均失效。
内存利用率	按需分配节点（每个节点存储数据 +2 个指针），无冗余空间，但存在'指针开销'（每个节点额外占用 2 个指针的内存）。内存分配分散，可能存在内存碎片。	扩容时会预分配额外内存（通常为当前容量的 1.5 倍或 2 倍），可能产生冗余空间（例如容量为 10 但仅存储 5 个元素，剩余 5 个空间闲置）。内存分配连续，缓存命中率更高。

#pragma once
#include <iostream>
#include <list>
using namespace std;
namespace Lotso {
    // 链表节点结构：存储数据与双向指针
    template<class T>
    struct list_node {
        list_node<T>* _prev; // 前驱节点指针
        list_node<T>* _next; // 后继节点指针
        T _data;             // 节点数据

        // 构造函数：默认值初始化，指针置空
        list_node(const T& x = T()) : _prev(nullptr), _next(nullptr), _data(x) {}
    };
}

namespace Lotso {
    // 迭代器类：T-数据类型，Ref-引用类型，Ptr-指针类型
    template<class T, class Ref, class Ptr>
    struct list_iterator {
        using Self = list_iterator<T, Ref, Ptr>; // 简化自身类型名
        using Node = list_node<T>;               // 节点类型别名
        Node* _node;                             // 迭代器指向的节点指针

        // 迭代器构造：接收节点指针初始化
        list_iterator(Node* node) : _node(node) {}

        // 1. 解引用运算符：返回数据引用（普通迭代器可修改，const 不可）
        Ref operator*() { return _node->_data; }

        // 2. 箭头运算符：支持复杂类型成员访问（如 struct.field）
        Ptr operator->() { return &_node->_data; }

        // 3. 前置++：向后移动（指向后继节点）
        Self& operator++() {
            _node = _node->_next;
            return *this;
        }

        // 4. 后置++：先返回当前，再移动
        Self operator++(int) {
            Self tmp(*this);
            _node = _node->_next;
            return tmp;
        }

        // 5. 前置--：向前移动（指向前驱节点）
        Self& operator--() {
            _node = _node->_prev;
            return *this;
        }

        // 6. 后置--：先返回当前，再移动
        Self operator--(int) {
            Self tmp(*this);
            _node = _node->_prev;
            return tmp;
        }

        // 7. 相等判断：比较节点指针
        bool operator!=(const Self& s) const { return _node != s._node; }
        bool operator==(const Self& s) const { return _node == s._node; }
    };
}

namespace Lotso {
    template<class T>
    class list {
        using Node = list_node<T>; // 节点类型别名
    public:
        // 类型重定义：普通/const 迭代器（复用 list_iterator）
        using iterator = list_iterator<T, T&, T*>;
        using const_iterator = list_iterator<T, const T&, const T*>;

        // -------------------------- 迭代器接口 --------------------------
        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); }

        // -------------------------- 初始化接口 --------------------------
        // 空链表初始化：创建哨兵头节点，形成自环
        void empty_init() {
            _head = new Node;
            _head->_prev = _head;
            _head->_next = _head;
        }

        // 默认构造
        list() { empty_init(); }

        // 初始化列表构造（支持{1,2,3}形式）
        list(initializer_list<T> il) {
            empty_init();
            for (auto& e : il) push_back(e);
        }

        // 范围构造（支持[first, last)区间）
        template<class InputIterator>
        list(InputIterator first, InputIterator last) {
            empty_init();
            while (first != last) {
                push_back(*first);
                ++first;
            }
        }

        // 析构函数：释放所有节点，避免内存泄漏
        ~list() {
            clear(); // 先删除所有数据节点
            delete _head; // 再删除哨兵头节点
            _head = nullptr; // 置空指针，避免野指针
            _size = 0;
        }

        // -------------------------- 插入删除接口 --------------------------
        // 尾插：复用 insert，简化代码
        void push_back(const T& x) { insert(end(), x); }

        // 头插：复用 insert
        void push_front(const T& x) { insert(begin(), x); }

        // 尾删：复用 erase
        void pop_back() { erase(--end()); }

        // 头删：复用 erase
        void pop_front() { erase(begin()); }

        // 任意位置插入：调整指针实现 O(1) 插入
        void insert(iterator pos, const T& x) {
            Node* cur = pos._node;     // pos 指向的当前节点
            Node* prev = cur->_prev;   // 当前节点的前驱
            Node* newnode = new Node(x); // 新建数据节点

            // 调整指针：prev <-> newnode <-> cur
            newnode->_prev = prev;
            newnode->_next = cur;
            prev->_next = newnode;
            cur->_prev = newnode;
            ++_size; // 有效元素个数递增
        }

        // 任意位置删除：返回下一个有效迭代器，避免失效
        iterator erase(iterator pos) {
            Node* cur = pos._node;     // 待删除节点
            Node* prev = cur->_prev;   // 前驱节点
            Node* next = cur->_next;   // 后继节点

            // 调整指针：跳过 cur 节点，连接 prev 和 next
            prev->_next = next;
            next->_prev = prev;
            delete cur; // 释放待删除节点内存
            --_size;    // 有效元素个数递减
            return iterator(next); // 返回下一个有效迭代器
        }

        // 清空容器：保留哨兵头节点，便于后续复用
        void clear() {
            iterator it = begin();
            while (it != end()) it = erase(it);
        }

        // -------------------------- 其他接口 --------------------------
        // 获取有效元素个数
        size_t size() const { return _size; }

    private:
        Node* _head;      // 哨兵头节点指针
        size_t _size = 0; // 有效数据节点个数
    };
}

#define _CRT_SECURE_NO_WARNINGS 1
#include "list.h"
using namespace std;

void test_list1() {
    Lotso::list<int> lt; // 尾插 4 个元素
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);

    // 1. 迭代器遍历
    Lotso::list<int>::iterator it = lt.begin();
    while (it != lt.end()) {
        cout << *it << " "; // 预期输出：1 2 3 4
        ++it;
    }
    cout << endl;

    // 2. 范围 for 遍历（依赖 begin() 和 end()）
    for (auto e : lt) {
        cout << e << " "; // 预期输出：1 2 3 4
    }
    cout << "\n" << endl;
}

int main() {
    test_list1();
    return 0;
}

void test_list2() {
    Lotso::list<int> lt;
    // 头插 2 个元素，尾插 2 个元素
    lt.push_front(-2);
    lt.push_front(-1);
    lt.push_back(1);
    lt.push_back(2);
    cout << "头插 + 尾插后：";
    for (auto e : lt) cout << e << " "; // 预期输出：-1 -2 1 2
    cout << endl;

    // 尾删 2 次，头删 2 次
    lt.pop_back();
    lt.pop_back();
    lt.pop_front();
    lt.pop_front();
    cout << "删除后 size：" << lt.size() << endl; // 预期输出：0
    cout << endl;
}

int main() {
    //test_list1();
    test_list2();
    return 0;
}

// 用 const 迭代器遍历的打印函数（验证只读特性）
void Print(const Lotso::list<int>& lt) {
    Lotso::list<int>::const_iterator it = lt.begin();
    while (it != lt.end()) {
        // *it = 10; // 编译报错：const 迭代器不可修改数据
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

void test_list3() {
    // 初始化列表构造
    Lotso::list<int> lt1 = { 1,2,3,4,5,6 };
    // 拷贝构造
    Lotso::list<int>lt2(lt1);
    cout << "lt2（拷贝 lt1）：";
    for (auto e : lt2) cout << e << " "; // 预期输出：1 2 3 4 5 6
    cout << endl;

    // const 迭代器遍历
    const Lotso::list<int>& clt = lt1;
    cout << "const 迭代器遍历 lt1：";
    Print(clt); // 预期输出：1 2 3 4 5 6
    cout << endl;
}

int main() {
    //test_list1();
    //test_list2();
    test_list3();
    return 0;
}

void test_list4() {
    Lotso::list<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);

    // 任意位置插入：在第 2 个元素（2）前插入 100
    auto it = lt.begin();
    ++it;
    lt.insert(it, 100);
    cout << "插入 100 后：";
    for (auto e : lt) cout << e << " "; // 预期输出：1 100 2 3 4
    cout << endl;

    // 任意位置删除：删除 100
    it = lt.begin();
    ++it;
    it = lt.erase(it);
    cout << "删除 100 后：";
    for (auto e : lt) cout << e << " "; // 预期输出：1 2 3 4
    cout << endl;

    // 清空容器
    lt.clear();
    cout << "clear 后 size：" << lt.size() << endl; // 预期输出：0
}

int main() {
    //test_list1();
    //test_list2();
    //test_list3();
    test_list4();
    return 0;
}

C++ 手写 List 容器实战：双向链表原理与源码实现

前言

一。底层原理：List 容器的'骨架'——带头双向循环链表

1.1 结构组成与优势

1.2 核心特性（对比 vector）

二。模块实现：Lotso 命名空间下的 List 核心代码

2.1 模块 1：链表节点（list_node）—— 容器的'基本单元'

2.1.1 代码实现（来自 list.h）

2.1.2 核心解析

2.2 模块 2：迭代器（list_iterator）—— 容器的'导航工具'

2.2.1 代码实现（来自 list.h）

2.2.2 核心解析

2.3 模块 3：容器类（list）——List 功能的'中枢'

2.3.1 代码实现（来自 list.h）

2.3.2 核心解析

三。功能测试：用 test.cpp 验证 List 正确性

3.1 测试用例 1：基础构造与遍历 (push_back+迭代器/范围 for)

3.1.1 代码实现 (来自 test.cpp)

3.1.2 测试结构与分析

3.2 测试用例 2：头插、头删、尾删

3.2.1 代码实现（来自 test.cpp）

3.2.2 测试结果与分析

3.3 测试用例 3：const 迭代器与拷贝构造

3.3.1 代码实现（来自 test.cpp）

3.3.2 测试结果与分析

3.4 测试用例 4：insert、erase 与 clear

3.4.1 代码实现（来自 test.cpp）

3.4.2 测试结果与分析

结尾：

更多推荐文章

相关免费在线工具

C++ 手写 List 容器实战：双向链表原理与源码实现

前言

一。底层原理：List 容器的'骨架'——带头双向循环链表

1.1 结构组成与优势

1.2 核心特性（对比 vector）

二。模块实现：Lotso 命名空间下的 List 核心代码

2.1 模块 1：链表节点（list_node）—— 容器的'基本单元'

2.1.1 代码实现（来自 list.h）

2.1.2 核心解析

2.2 模块 2：迭代器（list_iterator）—— 容器的'导航工具'

2.2.1 代码实现（来自 list.h）

2.2.2 核心解析

2.3 模块 3：容器类（list）——List 功能的'中枢'

2.3.1 代码实现（来自 list.h）

2.3.2 核心解析

三。功能测试：用 test.cpp 验证 List 正确性

3.1 测试用例 1：基础构造与遍历 (push_back+迭代器/范围 for)

3.1.1 代码实现 (来自 test.cpp)

3.1.2 测试结构与分析

3.2 测试用例 2：头插、头删、尾删

3.2.1 代码实现（来自 test.cpp）

3.2.2 测试结果与分析

3.3 测试用例 3：const 迭代器与拷贝构造

3.3.1 代码实现（来自 test.cpp）

3.3.2 测试结果与分析

3.4 测试用例 4：insert、erase 与 clear

3.4.1 代码实现（来自 test.cpp）

3.4.2 测试结果与分析

结尾：

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具