Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

LinkedList and Comparator

 
Lio Liov
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I figure it out !!!
Thanks
I made a
priorityqueue with comparator and now I am trying to convert it to Linked list with comparator
Is it possible at all and How can I do it
Thas how I wass creating the priority queue with comparator .How can I create new LinkedList with comparator
Thanks


 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lio Liov wrote:How can I create new LinkedList with comparator

You can't.

Maintaining a natural ordering is not one of the jobs that LinkedList is best suited for. LL will NOT impose an ordering by itself, so you would have to sort it every time the contents changed. If you need that functionality there are better data structures to use.
 
Lio Liov
Ranch Hand
Posts: 33
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks
I think I did it
It might not be very efficient but works
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dennis Deems wrote:
Lio Liov wrote:How can I create new LinkedList with comparator

You can't.


Well...



Not saying its a good idea, but it IS-A LL, and is uses a Comparator to maintain a sorted order.

A better approach to a SortedList would be involve Preferring Composition Over Inheritance.

Maintaining a natural ordering is not one of the jobs that LinkedList is best suited for. [...] If you need that functionality there are better data structures to use.


Absolutely.
 
Winston Gutkowski
Bartender
Pie
Posts: 10498
64
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lio Liov wrote:Thanks
I think I did it
It might not be very efficient but works

Yup. That'll do it, and it's very clear - but you're right, it won't be quick.
An alternative, if your list is likely to get large is:
(basically a dump-sort-and-reload, which will minimize the sort portion).

But I wouldn't bother unless you find performance is an issue.

HIH

Winston

[Edit] There is also a Skip List, which will maintain an order. Unfortunately, the only implementations provided by the standard libraries are as a java.util.Set or java.util.Map. It's possible that someone like Apache has a List implementation though.
 
Jesper de Jong
Java Cowboy
Saloon Keeper
Pie
Posts: 15438
41
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:[Edit] There is also a Skip List, which will maintain an order. Unfortunately, the only implementations provided by the standard libraries are as a java.util.Set or java.util.Map. It's possible that someone like Apache has a List implementation though.

The standard library has java.util.concurrent.ConcurrentSkipListMap and java.util.concurrent.ConcurrentSkipListSet
 
dennis deems
Ranch Hand
Posts: 808
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Lio Liov wrote:It might not be very efficient but works


Winston Gutkowski wrote:
Yup. That'll do it, and it's very clear - but you're right, it won't be quick.


A greater concern to me would be remembering, everywhere something is added to the list, that it needs to be sorted again.
 
Rob Spoor
Sheriff
Pie
Posts: 20608
63
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Winston Gutkowski wrote:An alternative, if your list is likely to get large is:
(basically a dump-sort-and-reload, which will minimize the sort portion).

Collections.sort returns void, so you should extract creating the copy to before the sorting:
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dennis Deems wrote:
Lio Liov wrote:It might not be very efficient but works


Winston Gutkowski wrote:
Yup. That'll do it, and it's very clear - but you're right, it won't be quick.


A greater concern to me would be remembering, everywhere something is added to the list, that it needs to be sorted again.


Which would be why one might define a SortedList that delegates to another List, which in turn does a binary-search-and-insert on add(), and then use that SortedList everywhere you'd otherwise have to remember to sort on add(). (This would also alleviate some of the performance hit from add();sort();
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic