鏈接列表的實現，在頭部添加還是在尾部添加？

我已經看到很多鏈接列表在頭部添加的實現，然後更新頭部引用或者不修改頭部引用，並且每次都在尾部添加更新。一個和另一個有明顯的好處嗎？哪一個是實施的首選方式？鏈接列表的實現，在頭部添加還是在尾部添加？

2011-05-01 phoenix

一個將新節點放在首位，另一個放在尾部。是否有優勢取決於你想要新節點的位置。 – 2011-05-02 00:03:24

沒有任何好處。事實上，唯一使頭部和尾部成爲尾巴的是我們稱之爲頭部和尾部。你可以用尾巴代替頭部，尾巴用頭部代替，而且你會有相同的確切列表，除非它是「倒退」。（這一點假設一個雙向鏈表...）

這有點像物質和反物質......

2011-05-02 00:03:28 corsiKa

鏈表的絕對簡單的實現只能（有效），在頭部添加。爲了添加到尾部，您需要第二個指向當前最後一個元素的指針。

用戶可能希望能夠添加到任一端，以及能夠在常量時間內查詢列表長度，並且從尾到頭遍歷列表（意味着您需要一個雙鏈表），所以一個合理的默認實現應該支持它（就像java.util中的那樣）。

如果您能證明有限的功能並獲得一些真正的好處（例如尾部共享以降低存儲要求），那麼您只能使用單鏈表。 ConcurrentLinkedQueue似乎是單鏈接的，以允許無鎖併發。在Javadocs中提到了無法知道當前長度的權衡。

2011-05-02 00:03:36 Thilo

我誠實地不知道生產庫中的任何單鏈表實現。 – corsiKa 2011-05-02 00:05:27

@glowcoder：我認爲java.util.concurrent.ConcurrentLinkedQueue是單鏈接的。 – Thilo 2011-05-02 00:17:25

你可能會爭論是否這是一個列表（注意它明顯缺乏實現List接口），儘管它似乎是用一個單獨的鏈表來實現的。確實，FIFO隊列不會從雙鏈路中受益。 – corsiKa 2011-05-02 00:22:57

java.util.LinkedList實現了兩個功能。它使它成爲通用的 - 可以將它用作隊列（FIFO）和堆棧（LIFO）

2011-05-02 00:11:15 Nulldevice

回答