Merge lists

[Tem]

List<int> a = new List<int>();
a.Add(1);
a.Add(2);
a.Add(3);

List<int> b = new List<int>();
b.Add(3);
b.Add(4);
b.Add(5);


What's the best way to merge 2 lists with no duplicate elements? the merged
list would have 5 elements 1,2,3,4,5

 

[Tem]

Best = easiest/most efficient

b could be merged into a or to a new int List
List<int> c

it has to be the same type so can't use a dictionary

[...]
What's the best way to merge 2 lists with no duplicate elements? the
merged list would have 5 elements 1,2,3,4,5

Define "best way" and "merged".

Is the input already sorted (as in your example)? Then a merge sort would
work well. Google can help you find details on the algorithm.

If the data's not already sorted, it might make more sense to use a
dictionary, to which you add every element of one list, and then iterate
the other list, adding to the dictionary only those elements that aren't
already in the dictionary. Then all of the values in the dictionary would
be your final collection.

If the lists are especially large and memory capacity is likely to be an
issue, then it may be better to just sort the lists and do the merge sort
solution.

It's really hard to say for sure what approach is literally the "best"
with only the information you've provided here.

Pete

 

[Tem]

Best = easiest/most efficient

b could be merged into a or to a new int List
List<int> c

it has to be the same type so can't use a dictionary

[...]
What's the best way to merge 2 lists with no duplicate elements? the
merged list would have 5 elements 1,2,3,4,5

Define "best way" and "merged".

Is the input already sorted (as in your example)? Then a merge sort would
work well. Google can help you find details on the algorithm.

If the data's not already sorted, it might make more sense to use a
dictionary, to which you add every element of one list, and then iterate
the other list, adding to the dictionary only those elements that aren't
already in the dictionary. Then all of the values in the dictionary would
be your final collection.

If the lists are especially large and memory capacity is likely to be an
issue, then it may be better to just sort the lists and do the merge sort
solution.

It's really hard to say for sure what approach is literally the "best"
with only the information you've provided here.

Pete

 

[Peter Bromberg [C# MVP]]

"it has to be the same type so can't use a dictionary".....
Isn't a generic Dictionary strongly typed when you instantiate it? This
doesn't make sense.
-- Peter
To be a success, arm yourself with the tools you need and learn how to use
them.

Site: http://www.eggheadcafe.com
http://petesbloggerama.blogspot.com
http://ittyurl.net

 

[Tem]

Is the input already sorted (as in your example)? Then a merge sort
No the list is in random order but all its elements are unique. The ordering
of the output doesn't matter but the elements has to be unique, no
duplicates

Best = easiest/most efficient

b could be merged into a or to a new int List
List<int> c

it has to be the same type so can't use a dictionary

[...]
What's the best way to merge 2 lists with no duplicate elements? the
merged list would have 5 elements 1,2,3,4,5

Define "best way" and "merged".

Is the input already sorted (as in your example)? Then a merge sort
would
work well. Google can help you find details on the algorithm.

If the data's not already sorted, it might make more sense to use a
dictionary, to which you add every element of one list, and then iterate
the other list, adding to the dictionary only those elements that aren't
already in the dictionary. Then all of the values in the dictionary
would
be your final collection.

If the lists are especially large and memory capacity is likely to be an
issue, then it may be better to just sort the lists and do the merge sort
solution.

It's really hard to say for sure what approach is literally the "best"
with only the information you've provided here.

Pete

 

[Gilles Kohl [MVP]]

List<int> a = new List<int>();
a.Add(1);
a.Add(2);
a.Add(3);

List<int> b = new List<int>();
b.Add(3);
b.Add(4);
b.Add(5);


What's the best way to merge 2 lists with no duplicate elements? the merged
list would have 5 elements 1,2,3,4,5

As others have stated, you haven't provided enough details on what can
be assumed about the input lists, and the requirements for the
resulting list, to suggest an optimal (and correct) solution. If you
target .NET 3.5 though, you may want to check if this fits the bill:

List<int> c = Enumerable.Union(a, b).ToList();

Regards,
Gilles.

 

[SMJT]

No the list is in random order but all its elements are unique. The ordering
of the output doesn't matter but the elements has to be unique, no
duplicates

Best = easiest/most efficient

b could be merged into a or to a new int List
List<int> c

it has to be the same type so can't use a dictionary

[...]
What's the best way to merge 2 lists with no duplicate elements? the
merged list would have 5 elements 1,2,3,4,5
Define "best way" and "merged".
Is the input already sorted (as in your example)?  Then a merge sort
would
work well.  Google can help you find details on the algorithm.
If the data's not already sorted, it might make more sense to use a
dictionary, to which you add every element of one list, and then iterate
the other list, adding to the dictionary only those elements that aren't
already in the dictionary.  Then all of the values in the dictionary
would
be your final collection.
If the lists are especially large and memory capacity is likely to be an
issue, then it may be better to just sort the lists and do the merge sort
solution.
It's really hard to say for sure what approach is literally the "best"
with only the information you've provided here.
Pete- Hide quoted text -

- Show quoted text -

Tem

Any reason why you can't just merge as follows;

List<int> a = new List<int>();
a.Add(1);
a.Add(2);
a.Add(3);
List<int> b = new List<int>();
b.Add(3);
b.Add(4);
b.Add(5);

List<int> c = new List<int>();
foreach (var item in a)
{
if (!c.Contains(item))
c.Add(item);
}
foreach (int item in b)
{
if (!c.Contains(item))
c.Add(item);
}

The contains calls the equals method, so if your Lists contains
soemthing more complicated than an ordinal type, such as an int you
will have to code your own Equals methods.

Or have I missed something?

S1

 

[Tem]

I got it to work. thank you. I will choose my words more carefully next
time.

Tem

Any reason why you can't just merge as follows;

List<int> a = new List<int>();
a.Add(1);
a.Add(2);
a.Add(3);
List<int> b = new List<int>();
b.Add(3);
b.Add(4);
b.Add(5);

List<int> c = new List<int>();
foreach (var item in a)
{
if (!c.Contains(item))

This if() is superfluous. Tem has said that the original list elements
are unique, so no need to check for duplicates copying the first list.

c.Add(item);
}
foreach (int item in b)
{
if (!c.Contains(item))

Instead, it would be better to use "a.Contains()".

Using "c.Contains()" means the list being inspected gets longer and longer
with each addition. For very short lists, this won't matter much, but for
any non-trivial list it could mean a significant difference in execution
speed. Again, since the list elements are known to be unique, it's only
necessary to check against the other list, not the currently generated
list, and since the other list is always going to be shorter than the
currently generated list, that's a better choice.

Of course, I suppose one could argue that since this solution is pretty
much the least efficient approach to the problem, that fixing the if()
statements as noted above won't make much difference. In some respect,
that'd be true. But even if one is doing the least efficient solution, I
see no reason to make it even _less_ efficient than it nominally has to
be.

c.Add(item);
}

Tem: other than the comments above, I would say that this solution is the
easiest. Since you haven't been more specific about your requirement of
"best", and since "easiest" was one of the conditions you consider to
qualify for "best", I'd say that the above meets your criteria.

Again, "easiest" and "most efficient" are not always the same. The above
is a good example of this. The above would be among the least efficient
solutions.

But if your lists are short and/or ease of coding is more important that
performance, I don't see any reason to do anything more complicated.

Pete

 

[Lasse Vågsæther Karlsen]

List<int> a = new List<int>();
a.Add(1);
a.Add(2);
a.Add(3);

List<int> b = new List<int>();
b.Add(3);
b.Add(4);
b.Add(5);


What's the best way to merge 2 lists with no duplicate elements? the
merged list would have 5 elements 1,2,3,4,5

..NET 3.5 has a new HashSet<T> type that can be used for this:


--- cut here ---
using System;
using System.Collections.Generic;

namespace ShortAndComplete
{
class Program
{
static void Main(String[] args)
{
HashSet<Int32> hs1 = new HashSet<Int32>(new Int32[] { 1, 2,
3 });
HashSet<Int32> hs2 = new HashSet<Int32>(new Int32[] { 3, 4,
5 });
hs1.UnionWith(hs2);
foreach (Int32 value in hs1)
Console.Out.WriteLine(value);
Console.ReadLine();
}
}
}
--- cut here ---

If you're not using .NET 3.5, either use Dictionary as suggested by
others, or you can download and use my Set<T> class for .NET 2.0:

https://vkarlsen.serveftp.com:8443/svn/LVK/LVK_2_0/trunk/LVK.Core/Collections/Set.cs

username and password is both 'guest' without the quotes.

Note that by itself the Set class needs some resources for its exception
messages, but you can safely just replace those with something suitable,
if you decide to use it.