What's the difference between a DoubleLinkedQueue and a ListQueue in Dart?

Question

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?

Answer 1

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.