What is a data structure that has O(1) for append, prepend, and retrieve element at any location?

Question

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.

Answer 1

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.

Answer 2

A deque (double-ended queue) may be implemented to provide all these operations in O(1) time, although not all implementations do. I've never used Java's ArrayDeque, so I thought you were joking about it not supporting random access, but you're absolutely right — as a "pure" deque, it only allows for easy access at the ends. I can see why, but that sure is annoying...

To me, the ideal way to implement an exceedingly fast deque is to use a circular buffer, especially since you are only interested in adding removing at the front and back. I'm not immediately aware of one in Java, but I've written one in Objective-C as part of an open-source framework. You're welcome to use the code, either as-is or as a pattern for implementing your own.

Here is a WebSVN portal to the code and the related documentation. The real meat is in the CHAbstractCircularBufferCollection.m file — look for the appendObject: and prependObject: methods. There is even a custom enumerator ("iterator" in Java) defined as well. The essential circular buffer logic is fairly trivial, and is captured in these 3 centralized #define macros:

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

As you can see in the objectAtIndex: method, all you do to access the Nth element in a deque is array[transformIndex(N)]. Note that I make tailIndex always point to one slot beyond the last stored element, so if headIndex == tailIndex, the array is full, or empty if the size is 0.

Hope that helps. My apologies for posting non-Java code, but the question author did say general answers were acceptable.

Answer 3

If you treat append to a Vector/ArrayList as O(1) - which it really isn't, but might be close enough in practice -
(EDIT - to clarify - append may be amortized constant time, that is - on average, the addition would be O(1), but might be quite a bit worse on spikes. Depending on context and the exact constants involved, this behavior can be deadly).

(This isn't Java, but some made-up language...).

One vector that will be called "Forward". A second vector that will be called "Backwards".

When asked to append - Forward.Append().

When asked to prepend - Backwards.Append().

When asked to query -

if ( Index < Backwards.Size() )
{
    return Backwards[ Backwards.Size() - Index - 1 ]
}
else
{
    return Forward[ Index - Backwards.Size() ]
}

(and also check for the index being out of bounds).

Answer 4

Your idea might work. If those are the only operations you need to support, then two Vectors are all you need (call them Head and Tail). To prepend, you append to head, and to append, you append to tail. To access an element, if the index is less than head.Length, then return head[head.Length-1-index], otherwise return tail[index-head.Length]. All of these operations are clearly O(1).

Answer 5

Here is a data structure that supports O(1) append, prepend, first, last and size. We can easily add other methods from AbstractList<A> such as delete and update

import java.util.ArrayList;

public class FastAppendArrayList<A> {
    private ArrayList<A> appends = new ArrayList<A>();
    private ArrayList<A> prepends = new ArrayList<A>();

    public void append(A element) {
        appends.add(element);
    }

    public void prepend(A element) {
        prepends.add(element);
    }

    public A get(int index) {
        int i = prepends.size() - index;
        return i >= 0 ? prepends.get(i) : appends.get(index + prepends.size());
    }

    public int size() {
        return prepends.size() + appends.size();
    }

    public A first() {
        return prepends.isEmpty() ? appends.get(0) : prepends.get(prepends.size());
    }

    public A last() {
        return appends.isEmpty() ? prepends.get(0) : appends.get(prepends.size());
    }