How to create a list of differences based on two other lists and include duplicates

Question

I have two lists

List<string> list1 as new List<string>();

and

List<string> list2 as new List<string>();

What I want to do is create a third list that is a list of differences.

Example: list1 contains (Test1, Test2, Test3, Test4) list2 contains (Test1, Test3)

I would want my new list to contain (Test 2, Test4)

I tried using

newlist = list1.Except(list2).ToList();

and for the above example it works fine.

Example 2: list 1 contains (Test1, Test1, Test2, Test2) list 2 is empty

I want my newlist to contain everything (Test1, Test1, Test2, Test2)

If I use the same Except method I was using above I get in my newlist (Test1, Test2)

Is there a way I can include the duplicates?

One more final example so it is hopefully clear on what I am looking for list1 contains (Test1, Test2, Test2, Test3, Test4) list2 contains (Test1, Test2, Test5, Test6)

I would want my newlist to contain (Test2, Test3, Test4, Test5, Test6)

One more thing is that list1 and list2 are in no particular order and newlist does not need to be in any particular order either.

Answer 1

I think getting what you are looking for here is going to be really hard to do with an out of the box. Really what you need to do is "summarize" both lists something like a count of each item, then from there, do a different on items, THEN a difference on counts.

Answer 2

You'll have to write this one yourself. The way Except probably works is by putting all of the elements from the first collection into the equivalent of aHashSet<T> and removing every item that's in the second.

What I'd do is something similar: put everything from the first collection into aDictionary<T, int> with values corresponding to occurrence counts. Enumerating over the second collection, subtract from these counts. Then reconstruct a list from the updated counts after subtraction.

Does that make sense?

Answer 3

UPDATE: I have compressed my previous code into something a little smaller:

var list1 = new List<string>() { "Test1", "Test2", "Test2", "Test3", "Test4" };
var list2 = new List<string>() { "Test1", "Test2", "Test5", "Test6" };

var newlist = new List<string>();
list1.ForEach(delegate(string s) { if (!list2.Remove(s)) newlist.Add(s); });
newlist = newlist.Concat(list2).ToList();