Hello,
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.
Thank you!
You should implement both and then do performance testing on actual data to see which works best in your specific circumstances.
If you use a LinkedList, you would need to resort the items each time you added one and since inserts are frequent, I wouldn't use a LinkedList. So in this case, I would use a PriorityQueue's If you will only be adding unique elements to the list, I recommend using a SortedSet (one implementation is the TreeSet).
Do you need it sorted at all times? If that's the case, you might want to go with something like a tree-set (or other SortedSet with a fast lookup).
If you only need it sorted occasionally, go with a linked list and sort it when you need access. Let it be unsorted when you don't need access.
java.util.PriorityQueue is
"An unbounded priority queue based on a priority heap"
. The heap data structure make much more sense than a linked list
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.
There is a fundamental difference between the two data structures and they are not as easily interchangeable as you might think.
According to the PriorityQueue documentation:
The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.
Use an ArrayList and call Collections.sort() on it only before iterating the list.
The issue with PriorityQueue is that you have to empty the queue to get the elements in order. If that is what you want then it is a fine choice. Otherwise you could use an ArrayList that you sort only when you need the sorted result or, if the items are distinct (relative to the comparator), a TreeSet. Both TreeSet and ArrayList are not very 'heavy' in terms of space; which is faster depends on the use case.
I can see two options, which one is better depends on whether you need to be able to have duplicate items.
If you don't need to maintain duplicate items in your list, I would use a SortedSet (probably a TreeSet).
If you need maintain duplicate items, I would go with an LinkedList and insert new items into the list in the correct order.
The PriorityQueue doesn't really fit unless you want to remove the items whenever you do operations.
Going along with the others, make sure you use profiling to make sure you're picking out the correct solution for your particular problem.