LinkedList and Comparator

[Lio Liov]

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

Comparator<Job> PrComparator = new PriorityComparator();
        LinkedList<Job>list=new LinkedList<Job>(10,PrComparator);

[dennis deems]

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]

Thanks
I think I did it
It might not be very efficient but works

Collections.sort(list,PrComparator);

[Jeff Verdegan]

Dennis Deems wrote:

Lio Liov wrote:How can I create new LinkedList with comparator

You can't.

Well...

public class SortedLinkedList<T> extends LinkedList<T> {
  private final Comparator<T> comparator;

  public SortedLinkedList(Comparator<T> comparator) {
    this.comparator = comparator;
  }

  public boolean add(T t) {
    // use Comparator for binary search
    // insert
  }

  // ... etc. ...
}

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]

Lio Liov wrote:Thanks
I think I did it
It might not be very efficient but works

Collections.sort(list,PrComparator);

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:

list = new LinkedList<Whatever>(
   Collections.sort(new ArrayList<Whatever>(list), PrComparator));

(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]

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]

Lio Liov wrote:It might not be very efficient but works

Collections.sort(list,PrComparator);

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]

Winston Gutkowski wrote:An alternative, if your list is likely to get large is:

list = new LinkedList<Whatever>(
   Collections.sort(new ArrayList<Whatever>(list), PrComparator));

(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:

list = new ArrayList<Whatever>(list);
Collections.sort(list, PrComparator);
list = new LinkedList<Whatever>(list);

[Jeff Verdegan]

Dennis Deems wrote:

Lio Liov wrote:It might not be very efficient but works

Collections.sort(list,PrComparator);

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();