只要粗粗看過數據結構，對鏈表的印象一定是插入、刪除操作都很快。不過對 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 失效。什麼玩藝，這樣的話我還用鏈表干什麼？
