什么是具有 O(1) 以在任何位置追加、前置和检索元素的数据结构? [英] What is a data structure that has O(1) for append, prepend, and retrieve element at any location?

问题描述

我正在寻找 Java 解决方案，但任何一般性的答案也都可以.

I'm looking for Java solution but any general answer is also OK.

Vector/ArrayList 的追加和检索为 O(1)，而前置的为 O(n).

Vector/ArrayList is O(1) for append and retrieve, but O(n) for prepend.

LinkedList(在 Java 中实现为双向链表)对于追加和前置是 O(1)，但对于检索是 O(n).

LinkedList (in Java implemented as doubly-linked-list) is O(1) for append and prepend, but O(n) for retrieval.

Deque (ArrayDeque) 对于上述所有内容都是 O(1)，但无法检索任意索引处的元素.

Deque (ArrayDeque) is O(1) for everything above but cannot retrieve element at arbitrary index.

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

In my mind a data structure that satisfy the requirement above has 2 growable list inside (one for prepend and one for append) and also stores an offset to determine where to get the element during retrieval.

推荐答案

您正在寻找双端队列.这是在 C++ STL 中按照您想要的方式实现的，您可以对其进行索引，但不能在 Java 中进行索引，正如您所指出的.您可以通过使用两个数组并存储零"所在的位置，从标准组件中推出自己的组件.如果您最终从零移动很远，这可能会浪费内存，但如果您走得太远，您可以重新设置基准并允许双端队列爬入新数组.

You're looking for a double-ended queue. This is implemented the way you want in the C++ STL, which is you can index into it, but not in Java, as you noted. You could conceivably roll your own from standard components by using two arrays and storing where "zero" is. This could be wasteful of memory if you end up moving a long way from zero, but if you get too far you can rebase and allow the deque to crawl into a new array.

一个更优雅的解决方案，在管理两个数组时并不需要太多幻想，是将一个循环数组强加到一个预先分配的数组上.这将需要实现 push_front、push_back 及其后数组的大小调整，但调整大小等条件会更清晰.

A more elegant solution that doesn't really require so much fanciness in managing two arrays is to impose a circular array onto a pre-allocated array. This would require implementing push_front, push_back, and the resizing of the array behind it, but the conditions for resizing and such would be much cleaner.

这篇关于什么是具有 O(1) 以在任何位置追加、前置和检索元素的数据结构?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！