为什么ArrayList不实现Queue？

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]

现在; 使用a ArrayList,remove操作将是O(n)- 我会想象API设计者认为这种性能是不可接受的.

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

ArrayDeque是一个不同的设计来支持这一点O(1)- 因此它不是一个List.