ArrayDeque vs ArrayList to implement a stack

Question

The documentation for ArrayDeque says:

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

There is no mention of the difference between using an ArrayDeque as a stack and using an ArrayList. You can use an ArrayList as a stack as follows.

list.add(object);                      // push
object = list.remove(list.size() - 1); // pop

I found that when I used an ArrayList in this way only, its performance is worse than ArrayDeque. What accounts for this difference? Surely, it can't just be the calls to size()? Internally, both ArrayList and ArrayDeque are implemented using an Object[] that is replaced by a larger array when required, so surely the performance should be about the same?

Answer 1

The main difference between both implementation is the resize strategy

• ArrayList is resized to a new size of oldCapacity + (oldCapacity >> 1), resulting in an increse of ~50%. The default capacity is 10, resulting in a capacities after resize of 15, 22, 33, 49, 73, 109, 163, 244, 366...

• ArrayDeque is always resized to a power of 2. On resize, the capacity is doubled. Starting with the default of 16, the resuling capacities after resize are 32, 64, 128, 256,...

So the ArrayDeque reaches higher capacities with much less resize operation, which are costly because of array copy. I.e. to store 256 in default-sized ArrayList, it requires 9 resize calls, while the ArrayDeque only need 4. Array copy may be fast, but may also require a GC to free some space for the new data sets, in addition to the memory copy costs (where the ArrayDeque might also perform better due to it's alignment to power-of-2).

Both datastructures have best-case complexity of O(1) for push and pop through direct access on either head & tail (ArrayDequeue) respectively add and remove(Last) size (ArrayList)

Answer 2

To answer the question, let's compare the remove methods of the ArrayList and ArrayDeque classes.

ArrayList remove method

public E remove(int index) {
    this.rangeCheck(index);
    ++this.modCount;
    E oldValue = this.elementData(index);
    int numMoved = this.size - index - 1;
    if (numMoved > 0) {
        System.arraycopy(this.elementData, index + 1, this.elementData, index, numMoved);
    }

    this.elementData[--this.size] = null;
    return oldValue;
}

ArrayDeque removeLast method

 public E removeLast() {
    E x = this.pollLast();
    if (x == null) {
        throw new NoSuchElementException();
    } else {
        return x;
    }
}

ArrayDeque removeLast method calling pollLast method

    public E pollLast() {
    int t = this.tail - 1 & this.elements.length - 1;
    E result = this.elements[t];
    if (result == null) {
        return null;
    } else {
        this.elements[t] = null;
        this.tail = t;
        return result;
    }
}

Let's explain the ArrayList remove method step by step:

1. Check if the entered index is within the limits of the array
2. Increment the ModCount variable by one.
3. Store the value to be deleted.
4. Determine how many numbers to move (in our example, numMoved 0 is found because the last element will be deleted).
5. Copy the array if the number to move is greater than 0 (the copy will not be performed because numMoved 0 is found).
6. Assign null to the last element of the array.
7. Return the deleted value.

Let's explain the ArrayDeque removeLast method step by step (it will suffice to explain the pollLast method):

1. Find the last index of the array
2. Return the value of the last element of the array.
3. Return null if the value of the last element is equal to null.
4. İf the value of the last element is not null (if it is not null, the following steps will occur).
5. Assign null to last element
6. Update the value of the tail variable
7. Return result

When we compare the steps, there is no noticeable difference in terms of performance. In our example, ArrayList's System.copyarray method will not work because we deleted the last element. If this method had worked, there would have been a performance difference. In conclusion there is no difference to be considered other than @Gerald Mücke's answer. If the element to be deleted was the first element of the list then there would be a performance difference. When we want to delete the first element, we can use the removeFirst method of the ArrayDeque class. (The removeFirst method works similarly to the removeLast method). When we want to delete the first element in ArrayList, we can use the remove(0) method. When we delete the ArrayList with 0 index, this time the array copy(System.copyarray) will be done. We used to say that ArrayList is slower because of the array copying process.