• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Ron McLeod
  • Jeanne Boyarsky
Sheriffs:
  • Paul Clapham
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Need help in List

 
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I want to compare List A and List B and list down all the elements which are present only in List A not in List B.
One way i can do this using contains() method of List interface and other by sorting the List B and then apply binary search on each element.
Among these to which one will be faster or there any other logic where this comaprision can be performed efficiently???
 
Ranch Hand
Posts: 513
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Chethan,

If you maintain both List A and List B in sorted order, there's a simple linear-time algorithm for doing what you want. It's easier to demonstrate it than to explain it in words:

If your program can guarantee that both lists will always be kept in sorted order, then this algorithm should yield faster asymptotic performance than the algorithms you described. However, if you can't guarantee that, then you'll need to sort both lists before using this algorithm, in which case this may or may not be faster than your algorithms. It also won't work if your list elements aren't Comparable.
[ December 06, 2007: Message edited by: Kelvin Lim ]
 
Chethan C Gowda
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Kelvin,
The list which i have is unsorted, as you said i dont think ill get better performance if i sort two lists and then applying comapreTo().
Im iterating one list by comparing its element against other list using contains().
Thanks for your reply
 
We cannot change unless we survive, but we will not survive unless we change. Evolving tiny ad:
Clean our rivers and oceans from home
https://www.kickstarter.com/projects/paulwheaton/willow-feeders
reply
    Bookmark Topic Watch Topic
  • New Topic