ArrayList VS ArrayDeque in shifting elements?

Question

I tried asking a similar question, but I failed to receive any satisfying answer. The motivation behind this question is this question's first (accepted) answer that roughly says:

ArrayDeque doesn't have the overhead of shifting contents like ArrayList.

From my point of view, they should act the same. The only difference is that ArrayList is implemented from List interface, meaning it can access any arbitrary index. On the other side, ArrayDeque is implemented from Queue interface and it works in LIFO/FIFO manner.

The thing I want to point is that they both use AN ARRAY to store elements. Meaning if they both had an array with these elements:

2, 4, 6, 8, 10

, doing arraylist.remove(0); and arraydeque.poll(); should both remove first/head element with value 2.

Now my big question. Do all those left numbers (4,6,8,10) get shifted to left for 1 slot in both cases? Is there any difference between ArrayList and ArrayDeque in way how they shift elements when we do any structure modification?

Answer 1

In ArrayList, each of the elements gets shifted over.

In ArrayDeque, the elements don't move in the array. The pointer in the array that says where the current head of the queue is gets moved over.

(Why doesn't ArrayList do this, you might ask? It could conceivably do it, but it'd only work for inserting/removing elements at the beginning and end, not in the middle. ArrayList isn't really designed to be used that way -- if you're doing that, then you have a queue/deque, so you might as well use ArrayDeque.)

Answer 2

ArrayDeque maintains a small internal array of size 16, and maintains the pointer to head and tail until its size reach its limit. Once it reach it limits, it will double the size of the array. All the operations, we do on ArrayDeque are managed with head and tail pointers in hand.

But in case of ArrayList, majority of operations are using index of array. And it starts from 0. So in case of ArrayList it has to move all elements of ArrayList if we remove first element from it to maintain its index. That is not a challenge for ArrayDeque, it can just update the pointer of tail or head depends on from where we are removing the item.