Java - PriorityQueue vs sorted LinkedList

Question

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 1

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.

Answer 2

You should implement both and then do performance testing on actual data to see which works best in your specific circumstances.