msr msr - 4 months ago 12
Java Question

Java - PriorityQueue vs sorted LinkedList

Which implementation is less "heavy": PriorityQueue or a sorted LinkedList (using a Comparator)?

I want to have all the items sorted. The insertion will be very frequent and ocasionally I will have to run all the list to make some operations.

Answer

A LinkedList is the worst choice. Either use an ArrayList (or, more generally, a RandomAccess implementor), or PriorityQueue. If you do use a list, sort it only before iterating over its contents, not after every insert.

One thing to note is that the PriorityQueue iterator does not provide the elements in order; you'll actually have to remove the elements (empty the queue) to iterate over its elements in order.

Comments