擅长插入，删除和随机访问的数据结构

目前，我正在寻找以下数据结构。擅长插入，删除和随机访问的数据结构

快速在尾部插入。
快速删除头部。
能够执行随机访问。

我知道ArrayBlockingQueue擅长于（1）和（2），并且ArrayList擅长于（3）。是否有来自标准库/ Apache库/ Google库的单一数据结构，这使我能够同时满足所有3个要求？

来源

2011-10-10 Cheok Yan Cheng

可我知道后面使用ArrayBlockingQueue –

我觉得你的情况最好的数据结构是一个ringbuffer/circular buffer。环缓冲器在恒定时间内执行所有三个操作。

的实现可以发现here和许多其他here

编辑：与ringbuffers的问题是，你应该知道在一开始许多元素是如何在最坏的情况下缓冲。但也存在动态环形缓冲区。

来源

2011-10-10 07:47:39 thomas

的原因，我认为环形缓冲区是你想要的数据结构。一个动态缓冲区可以为你提供O（1）分期插入，和ArrayList一样，也是O（1）删除（通过移动指针）。我不知道它是否在通常的Java库中实现。 –

+1。这正是OP正在寻找的东西。我不认为在'java.util'中实现了一个，但是使用数组编写一个很容易。 – MAK

LinkedList的可能是合适的，如果速度是不是3.注意ArrayBlockingQueue被设计用于多线程将访问列表环境中非常重要。 ArrayList和LinkedList不是。如果您需要从多个线程访问它们，则必须使用Collections.synchronizedList()来包装它们。

来源

2011-10-10 08:00:11 andypandy

LinkedHashMap是一个U需要try.It插上U最重要的。

Hash和双链表数据结构的组合。

来源

2011-10-10 08:05:45

擅长插入，删除和随机访问的数据结构

回答

相关问题