将LinkedHashSet转换为List

Question

假设列表b是一个LinkedList，假设列表a也是一个LinkedList。

问题：

如何在常数时间内将这些列表附加到一起？

答案：

这是可能的，因为LinkedList很可能是一个双向链表（否则它无法实现Deque接口）。而将双向链表附加到一起是一个0(1)操作。

addAll方法不会在常数时间内运行。

问题：

如何在常数时间内将LinkedHashSet转换为列表？

答案：

这也可能是可能的，因为LinkedHashSet“维护通过其所有条目的双向链接列表”。

- Klems

Answer 1

你需要实现自己的类。 LinkedList 类不会公开其内部节点结构，因此您不能只是将其最后一个节点指向另一个 LinkedList 的第一个节点。

对于 LinkedHashSet 来说，答案也是类似的：虽然它确实维护了这个双向链表，但你无法访问它。

- dlev

---

由于LinkedHashSet实现了抽象集合接口，因此您可以访问列表..请参见@Michael McGrady的答案。 - Northern Pole

Answer 2

你的假设基于没有封装的情况 - 也就是说，LinkedHashSet愿意向外界暴露其内部的LinkedList，但我怀疑它并不会这样做。

同样地，连接两个链表 - 我不知道每个节点是否知道自己属于哪个列表，但这肯定是一个可能会破坏你常数时间添加的可能性。即使它们不知道，一旦你把一个列表的头连接到另一个列表的尾部，就会出现问题 - 你有两个列表都引用着相同的数据，这将产生一些奇怪的后果。

换句话说，这两个操作在计算机科学意义上是可行的，你可以构建自己的实现来支持它们，但这并不意味着Java API以一种暴露其内部的方式来支持这些操作。

- Jon Skeet

---

Java 已经有一个将 LinkedList 追加的方法了吗？这些方法当然应该使用 LinkedList 而不是 List，因为它们无法与 ArrayList 一起工作。同样的，将 LinkedHashSet 转换为 LinkedList 也是如此。这其实就是我的问题所在。 - Klems

@Klems：不，我不认为它会 - 因为那样你会有两个共享节点的LinkedList对象。同样，如果调用者随后修改返回的列表，您该如何从LinkedHashSet创建LinkedList而不引入可能的损坏？（我想它可能会返回一个不可变视图。） - Jon Skeet

@Klems：嗯，你已经可以返回一个迭代器了…集合本身就是可迭代的。如果你只能从中读取，那么拥有一个链表会有什么好处呢？ - Jon Skeet

我们可以从适用于List且不修改它们的每种方法中受益。实际上，我认为LinkedHashSet更像List而不是Set。无论如何，我不明白将它们用作Set的意义所在。我必须在线程之间使用列表。 - Klems

@Klems：我想我们必须同意有所不同……但是你可以相当容易地构建具有该属性的自己的实现。 - Jon Skeet

Answer 3

你无法访问它，但我怀疑集合可以，所以你不应放弃希望，这是解决你问题的可行且快速的方法。

我进一步查看了，你是正确的。如果你有Set<Whatever> whatever = SOME CONSTRUCTOR，那么你可以编写List<Whatever> list = new LinkedList(whatever);，因为LinkedList具有Collections构造函数，而Set具有Collections接口。

- Michael McGrady