Java - PriorityQueue vs sorted LinkedList

java sorting linked-list priority-queue
rasgo picture rasgo · May 20, 2010 · Viewed 18.7k times · Source

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

erickson picture erickson · May 21, 2010

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.

Related questions

Sorting a linked list in Java

I have written a bubble sort algorithm to sort a linked list. I am a Java beginner and trying to learn data structures. I am confused why my second element is not sorted properly. EDIT class SListNode { Object item; SListNode …

Read More
sorting a doubly linked list with merge sort

I have found this code in the internet and it was for arrays ,I want to change it for doubly linked list(instead of index we should use pointer) would you please help me that how can i change merge …

Read More
Sort a Map<Key, Value> by values

I am relatively new to Java, and often find that I need to sort a Map<Key, Value> on the values. Since the values are not unique, I find myself converting the keySet into an array, and sorting …

Read More