Почему ArrayList не реализует очередность?

Question

Возможно, это глупо, но я должен знать ответ. Я почесываю голову, глядя на его исходный код и не вижу причин, по которым авторы применяют Queue в LinkedList, но решили не делать то же самое с ArrayList, вместо этого они создали отдельный класс ArrayDeque.

Answer 1

interface Queue требует, чтобы add добавляет элементы в конец Queue и remove берет элементы от начала Queue.

(псевдокод)

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] 

В настоящее время; с ArrayList, операция remove будет O(n) - Я бы предположил, что дизайнеры API решили, что эта производительность неприемлема.

remove является O(n), поскольку он требует переиндексации весь список - B теперь 0 и C теперь 1. LinkedList не имеет этой проблемы, так как использует связанный список datastructure; он просто удаляет головной узел и устанавливает дочерний узел этого узла в качестве нового головного узла.

ArrayDeque - это другая конструкция для поддержки этого в O(1) - поэтому это не List.

Answer 2

Скорее всего, потому что это будет не очень производительным как Queue, так как добавление к (ну, убрав из в случае Queue) начала это O(N) операция вместо O(1). ArrayDeque, с другой стороны, отличается от дизайна, поскольку он не является List и поэтому не требует произвольного доступа.