What's the difference between a DoubleLinkedQueue and a ListQueue in Dart?
dart, iterator, linked-list, list, queue
Solution
The `DoubleLinkedQueue` is basically a Queue implemented on top of a double-linked list. This means that removing elements at arbitrary positions in it is fast, since it only requires the adjustment of pointers.
The `ListQueue` is implemented on top of a List. First and last are indices into the list. In general this is the more efficient implementation, since it has less memory-overhead than the double-linked list.
You can see both implementations here
Most of the time you want to use the `ListQueue`. For that reason, the `Queue` interface defaults to the ListQueue (i.e. `Queue()` returns a `ListQueue`).
The `DoubleLinkedQueue` implementation is mostly useful if you need to selectively remove elements inside the queue. It's a relatively rare scenario, and the main-reason the class is in the dart-libraries, is that the `DoubleLinkedQueue` existed before the `ListQueue`. Since we already had the `DoubleLinkedQueue` we kept it. If we had started out with the ListQueue we probably wouldn't have added the `DoubleLinkedQueue`.
Problem
The Dart core API has two classes that implement the `Queue<E>` interface, `DoubleLinkedQueue<E>` and `ListQueue<E>`. The documentation of both classes is almost identical, the only difference that is explicitly mentioned is the following note in the `ListQueue<E>` documentation: Operations like `removeAll` and `removeWhere` are very inefficient. If those are needed, use a `DoubleLinkedQueue` instead. What is the actual difference between them implementation-wise and when should which implementation be used?