双向链表节点应统一用原始指针(Node*)表示prev和next,由链表容器统一管理内存;构造时置空指针;insert_after和erase需处理nullptr及头尾边界;迭代器须手动维护有效性,禁用std::iterator继承,正确声明类型别名与const语义。

如何正确设计双向链表的节点结构
节点必须同时持有 prev 和 next 指针,且不能裸用原始指针管理内存——否则插入/删除时极易出现悬垂指针或重复释放。推荐用 std::unique_ptr 管理 next,但 prev 不能也用 unique_ptr(会破坏所有权链),所以实际应统一用原始指针,靠链表容器本身保证生命周期安全。
常见错误是把 prev 和 next 都声明为 std::unique_ptr<node></node>,导致无法双向遍历(prev 指向的节点无法被当前节点“持有”)。正确做法是:
-
next和prev都是Node*(原始指针) - 所有节点由链表类内部的
std::vector<:unique_ptr>></:unique_ptr>或直接在堆上new后由链表统一delete - 构造函数中显式置
prev = next = nullptr,避免野指针
insert_after 和 erase 的边界处理要点
这两个操作看似简单,但最容易在空链表、单节点、插在头/尾时出错。关键不是“写对逻辑”,而是“提前拦截非法状态”。
例如 insert_after(nullptr, value) 应该插入到头部,而不是崩溃;erase(nullptr) 应该静默返回。实操建议:
立即学习“C++免费学习笔记(深入)”;
-
insert_after(Node* pos, T val):若pos == nullptr,等价于push_front(val);否则修改pos→next和新节点的prev/next,注意顺序:先连新节点的prev和next,再改pos→next和原pos→next→prev -
erase(Node* pos):必须检查pos == head_和pos == tail_,更新头尾指针;若pos→prev存在,要设pos→prev→next = pos→next;同理处理next;最后delete pos - 永远不要在
erase后继续访问pos,哪怕只是打印pos->data—— 这是典型 UAF(Use-After-Free)
迭代器解引用和递增的线程安全陷阱
标准库迭代器不要求线程安全,但你自己实现时容易忽略:迭代器本身不拥有节点,只持有一个 Node*。一旦外部调用 erase(it.node_),这个迭代器立刻失效。
这意味着你不能依赖 operator++ 的返回值做二次操作,比如 *(++it) 在 ++it 过程中若触发了节点删除(比如在自定义逻辑里误删),就会崩。实操建议:
-
operator*和operator->必须加空指针检查(调试模式下可assert(node_ != nullptr)) -
operator++()应返回*this(前缀),且只做node_ = node_->next;后缀版本需先拷贝再递增 - 禁止在循环中一边遍历一边调用
erase,除非你手动维护next指针,例如:auto it = begin();<br>while (it != end()) {<br> auto next = std::next(it);<br> if (should_erase(*it)) list.erase(it.node_);<br> it = next;<br>}
为什么不要继承 std::iterator
std::iterator 在 C++17 中已弃用,C++20 彻底移除。硬继承它不仅编译失败,还会掩盖你是否正确定义了 value_type、reference 等关键类型别名。
正确做法是直接在迭代器类内使用 using 声明:
template<typename T><br>struct list_iterator {<br> using value_type = T;<br> using reference = T&;<br> using pointer = T*;<br> using difference_type = std::ptrdiff_t;<br> using iterator_category = std::bidirectional_iterator_tag;<br> // ...<br>};漏掉 iterator_category 会导致无法用于 std::distance 或某些算法重载;把 reference 写成 const T& 而非根据 const 迭代器特化,会导致非常量迭代器无法赋值。
真正麻烦的是 const 迭代器的实现——它不该允许通过 operator* 修改元素,但又不能简单套用 const T&,因为 T 可能是用户自定义类型,其 const 成员函数未必覆盖全部接口。稳妥方式是让 const 迭代器持有 const Node*,并在 operator* 中返回 const T&。


















