爲什麼一個單鏈表有多個頭是件好事？

Question

在這篇文章中，When is doubly linked list more efficient than singly linked list?，RICI解釋說：

如果缺失並不重要，也許是因爲數據結構是不變的 ，單鏈表提供了另一種真正有用的特性： 它們允許結構共享。一個單鏈表可以愉快地成爲多個頭的尾部，這對於一個 雙鏈表是不可能的。由於這個原因，單鏈表有 傳統上是功能 語言選擇的簡單數據結構。

怎麼能有多個頭是好東西？

Answer 1

這本質上不是一件好事。這只是懶惰複製不可變鏈接列表的自然結果。

想象：

LinkedList a = createLinkedList(...); 

LinkedList b = prepend(a, 3.14); 

LinkedList c = prepend(a, 2.72); 

如果內容被懶惰地複製（這是很自然的選擇，如果列表是不可變的），那麼b和c第一元件現在的a第一元件都指向。

Answer 2

我想說如果在你的代碼中有多個列表的尾部部分是相同的，那麼將它們表示爲共享這些尾部的列表是一件好事，因爲它可以節省內存。但是，如果像這樣的東西對你沒有用，那麼這個能力不會給你任何東西。