链接列表的实现，在头部添加还是在尾部添加？

我已经看到很多链接列表在头部添加的实现，然后更新头部引用或者不修改头部引用，并且每次都在尾部添加更新。一个和另一个有明显的好处吗？哪一个是实施的首选方式？链接列表的实现，在头部添加还是在尾部添加？

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

回答