Dart中DoubleLinkedQueue和ListQueue有什么区别？

Question

Dart核心API有两个实现Queue<E>接口的类，DoubleLinkedQueue<E>和ListQueue<E>。

这两个类的文档几乎相同，唯一明确提到的区别是ListQueue<E>文档中的以下注释：

removeAll和removeWhere等操作非常低效。如果需要这些操作，请改用DoubleLinkedQueue。

从实现上讲，它们之间的实际区别是什么？应该使用哪种实现？

- Steven Roose

---

我个人认为Queue不应该有removeWhere或removeAll方法；这不是队列的一部分。我认为这是一个糟糕的设计。当然，这并没有回答你关于它们之间区别的问题，这就是为什么这只是一条评论而不是答案。 - Levi Morrison

是的，LinkedList 类也相当奇怪。它要求列出的元素扩展某个类。并不是真正的通用实现。我也看不出 Queue 和 LinkedList 之间有什么区别。 - Steven Roose

Answer 1

DoubleLinkedQueue是基于双向链表实现的队列。这意味着在任意位置移除元素很快，因为只需要调整指针。

ListQueue是基于列表实现的队列。首尾是索引。通常来说，这是更有效的实现，因为它比双向链表具有更少的内存开销。

你可以在这里看到两种实现方式。

大多数情况下，你应该使用ListQueue。出于这个原因，Queue接口默认使用ListQueue(即Queue()返回一个ListQueue)。

DoubleLinkedQueue实现主要用于需要选择性地在队列内部删除元素的情况。这是相对较少见的场景，该类存在于dart库中的主要原因是在ListQueue之前就有了DoubleLinkedQueue。由于我们已经有了DoubleLinkedQueue，所以我们保留了它。如果我们一开始就使用ListQueue，可能就不会添加DoubleLinkedQueue了。

- Florian Loitsch