什么是O（1）的数据结构，用于在任何位置追加，预处理和检索元素？ [英] What is a data structure that has O(1) for append, prepend, and retrieve element at any location?

问题描述

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

Vector / ArrayList是用于追加和检索的O（1），但是O ）用于前缀。

LinkedList（在Java中实现为双向链表）是O（1），用于追加和前缀，但O（n）用于检索。 / p>

Deque（ArrayDeque）对于上面的所有内容都是O（1），但不能在任意索引处检索元素。

在我看来，满足上述要求的数据结构有2个可扩展列表（一个用于前置，一个用于追加），并且还存储偏移量以确定在哪里获取

解决方案

您正在寻找一个双端队列。这是按照您想要的方式在C ++ STL中实现的，您可以将其索引到其中，但不能在Java中进行索引。您可以通过使用两个数组来存储标准组件，并将其存储在零位置。如果你最终从零开始很长一段时间，这可能会浪费记忆力，但是如果你太过分了，你可以修改并允许deque爬行到一个新的数组。

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

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

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

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

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

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.

解决方案

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.

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屋！