访问Java LinkedList的更低级别？

我有一个包含几个特殊特殊元素的元素列表，我需要在常量时间内找到这些元素的邻居。这听起来很容易使用双向链表：简单地存储对包含这些特定元素的节点的引用，并检查它们的前一个节点和下一个节点。（我也喜欢使用链表，因为我经常删除和添加元素，列表很大，性能尤为重要）。访问Java LinkedList的更低级别？

但是，似乎Java的LinkedList不允许我存储包含元素的节点。是对的吗？如果是这样，是否有干净的做我需要做的事情？这不应该很难，但我没有找到解决方案。

这需要与不断变化的列表一起工作，我更喜欢在更改过程中不必更新任何内容（例如，如果我使用数组，我将不得不在数组中移动时不断更新它们的索引）。此外，我可能需要在未来从该特殊节点开始遍历列表而不浪费时间来查找该节点（这对于链表的低级实现也很容易），所以我会更感激解决方案也解决了这个问题。

编辑：谢谢你的答案。不过，我希望有一个解决方案不涉及实现我自己的链接列表版本。有一个吗？

来源

2011-03-24 loop

我可能是错的，但扩展'AbstractSequentialList'似乎是你最好的选择。 – biziclop 2011-03-24 23:39:49

ArrayList会做你想做的。 – 2011-03-24 23:43:14

@Romain Hippeau修改阵列列表虽然相当昂贵。 – biziclop 2011-03-24 23:57:30

我认为实现自己的双链表类是获得最佳性能的唯一方法。

标准列表实现通过使用抽象/信息隐藏来维护列表不变量。因此，他们“只是工作”......模仿应用程序在涉及多个线程的情况下对同步进行正确的操作。

您希望（也许需要）钻取抽象并获取实现细节，然后执行可能导致不变量被违犯的事情。它不受支持。

来源

2011-03-25 00:58:48

您可以使用ListIterator及其next（）和previous（）方法。注意：如果您不使用ListIterator而以任何方式更改列表，则ListIterator将失效。

或者您可以使用ArrayList的索引。

来源

2011-03-24 23:38:50

我认为OP的噩梦是你无法访问（和存储）实际的列表条目容器，所以给定值对象，你可以在那里不断跳转。但有一个非常好的理由，他们没有暴露。 – biziclop 2011-03-24 23:42:40

你可以创建你自己的双向链表。但是，您最终可能会引用不在列表中的节点。 ;） – 2011-03-24 23:57:23

这就是我提到的非常好的理由。 :)尽管在自定义实现中，您可以在条目容器中保留一个布尔型字段，告诉您您的引用是否仍然有效。 – biziclop 2011-03-24 23:59:44

访问Java LinkedList的更低级别？

回答

相关问题