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

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?

Answers


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. new 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.


Need Your Help

iOS NSDate() returns incorrect time

ios swift nsdate

I am trying to get current date in Swift using NSDate(). When I create breakpoint and stop application, I can see that there is 3 hours difference with devices' system time. Application is running on

Invalid Cloudinary Configuration

node.js file config cloudinary keystonejs

I'm new to keystone and am trying to deploy a simple website template to familiarise myself with the technology, I have downloaded all the necassary modules and created a keystone.js file and package.