By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
429,514 Members | 1,308 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 429,514 IT Pros & Developers. It's quick & easy.

Priority queue based on a sorted linked list

P: 8
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?
May 18 '08 #1
Share this Question
Share on Google+
3 Replies


Expert 100+
P: 849
Well...Java has a PriorityQueue class builtin that derives from LinkedList...unless 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.
May 18 '08 #2

BigDaddyLH
Expert 100+
P: 1,216
Well...Java has a PriorityQueue class builtin that derives from LinkedList...
Really? 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. Why use a linked list in the first place?
May 18 '08 #3

Expert 100+
P: 849
Really? 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. Why use a linked list in the first place?
That's what I get for going off memory rather than looking at the API...;)
May 18 '08 #4

Post your reply

Sign in to post your reply or Sign up for a free account.