C++如何手写实现双向链表-C++-PHP中文网

手写双向链表应优先明确所有权和生命周期：用std::unique_ptr管理next、裸指针存prev，禁止拷贝（=delete），移动安全；insert/erase需严格指针操作顺序；迭代器需区分const/non-const并正确定义end()；边界case（空链、单节点、头尾删）必须防护nullptr。

c++如何手写实现双向链表

为什么别急着写 `Node` 类？先想清楚所有权和生命周期

手写双向链表最常崩在析构和拷贝上——不是逻辑错，是对象被重复 delete 或访问野指针。C++ 里 next 和 prev 都是裸指针时，std::list 能安全，你写的容易段错误，核心就差一层语义约束：谁负责 new，谁负责 delete，拷贝是深是浅？

推荐起步就用 std::unique_ptr 管理 next，用裸指针存 prev（因为前驱不拥有后继）；或者全用裸指针但明确禁止拷贝（= delete），只支持移动。别一上来就写 Node* next; + Node* prev; 还配拷贝构造。

如果允许拷贝，必须深拷贝整条链，且每个 Node 的 prev 指针要重连，否则变成单向或悬垂
用 std::unique_ptr 做 next，Node* 做 prev，可避免循环引用，析构时从 head 一路 release 即可
不打算支持拷贝/赋值，就在类里声明 List(const List&) = delete; 和 List& operator=(const List&) = delete;

`insert_after` 和 `erase` 的指针操作顺序不能错

双向链表的中间插入/删除看似简单，但指针改错一步就内存泄漏或崩溃。关键不是“改哪几个”，而是“改的顺序”——尤其 erase 里，必须先保存 next 和 prev，再断开连接，最后 delete；反过来，insert_after 必须先连新节点的 prev 和 next，再改原节点的 next，最后改原 next 的 prev。

典型错误：cur->next = new_node; new_node->next = cur->next; —— 第一行已覆盖 cur->next，第二行取到的是新节点自己，不是原来的后继。

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

insert_after(Node* cur, int val) 正确顺序：

auto new_node = std::make_unique<node>(val);<br>new_node->prev = cur;<br>new_node->next = std::move(cur->next);<br>if (new_node->next) new_node->next->prev = new_node.get();<br>cur->next = std::move(new_node);</node>

erase(Node* to_del) 必须先记下 to_del->prev 和 to_del->next，再修改前后节点的指针，最后释放 to_del

迭代器怎么写才不被 `std::vector` 迭代器教坏？

别直接模仿 std::vector::iterator 返回 T& 和 T*。双向链表迭代器本质是包装一个 Node*，解引用返回 node->data 的引用，operator++ 就是 ptr = ptr->next.get()。难点在 const 迭代器和 end() 的实现。

end() 不能返回 nullptr 的迭代器——它得是个合法对象，通常指向一个 dummy tail 节点，或用 Node* 为 nullptr 但要求 operator!= 明确定义
const 迭代器不是加个 const 修饰符就行，得单独写 const_iterator 类，内部存 const Node*，operator* 返回 const T&
迭代器失效只发生在被 erase 的节点上，其他节点的迭代器仍有效——这点比 vector 友好，但很多人写完发现 for (auto it = begin(); it != end(); ++it) 中 erase 后没更新 it，导致跳过下一节点

测试时最容易漏掉的三个边界

空链表、单节点、头尾删除——这三个 case 一跑就崩，不是代码难，是判断条件漏了 nullptr 分支。比如 pop_front() 不检查 head == nullptr，直接 head->next.release() 就崩；erase(head.get()) 后忘了更新 head，后续操作全错。