1

Is there a way to first sort then search for an objects within a linked list of objects. I thought just to you one of the sorting way and a binary search what do you think? Thanks

gbox
  • 809
  • 1
  • 8
  • 22
  • 2
    Binary search will not work well with a linked list. You need random access for that. – Thilo Feb 02 '10 at 05:13
  • According to the API docs, `binarySearch` for large linked lists will do O(log n) comparisons with O(n) link traversals. A naive algorithm would do O(n log n) link traversals. – Tom Hawtin - tackline Feb 02 '10 at 05:32
  • Are you doing this to construct a computer performance benchmarking routine and that you need to put in as many highly inefficient obstacles as possible to test the efficient performance of cpus? – Blessed Geek Feb 02 '10 at 06:13
  • See also http://stackoverflow.com/questions/7685/merge-sort-a-linked-list – finnw Feb 02 '10 at 17:37

3 Answers3

5

This is not a good approach, IMO. If you use Collections.sort(list), where the list is a LinkedList, this copies the list to a temporary array, sorts it, and then copies back to the list' i.e. O(NlogN) to sort plus 2 * O(N) copies. But when you then try to do an binary search (e.g. using Collections.binarySearch(list), each search will do O(N) list traversal operations. So you may as well have not bothered sorting the list!

Another approach would be to convert the list to an array or an ArrayList, and then sort and search that array / ArrayList. That gives one copy plus one sort to setup, and O(logN) for each search.

But neither of these is the best approach. That depends on how many times you need to perform search operations.

  • If you simply want to do one search on the list, then calling list.contains(...) is O(N) ... and that is better than anything involving sorting and binary searching.

  • If you want to do multiple searches on a list that never changes, you're probably better off putting the list entries into a HashSet. Constructing a HashSet is O(N) and searching is O(1). (This assumes you don't need your own comparator.)

  • If you want to do multiple searches on a list that keeps changing where the order IS NOT significant, replace the list with a HashSet. The incremental cost of updating the HashSet will be O(1) for each addition/removal, and O(1) for each search.

  • If you want to do multiple searches on a list that keeps changing and the order IS significant, replace the list with an insertion-ordered LinkedHashMap. That will be O(1) for each addition/removal, and O(1) for each search ... but with large constants of proportionality than for a HashSet.

Stephen C
  • 698,415
  • 94
  • 811
  • 1,216
3
  • java.util.Collections#sort()
  • java.util.Collections#binarySearch()

The Collections class has lots of other amazing methods to make programmers life easier.

Note that the sort method's implementation will indeed convert the list to array, but from you need not explicitly convert the list in to array before calling the method:)

Suraj Chandran
  • 24,433
  • 12
  • 63
  • 94
  • Note that these methods will dump the whole list into an array first, and then reconstitute the list. So this is not a algorithm specific for linked lists. – Thilo Feb 02 '10 at 05:16
  • @Thilo - that is correct. It "works", but if you do this naively on a linked list, the performance will be *worse* than if you simply called `java.util.List#contains()`!! – Stephen C Feb 02 '10 at 07:34
1

You may want to question if searching over a sorted list is the best option for your use-case as this does not perform well. The list sort is O(NlogN) and the binary search is O(logN). You might consider making a Set out of your list elements and then searching that via the contains method, which is O(1), if you just want to see if an element exists. It would be much easier to give you some advice on what collection you might consider if you could explain more about your use-case.

EDIT: Consider performance issues of List sorting if you plan to do this for large lists.

harschware
  • 13,006
  • 17
  • 55
  • 87
  • Note that java's sort() method uses a modified version of merge sort – Suraj Chandran Feb 02 '10 at 05:30
  • @Suraj - that probably doesn't matter. The more important issue is understanding your use case and picking the most appropriate approach. The difference between the most appropriate and least appropriate approaches *could* be as much as `O(N**2)` ... and that's a BIG difference! – Stephen C Feb 02 '10 at 07:41