在这种情况下,ArrayDeque
是否应该优于 LinkedList
?
Why is ArrayDeque better than LinkedList .
在我看来,我应该使用 LinkedList 而不是 ArrayDeque,因为有相当多的 poll
和 offer
该算法中正在进行操作,并且不存在对元素的随机访问。
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode a) {
Queue<TreeNode> q = new LinkedList<>(); // new ArrayDeque<>() ???
q.offer(a);
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
while (q.peek() != null){ //returns null if empty
ArrayList<Integer> list = new ArrayList<>();
int n = q.size();
for (int i = 0; i < n; i++){
TreeNode node = q.poll();
list.add(node.val);
if (node.left != null) {
q.offer(node.left);
}
if (node.right != null) {
q.offer(node.right);
}
}
ans.add(list);
}
return ans;
}
最佳答案
在将 ArrayDeque
和 LinkedList
视为双端队列时,需要权衡取舍。
一般来说,LinkedList
类型有以下优点:
- 添加元素的成本是最坏情况下的 O(1),因此任何单个插入都不会花费太多时间。
- 从末端删除一个元素的成本是最坏情况下的 O(1),因此任何单个删除都不会花费太多时间。
一般来说,LinkedList
类型有以下主要缺点:
- 因为
LinkedList
中的元素不一定连续存储在内存中,LinkedList
的引用局部性差,访问可能会导致更多缓存未命中,从而降低性能。
一般来说,ArrayDeque
类型有以下优点:
- 由于元素是连续存储的,
ArrayDeque
具有很好的引用局部性,因此元素访问通常会造成很少的缓存未命中,从而带来出色的性能。
一般来说,ArrayDeque
有以下缺点:
- 虽然
ArrayDeque
上的任何 n 操作序列都需要时间 O(n),但当插入时超出数组容量时,ArrayDeque
可能必须执行O(n) 复制元素。因此,ArrayDeque
每次操作的最坏情况性能比LinkedList
慢。 - 类似地,如果数组容量在删除时下降得太低,则可能需要 O(n) 的时间来调整数组的大小,但是,和以前一样,
ArrayDeque
上的任何一系列 n 操作都会花费时间 O(n)。
在您的特定用例中,由于您关心的只是层序遍历的端到端效率,而不是从队列中单独添加或删除元素的成本,因此可能会更快使用 ArrayDeque
而不是 LinkedList
。从某种意义上说,LinkedList
类型通常只有在您需要对执行的每个操作都具有良好的最坏情况性能时才更好,而这里不是这种情况。当您只关心端到端运行时时,ArrayDeque
通常性能更高。
希望这对您有所帮助!
关于java - ArrayDeque vs LinkedList as Queue 进行层序遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56767560/