File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Need help in List Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Need help in List" Watch "Need help in List" New topic

Need help in List

Chethan C Gowda

Joined: Dec 06, 2007
Posts: 22
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???

Kelvin Chenhao Lim
Ranch Hand

Joined: Oct 20, 2007
Posts: 513
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 ]

SCJP 5.0
Chethan C Gowda

Joined: Dec 06, 2007
Posts: 22
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
I agree. Here's the link:
subject: Need help in List
It's not a secret anymore!