11

I have 2 lists: list1 and list2 (both of type int)

Now I want to remove content of list2 from list1. How I can do this in C#?

PS: Don't use loop.

7
  • 3
    If list1 contains 1, 2, 2, 3, 3, 4, 4, 5, and list2 contains 2, 3, 4, what should the result be? 1, 5, or 1, 2, 3, 4, 5?
    – millimoose
    Jan 17, 2013 at 22:03
  • Also, the restriction "don't use loop" is silly. Any builtin method that does this will use some sort of loop.
    – millimoose
    Jan 17, 2013 at 22:04
  • @millimoose It's probably some kind of assignment - there'll be a clause stating that the student can't use a loop.
    – Jeff
    Jan 17, 2013 at 22:06
  • @Arry, please note that all provided solutions will be use loops but implicitly. Jan 17, 2013 at 22:07
  • 1
    @Jeff Remove() returns a bool, so just: list1.RemoveAll(x=>list3.Remove(x))
    – millimoose
    Jan 17, 2013 at 22:16

4 Answers 4

28

IMPORTANT CHANGE

As was pointed out in the comments, .Except() uses a set internally, so any duplicate members of list1 will be absent in the final result.

Produces the set difference of two sequences

http://msdn.microsoft.com/en-us/library/system.linq.enumerable.except(v=vs.110).aspx

However, there is a solution that is both O(N) and preserves duplicates in the original list: Modify the RemoveAll(i => list2.Contains(i)) approach to use a HashSet<int> to hold the exclusion set.

List<int> list1 = Enumerable.Range(1, 10000000).ToList();
HashSet<int> exclusionSet = Enumerable.Range(500000, 10).ToHashSet(); 

list1.Remove(i => exclusionSet.Contains(i));

The extension method ToHashSet() is available in MoreLinq.

ORIGINAL ANSWER

You can use Linq

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

UPDATE

Out of curiosity I did a simple benchmark of my solution vs. @HighCore's.

For list2 having just one element, his code is faster. As list2 gets larger and larger, his code gets extremely slow. It looks like his is O(N-squared) (or more specifically O(list1.length*list2.length) since each item in list1 is compared to each item in list2). Don't have enough data points to check the Big-O of my solution, but it is much faster when list2 has more than a handful of elements.

Code used to test:

        List<int> list1 = Enumerable.Range(1, 10000000).ToList();
        List<int> list2 = Enumerable.Range(500000, 10).ToList(); // Gets MUCH slower as 10 increases to 100 or 1000

        Stopwatch sw = Stopwatch.StartNew();

        //list1 = list1.Except(list2).ToList();
        list1.RemoveAll(i => list2.Contains(i));

        sw.Stop();

        var ms1 = sw.ElapsedMilliseconds;

UPDATE 2

This solution assigns a new list to the variable list1. As @Толя points out, other references (if any) to the original list1 will not be updated. This solution drastically outperforms RemoveAll for all but the smallest sizes of list2. If no other references must see the update, it is preferable for that reason.

13
  • 2
    This does not actually remove any content from list1. Jan 17, 2013 at 21:58
  • 1
    This is returns new list, and not removes from original. Jan 17, 2013 at 22:03
  • Yeah, if there are any other references to the original list they will be unchanged, which means this is a circumstantial fix.
    – Jeff
    Jan 17, 2013 at 22:04
  • @Толя: Agreed. However, it performs much better than RemoveAll. The best solution depends on whether additional references must see the change (and I would argue code program with such side effects is not desirable).
    – Eric J.
    Jan 17, 2013 at 22:15
  • @EricJ. That's fair. Out of interest, what's n in your n-squared? Is it the number of items in list2 or is it the total number of items (so it's actually O(list1.length*list2.length))?
    – Jeff
    Jan 17, 2013 at 22:21
9
list1.RemoveAll(x => list2.Contains(x));
4
  • 2
    +1 because this actually removes items from the original list. (That said it will remove all occurences of any element in list2 from list1 even if they repeat.)
    – millimoose
    Jan 17, 2013 at 22:01
  • 1
    @HighCore: My measurements show that this solution is much slower than mine if list2 has more than a few elements. I'm not surprised that this is O(n-squared) but am not sure why mine is much faster.
    – Eric J.
    Jan 17, 2013 at 22:12
  • 2
    @EricJ. .Except() uses Sets internally, so the removal and such are O(n)
    – millimoose
    Jan 17, 2013 at 22:17
  • 1
    @millimoose: I actually measured times close to O(m*n). See the code I ran in my answer.
    – Eric J.
    Jan 31, 2014 at 19:35
6

You can use this:

List<T> result = list1.Except(list2).ToList();
0
1

This will remove every item in the secondList from the firstList:

firstList.RemoveAll( item => { secondList.Contains(item); } );
1
  • 4
    This is exactly the same as HighCore's answer, but malformed (you're missing ); at the end)
    – Jeff
    Jan 17, 2013 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.