Re: Merging Linked Lists
Damo writes:
>> I (will) have anythng up to 6 Linked Lists of strings. I want to merge
>> them and remove duplicate entries at the same time.
Daniel Dyer wrote:
> Is LinkedList the best data structure for your needs? Perhaps a Set
> would be better if you need no duplicates and don't care about sorting?
Daniel Pitts wrote:
> Is there any reason not to use a Set instead?
Daniel Pitts wrote:
So. My professional suggestion is to make all of your types "Set" (or
"Collection" is better, depending on what you need to do), and
instantiate with "new HashSet()".
Lee Weiner wrote:
> The whole reason for a Set to exist is to eliminate duplicates. That's what
> they do, that's all they do. AFAIC, a Set is the most efficient tool for
> your requirement.
Daniel Pitts wrote:
> Actually, a set is likely more efficient in some ways. Also, they are
> for much more than just eliminating duplicates.
>
> For example, they are also for efficient "contains" checks.
Patricia Shanahan wrote:
> Damo wrote:
>> My plan was to iterate through the lists , if the first list contains
>> the current item in the second list,skip it or else insert it into the
>> corrsponding position in the first list.
>> this should I think return one List with no duplicates
>
> That sounds like an O(n*n) method for merging two lists, each containing
> n elements, even if you use iterators.
>
> Sort-and-merge is O(n log n). You only have to look at the head elements
> of each list, move the smaller to the result, dropping any duplicates
> from either list.
>
> Dumping all the data into a HashSet is O(n). It is also VERY simple to
> code, using addAll.
Jhair Tocancipa Triana wrote:
If you don't want duplicates, what about using Sets instead of a
Lists?
Get the hint??
- Lew