在C++中链表重不重要？ 第1页

std::list 是没用的。因为它不是 intrusive linked list。Intrusive linked list 是 Linux kernel 那种把 prev/next pointer 直接放入 data struct 里。这个设计在 C++ 里也很容易实现，只要用 templated base class 就可以了，可惜 std::list 没有采用。

链表的最大作用是它是一个局部化结构。局部化是指，逻辑代码只需要链表的一个 node，就可以对这个 node 本身进行 remove 操作，或者对其前后进行 insert 操作。或者进行 move to next 操作。而且链表的后半部分，从逻辑上也是一个完全的链表。

而这些都是 std::list 的设计无法满足的。因为 std::list 的设计要满足 STL 对一般 iterator 的惯例。而链表的特性和一般 iterator 的惯例是矛盾的。Iterator 会失效，而且 iterator 和 data struct 并非随时绑定。在逻辑代码中传递参数的时候会遇到很多两难问题。传 iterator 会遇到失效问题，传 data struct 会没法进行链表操作。

这个问题给人的感觉很无厘头，就好像在问在数学里面乘法重不重要一样……

更麻烦的是，竟然还有这么多无厘头的回答……