java - 为什么 ArrayList 没有实现 Queue？

Question

也许这很愚蠢，但我必须知道答案。我在看它的源代码时抓耳挠腮，没有看到作者在 LinkedList 中实现 Queue 的任何原因，但决定不对 ArrayList 做同样的事情，相反，他们创建了单独的类 ArrayDeque。

Answer 1

接口(interface) Queue 要求 add 将项目添加到 Queue 的末尾，remove 从中获取元素队列的开始。

(伪代码)

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 设计者认为这种性能是 Not Acceptable 。

remove 是 O(n) 因为它需要重新索引整个列表 - B 现在是 0 并且C 现在是 1。 LinkedList 没有这个问题，因为它使用链表数据结构；它只是删除头节点并将该节点的子节点设置为新的头节点。

ArrayDeque 是在 O(1) 中支持此功能的不同设计 - 因此它不是 List。