Is there a way to achieve retrieval (get()) with O(1) time complexity for ArrayDeque?

Question

I am trying to use ArrayDeque for a class that is supposed to have O(1) time complexity for addfront, addback and retrieval. I could only think of using toArray() for retrieval and it is unfortunately O(n). Is there a way to implement a retrieval method for ArrayDeque that is O(1)?

Answer 1

No.

I looked through the source code of ArrayDeque, and in no place is there a method that accesses an arbitrary array element by index. This would have been required in order for the operation to perform in O(1).

It shouldn’t be too hard to implement your own class that fulfils your requirements, though. Search for “circular buffer”. If your array overflows, copy the entire contents into a new array of double size. This can’t be done in constant time, of course, but adding will still be in amortized constant time, the same as for ArrayDeque.

I have assumed that by get() you mean inspecting (without removing) an element by its position/index in the queue counted either from the front or from the back.

Edit

I guess another way would be to use array and find a way to make addfront constant time but I'm not sure how

Here’s a simple implementation. Please develop further to your need. The ideas are to use a circular buffer and to copy to a new array if the old one gets too small. I believe that ArrayDeque uses the same ideas.

public class MyArrayDeque<E> {

    private Object[] elements;
    
    // Index to first element.
    private int front = 0;
    // Index to first free space after last element.
    // back == front means queue is empty (not full).
    private int back = 0;
    
    public MyArrayDeque(int initialCapacity) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Initial capacity must not be negative");
        }
        // There’s always at least 1 free space, so add 1 to have room for initialCapacity elements
        elements = new Object[initialCapacity + 1];
    }

    public void addFront(E elem) {
        checkCapacity();
    
        if (front == 0) {
            front = elements.length - 1;
        } else {
            front--;
        }
        
        elements[front] = elem;
    }

    public void addBack(E elem) {
        checkCapacity();
        
        elements[back] = elem;

        if (back == elements.length - 1) {
            back = 0;
        } else {
            back++;
        }
    }

    // Makes sure the queue has room for one more element.
    private void checkCapacity() {
        boolean needToExpand;
        if (front == 0) {
            needToExpand = back == elements.length - 1;
        } else {
            needToExpand = back == front - 1;
        }
        if (needToExpand) {
            Object[] newElements = new Object[elements.length * 2];
            if (front <= back) {
                int size = back - front;
                System.arraycopy(elements, front, newElements, 0, size);
                front = 0;
                back = size;
            } else {
                int numberOfElementsToCopyFirst = elements.length - front;
                System.arraycopy(elements, front, newElements, 0, numberOfElementsToCopyFirst);
                System.arraycopy(elements, 0, newElements, numberOfElementsToCopyFirst, back);
                front = 0;
                back = numberOfElementsToCopyFirst + back;
            }
            elements = newElements;
        }
    }

    /** Gets the ith element counted from the front without removing it. */
    public E get(int i) {
        int index = front + i;
        if (index >= elements.length) {
            index -= elements.length;
        }
        boolean outOfRange;
        if (front <= back) {
            outOfRange = index < front || index >= back;
        } else {
            outOfRange = index >= back && index < front;
        }
        if (outOfRange) {
            throw new ArrayIndexOutOfBoundsException(i);
        }
        return getInternal(index);
    }

    @SuppressWarnings("unchecked")
    private E getInternal(int index) {
        return (E) elements[index];
    }

}

For a simple demonstration:

    MyArrayDeque<String> queue = new MyArrayDeque<>(1);
    
    queue.addFront("First element added");
    queue.addBack("Added at back");
    queue.addFront("Added at front");
    
    System.out.println(queue.get(1));

Output is:

First element added

Answer 2

You could achieve it using additional structure so the space complexity will become O(2n) which might not be very important. The approach I could suggest is to use a HashMap and to store there an index and link of Object you put to queue. Also, you will need to keep track on first and last index available. Every time you will have to access the element by index - you will have to calculate the shift based on the start index. Of course, you will have to take care to update start and end indexes every time element is added or removed from the queue. The only disadvantage - removal from the middle may take O(n), which might not be critical for the queue case. Here is an example with states of your objects while using additional structure:

indexMap: {}
startIndex:0
endIndex:0

--> add an element to the head 
newCalculatedIndex = startIndex == endIndex ? startIndex : startIndex -1; 
//newCalculatedIndex = 0 
indexMap: {(0,'A')}
startIndex:0
endIndex:0

--> add an element to the head 
//newCalculatedIndex = 0-1 = -1
indexMap: {(-1,'B'), (0,'A')}
startIndex:-1
endIndex:0

--> add an element to the tail 
newCalculatedIndex = startIndex == endIndex ? endIndex : endIndex + 1; 
//newCalculatedIndex = 0 + 1 = 1
indexMap: {(-1,'B'), (0,'A'), (1,'C')}
startIndex:-1
endIndex:1

--> Access element with index 2:
calculatedIndex = -1 + 2 = 1 -> indexMap.get(1) returns 'C'

Answer 3

The ArrayDeque API doesn't provide any way to do this.

However, you could write a custom subclass of ArrayDeque that implements get. Something like this:

public E get(int i) {
    if (i < 0 || i > size()) {
        throw new ....("out of bounds");
    }
    long pos = this.head + i; 
    if (pos >= this.elements.length) {
        pos -= this.elements.length;
    }
    return this.elements[(int) pos];
}

Note: this code has not been compiled / debugged. Use at your own risk!

This is O(1) and has no impact on the performance of the existing operations in the ArrayDeque API.

---

UPDATE

The above won't work as a subclass of the standard ArrayDeque class because the fields it is accessing are package private. However, you could copy the original class and add the above method to the copy.

(Just make sure that you copy the code from the OpenJDK codebase, and satisfy the GPLv2 requirements.)