什么是在任何位置具有O(1)for append,prepend和retrieve元素的数据结构？

Question

我正在寻找Java解决方案,但任何一般的答案也没关系.

Vector/ArrayList是O(1)用于追加和检索,但O(n)用于前置.

LinkedList(在Java中实现为双链接列表)是O(1)用于追加和前置,但是O(n)用于检索.

Deque(ArrayDeque)对于上面的所有内容都是O(1)但不能在任意索引处检索元素.

在我看来,满足上述要求的数据结构内部有2个可增长列表(一个用于前置,一个用于追加),还存储一个偏移量以确定在检索期间获取元素的位置.

Answer 1

你正在寻找一个双端队列.这是按照您所希望的方式在C++ STL中实现的,您可以将其编入索引,但不是在Java中,正如您所指出的那样.你可以想象,通过使用两个数组并存储"零"的位置,从标准组件中滚动自己.如果最终从零开始移动很长时间,这可能会浪费内存,但是如果你走得太远,你可以重新定义并允许双端队列爬进一个新阵列.

一个更优雅的解决方案,在管理两个数组时并不需要那么多的好处,就是将一个圆形数组强加到预先分配的数组上.这需要实现push_front,push_back以及后面数组的大小调整,但是调整大小的条件会更加清晰.

Answer 2

一个双端队列(双端队列)可以实现提供所有这些操作在O(1)时间,虽然不是所有的实现做.我从来没有使用过Java的ArrayDeque,所以我认为你开玩笑说它不支持随机访问,但你绝对正确 - 作为一个"纯粹"的双端队列,它只允许在两端轻松访问.我明白为什么,但这肯定很烦人......

对我来说,实现极快deque的理想方法是使用循环缓冲区,特别是因为你只想在前后添加删除.我没有立即意识到Java中的一个,但我在Objective-C中编写了一个作为开源框架的一部分.欢迎您按原样或作为实现自己的模式使用代码.

这是代码和相关文档的WebSVN门户.真正的肉在CHAbstractCircularBufferCollection.m文件中 - 寻找appendObject:和prependObject:方法.甚至还定义了自定义枚举器(Java中的"迭代器").基本的循环缓冲逻辑相当简单,并在这3个集中式#define宏中捕获:

#define transformIndex(index) ((headIndex + index) % arrayCapacity)
#define incrementIndex(index) (index = (index + 1) % arrayCapacity)
#define decrementIndex(index) (index = ((index) ? index : arrayCapacity) - 1)

正如您在objectAtIndex:方法中看到的,所有您在deque中访问第N个元素所做的就是array[transformIndex(N)].请注意,我tailIndex总是指向最后一个存储元素之外的一个槽,因此,如果headIndex == tailIndex,数组已满,或者如果大小为0则为空.

希望有所帮助.我对发布非Java代码表示歉意,但问题作者确实说一般答案是可以接受的.