Priority queue based on a sorted linked list

[morris11]

I want to implement a priority queue based on a sorted linked list. The remove operation on the priority queue should remove the item with a smallest key. Can anybody give me an idea how to do that?

[Laharl]

Well...Java has a PriorityQueue class builtin that derives from LinkedList...un less this is an academic excercise, in which case you need to work out how to sort a linked list even remotely efficiently. I recommend a variation on Selection Sort, though swapping is a little more complicated than it would be in an array. Once sorted, the smallest item should be the front node.

[BigDaddyLH]

Well...Java has a PriorityQueue class builtin that derives from LinkedList...

Really? java.util.Prior ityQueue is "An unbounded priority queue based on a priority heap". The heap data structure make much more sense than a linked list. Why use a linked list in the first place?

[Laharl]

Really? java.util.Prior ityQueue is "An unbounded priority queue based on a priority heap". The heap data structure make much more sense than a linked list. Why use a linked list in the first place?

That's what I get for going off memory rather than looking at the API...;)