链表迷魂阵

只要粗粗看过数据结构，对链表的印象一定是插入、删除操作都很快。不过对 C++ 标准库里的 list（也就是 std::list ）就得多加小心。比如下面的代码：

std::list node_list;
...
NodeData a = node_list.front();
...
node_list.remove(a);

熟悉 STL 的人可能一眼发现其中的陷阱：node_list.remove(a) 可不是一个 O(1) 的操作（虽然经典链表的删除操作是）。这是因为 std::list<T>::remove(const T&) 实际是一个经典链表的查找操作加上一个经典删除操作。虽然能看出这个问题的人也许不在少数，但是犯下这个错误的人也不在少数。而且，当前者遇到后者编写的代码时，修改起来往往很头疼。因为虽然 NodeData 是从链表中取出的，但是它并没有存储前后节点的信息。所以要想把上面的有缺陷的代码改正，必须把所有涉及到 NodeData 参数传递和临时存储的地方都加以修改。所以说，使用 std::list::front() 这样的拷贝语义函数的行为本身看起来就是个错误。

这里先插上两句说说所谓『经典』链表（因为后文会拿来比较）。很多数据结构的书里的链表就是把 NodeData 这个对象本身加上一个 prev 指针和一个 next 指针，用来分别指向前一个和后一个节点。所以『经典』链表的数据结构和节点数据本身由一个对象表示。经典链表对 NodeData 的定义是侵入式的 —— 如果你希望把一个原来和链表操作完全没有联系的对象或者 struct 加入链表，就必须修改它本身的结构。相对的，std::list 的方式是把链表看成一种『容器』，包容原有的对象而无需修改其结构。

所以你的第一反应也许是应该永远用 std::list::begin() 或者 --std::list::end() 之类的操作返回 iterator，相比 NodeData，iterator 更像经典链表的节点，带有前后节点的联系。但是 C++ 永远不会给你简单的方案。这个方案的问题在当在代码的多处拥有指向同一个 NodeData 的 iterator 时，调用任何一个 iterator 或者 list 本身的 erase() 方法都会导致其它 iterator 失效。而且，C++ 标准库仅仅告诉你唯一的以定义行为是其它 iterator 会『失效』。你甚至没有一个 valid() 方法来检验一个 iterator 是否失效。C++ 标准期待的是你无论如何知道这一状态并且决不能再对那些 iterator 做任何操作。

所以 std::list 相比『经典』链表有两个致命问题。第一是直接取出 NodeData 的操作丢失了和 list 本身的联系，让后续操作承受性能损失。第二，『经典』链表可以通过设置 prev/next 让任何拥有 NodeData 指针的代码轻易的判断一个节点数据是否还在链表中，而 std::list 对 iterator 行为的粗略定义让这一点变得不可行。

接下来我们把问题搞得更全面（也更复杂）一些，考虑 NodeData 的生命周期。C++ 标准库一贯的拷贝语义让这个问题得到了（幼稚地）解决。但是对于 std::list 来说，我们已经看到拷贝语义的操作会让取出的节点丢失和 list 的联系，而总是取出 iterator 又会带来失效的问题。

当然，经典链表虽然没有 iterator 失效问题，但是仍然要面对何时销毁节点数据本身的问题。不过，讽刺的是并非所有的数据都是可复制（copiable）的，所以 std::list 里面存储的也经常并非数据本身，而是数据的指针。因此，在同样面对 std::list<NodeData> 的『联系切断』和『iterator 失效』两难之际，std::list<NodeData*> 还必须面对经典链表的销毁节点数据的时机问题。更遗憾的是，C++ 的内存管理法宝 shared_ptr 在这个问题上完全无能为力。一个 std::list< shared_ptr<NodeData> > 同样拥有『联系切断』和『iterator 失效』的矛盾。这时只有经典链表，加上在 NodeData 中实现手工引用计数才算一个比较完美的方案。

链表是 C++ 的好几个设计理念走麦城的地方。链表重在『链』，它的灵活性就在于『链』。把链表作为『容器』，特别是和 STL 其它容器一样保持拷贝语义操作就毁了链表。而且基于拷贝构造和自动析构的共享指针和手工的引用计数相比也并非处处领先。

如果一开始能抛开 STL 那种容器的概念和对数据节点不侵入的要求，C++ 的链表设计不会这么差。比如 Linux 内核的链表设计，把链表节点作为链表数据的一部分，让链表数据包含节点，而不是反之。这样的设计用 C++ 模版也完全可以作到。（当然我更喜欢 Linux 内核的基于宏的设计，而且 Linux 的设计通过一个可被优化的 forced cast 同样保证了类型安全。）

后记：

写这篇 blog 的时候又重温了一下 Java 的 LinkedList 文档，发现 C++ 还不是最差的。LinkedList 的文档是，至少 6.0 还如此 —— 对 LinkedList 做的任何结构更改（什么意思？删除节点算吗？）都会导致所有已经获取的 iterator 失效。什么玩艺，这样的话我还用链表干什么？