Why ArrayList doesn't implements Queue?

Question

Maybe it's silly, but I have to know the answer. I am scratching my head looking at its source code and doesn't see any reason why authors implement Queue in LinkedList, but decided not to do the same with ArrayList, instead they have created separate class ArrayDeque.

Answer 1

The interface Queue requires that add adds items to the end of the Queue and remove takes elements from the start of the Queue.

(pseudo code)

Queue<String> q = ...
q.add("A")
q.add("B")
q.add("C")
//q is now [A,B,C]
String a = q.remove()
// a is A and q is [B, C]

Now; with an ArrayList, the remove operation would be O(n) - I would imagine that the API designers decided that this performance is unacceptable.

remove is O(n) because it requires reindexing the whole list - B is now 0 and C is now 1. LinkedList does not have this problem as it uses a linked list datastructure; it just remove the head node and sets the child of that node to be the new head node.

ArrayDeque is a different design to support this in O(1) - it is therefore not a List.

Answer 2

Most likely because it wouldn't be very performant as a Queue, since adding to (well, removing from in the case of Queue) the beginning is an O(N) operation instead of O(1). ArrayDeque on the other hand is a different design, since it's not a List and therefore doesn't need to provide random access.