1. 链表的本质为什么需要它数组的本质是连续内存块。这个连续性带来了两个致命约束:1分配时必须预知大小(动态扩容需要realloc代价是O(n)拷贝)。2插入/删除需要移动大量元素。但数组连续性的巨大优势是缓存友好CPU预取机制可以一次加载一批相邻元素到L1/L2缓存遍历速度极快。链表用离散的节点换取了动态插入和删除的自由。每个节点独立分配通过指针串联。这种设计的本质是用指针开销换取内存灵活性任意位置插入/删除O(1)且操作绝不会导致其他元素的迭代器失效被删除元素本身除外。struct Node { int data; struct Node* next; };链表和数组的基本操作效率对比操作数组单向链表双向链表随机访问O(1)O(n)O(n)头部插入O(n)O(1)O(1)尾部插入已知尾指针O(1) amortizedO(1)O(1)任意位置插入已知位置O(n)O(1)*O(1)*删除已知节点O(n)O(n)O(1)*表示在持有前驱节点指针的插入任意插入时如果没有持有前驱指针那么插入的效率也为O(n)。2.单向链表结构、实现与变体2.1 基础结构定义// C版本模板化智能指针版本 templatetypename T class m_list { private: struct Node { T data; unique_ptrNode next; Node(const T val, unique_ptrNode nxt nullptr) : data(val), next(nxt) {} Node(T val, Node *nxt nullptr) : data(std::move(val)), next(nxt) {} }; unique_ptrNode head_; Node *tail_; size_t size_; public: m_list() : head_(), tail_(nullptr), size_(0) {} // ... 插入、删除、查找等方法 };公开接口层面提供了完整的操作方法集包括插入操作push_front头插、push_back尾插、insert_at指定位置插入删除操作pop_front头删、pop_back尾删、erase_at指定位置删除、clear清空访问操作operator[]随机访问、size()获取长度控制权管理拷贝构造、移动构造、拷贝赋值运算符遍历支持Iterator迭代器类及begin()/end()方法2.2 核心数据结构设计Node节点结构struct Node { T data; unique_ptrNode next; Node(const T val) : data(val), next() { cout 拷贝构造Node: val \n; } Node(T val) : data(std::move(val)), next() { cout 移动构造Node: val \n; } ~Node() { cout 析构Node: data \n; }; };2.3 插入操作的实现头插法push_frontvoid push_front(const T val) // 左值版本 void push_front(T val) // 右值版本链表提供了两个版本的push_front函数分别处理左值和右值。这种重载是C11移动语义的核心应用。当传入左值时调用拷贝构造版本传入右值临时对象或std::move的结果时调用移动构造版本避免不必要的拷贝。void push_front(T val) { if (!head_) { head_ std::make_uniqueNode(std::forwardT(val)); tail_ head_.get(); } else { unique_ptrNode new_node std::make_uniqueNode(std::forwardT(val)); new_node-next std::move(head_); head_ std::move(new_node); } size_; }尾插法push_backvoid push_back(const T val) void push_back(T val)尾插操作充分利用了tail_指针的存在。如果没有tail_指针尾插操作需要从头遍历到尾时间复杂度为O(n)。有了尾指针尾插操作可以直接在O(1)时间内完成tail_-next std::make_uniqueNode(val); tail_ tail_-next.get(); size_;需要注意的是当链表为空时push_back直接调用push_front来处理。这种复用逻辑的方式简化了代码。指定位置插入insert_atvoid insert_at(size_t index, const T val) void insert_at(size_t index, T val)insert_at函数实现在指定索引位置插入元素其逻辑需要处理三种边界情况。当索引为0时调用push_front当索引等于大小时调用push_back其他情况则遍历到插入位置的前驱节点进行链接操作。核心插入逻辑展示了智能指针的所有权转移unique_ptrNode pNext std::move(pMove-next); unique_ptrNode newNode std::make_uniqueNode(val); newNode-next std::move(pNext); pMove-next std::move(newNode); size_;首先将待插入位置后续节点的所有权保存到pNext创建新节点后将其链接到后续节点最后将新节点链接到前驱节点。整个操作保持了所有权链条的完整性和正确性。2.4 删除操作的实现头删操作pop_frontvoid pop_front() { if (!head_) return; unique_ptrNode pNext std::move(head_-next); head_ std::move(pNext); --size_; }pop_front函数删除链表头部的第一个元素。实现采用了智能指针移动的优雅方式首先将原头节点的next指针指向第二个节点转移到临时智能指针pNext然后将head_移动到pNext。由于head_被覆盖原头节点失去所有权并自动被销毁。整个过程无需手动delete体现了智能指针的自动化内存管理优势。尾删操作pop_backvoid pop_back() { if (!head_) return; Node *pMove head_.get(); while (pMove-next.get() ! tail_) { pMove pMove-next.get(); } tail_ pMove; unique_ptrNode pNext std::move(tail_-next); tail_-next nullptr; --size_; }pop_back函数删除链表尾部元素。实现比头删稍复杂因为单向链表只能从头向尾遍历。这里需要找到倒数第二个节点即尾节点的前驱将其设置为新的尾节点。循环while (pMove-next.get() ! tail_)的作用就是定位到倒数第二个节点。找到后将tail_更新为该节点然后将尾节点的智能指针转移并清空。这段代码有一个需要关注的点当链表中只有一个节点时pMove就是head_而head_-next为空tail_也指向head_。此时循环不会执行直接将尾指针设置为pMove即head_然后移动并清空next。这个逻辑是正确的单节点链表尾删后变为空链表。指定位置删除erase_atvoid erase_at(size_t index) { if (index size_) return; // 越界 Node *pMove head_.get(); for (size_t i 0; i index - 1; i) { pMove pMove-next.get(); } unique_ptrNode pNext std::move(pMove-next); pMove-next std::move(pNext-next); --size_; }erase_at函数实现在指定位置删除元素。边界检查index size_确保不会访问越界位置。删除逻辑需要定位到待删除节点的前驱然后通过智能指针的移动操作将前驱节点直接链接到待删除节点的下一个节点。被移动的pNext原待删除节点在离开作用域时自动销毁其析构函数会打印调试信息。这段代码的巧妙之处在于不需要显式处理待删除节点只需将pMove-next重新指向 pNext-next待删除节点的所有权转移到pNext当pNext离开作用域时自动被清理。如果待删除节点是尾节点pNext-next为空nullptr尾节点的智能指针被正确处理tail_指针仍然指向正确的位置虽然可能已经悬空但在下一次push_back或pop_back时会重新定位。2.5 随机访问运算符的实现operator[]的设计T operator[](size_t index) { Node *pMove head_.get(); for (size_t i 0; i index; i) { if (!pMove) throw std::out_of_range(Index out of range); pMove pMove-next.get(); } return pMove-data; } const T operator[](size_t index) const { Node *pMove head_.get(); for (size_t i 0; i index; i) { if (!pMove) throw std::out_of_range(Index out of range); pMove pMove-next.get(); } return pMove-data; }operator[]提供了类似数组的下标访问能力这是链表相对少见的特性。标准库中的std::list不提供operator[]因为链表的随机访问时间复杂度是O(n)不符合数组式访问的使用预期。但作为教学实现或特定场景这个功能提供了便利。代码实现了两个版本非const版本返回可修改的引用const版本返回const引用。两个版本都通过遍历链表到指定位置来访问数据。安全检查在每次移动前判断pMove是否为空防止访问越界。2.6 拷贝与移动语义拷贝构造函数m_list(const m_list other) { if (!other.head_) return; Node *pMove other.head_.get(); while (pMove) { push_back(pMove-data); pMove pMove-next.get(); } }移动构造函数m_list(const m_list other) noexcept { head_ std::move(other.head_); tail_ other.tail_; other.tail_ nullptr; size_ other.size_; }拷贝赋值运算符m_list operator(const m_list other) { if (this other) return *this; clear(); for (Node *pMove other.head_.get(); pMove; pMove pMove-next.get()) { push_back(pMove-data); } return *this; }2.7 迭代器的设计与实现迭代器类遵循C标准库的迭代器规范定义了必要的类型别名。iterator_category forward_iterator_tag表明这是一个前向迭代器只支持单向遍历。这些类型别名使得迭代器能够与标准库算法如std::for_each、std::find等配合使用。class Iterator { private: Node *ptr_; public: using iterator_category std::forward_iterator_tag; using value_type T; using difference_type std::ptrdiff_t; using pointer T *; using reference T ; explicit Iterator(Node *ptr nullptr) : ptr_(ptr) {} // ... };迭代器操作reference operator*() const { #ifdef _DEBUG if (!ptr_) throw std::runtime_error(Dereferencing null iterator); #endif return ptr_-data; } Iterator operator() { #ifdef _DEBUG if (!ptr_) throw std::runtime_error(Incrementing past end); #endif ptr_ ptr_-next.get(); return *this; }代码大量使用std::unique_ptr来管理节点内存这一选择带来了多重优势。智能指针确保了节点的生命周期与链表一致当节点被删除或链表被清空时相关的内存会自动释放。同时移动语义天然支持节点所有权的转移使得push_front、insert_at、erase_at等操作可以简洁地实现无需手动管理内存。推荐一个零声教育学习教程个人觉得老师讲得不错分享给大家[LinuxNginxZeroMQMySQLRedisfastdfsMongoDBZK流媒体CDNP2PK8SDockerTCP/IP协程DPDK等技术内容点击立即学习:链接代码放在附件中