Use LINQ to get items in one List<>, that are not in another List<>

Question

I would assume there's a simple LINQ query to do this, I'm just not exactly sure how.

Given this piece of code:

class Program
{
    static void Main(string[] args)
    {
        List<Person> peopleList1 = new List<Person>();
        peopleList1.Add(new Person() { ID = 1 });
        peopleList1.Add(new Person() { ID = 2 });
        peopleList1.Add(new Person() { ID = 3 });

        List<Person> peopleList2 = new List<Person>();
        peopleList2.Add(new Person() { ID = 1 });
        peopleList2.Add(new Person() { ID = 2 });
        peopleList2.Add(new Person() { ID = 3 });
        peopleList2.Add(new Person() { ID = 4 });
        peopleList2.Add(new Person() { ID = 5 });
    }
}

class Person
{
    public int ID { get; set; }
}

I would like to perform a LINQ query to give me all of the people in peopleList2 that are not in peopleList1.

This example should give me two people (ID = 4 & ID = 5)

Plonk

Perhaps it's a good idea to make ID readonly since the identity of an object shouldn't change over its live time. Unless of course your testing- or ORM-framework requires it to be mutable. – Wynellwynn

Could we call this a "Left (or Right) Excluding Join" according to this diagram? – Countercheck

Answer 1

This can be addressed using the following LINQ expression:

var result = peopleList2.Where(p => !peopleList1.Any(p2 => p2.ID == p.ID));

An alternate way of expressing this via LINQ, which some developers find more readable:

var result = peopleList2.Where(p => peopleList1.All(p2 => p2.ID != p.ID));

Warning: As noted in the comments, these approaches mandate an O(n*m) operation. That may be fine, but could introduce performance issues, and especially if the data set is quite large. If this doesn't satisfy your performance requirements, you may need to evaluate other options. Since the stated requirement is for a solution in LINQ, however, those options aren't explored here. As always, evaluate any approach against the performance requirements your project might have.

Stelliform

You are aware that that's a O(n*m) solution to a problem that can easily be solved in O(n+m) time? – Corsage

Yeah, it wouldn't let me mark it as the answer right away, said I needed to wait 5 minutes :) Thanks again! – Plonk

@nikie, the OP asked for a solution that uses Linq. Maybe he's trying to learn Linq. If the question had been for the most efficient way, my question would not necessarily have been the same. – Stelliform

@nikie, care to share your easy solution? – Cotenant

This is equivalent and I find easier to follow: var result = peopleList2.Where(p => peopleList1.All(p2 => p2.ID != p.ID)); – Annapurna

@KlausByskovPedersen while your answer is spot on for the given question, please note that Google brings people like me who search for the same question without the "Use Linq" bit. I was already aware of where but was looking to see if there was a better solution. So would you consider adding the Except bit to your answer as well? – Lockjaw

You could also use .All(), making it slightly clearer, var result = peopleList2.Where(p => peopleList1.All(p2 => p2.ID != p.ID)); – Mexico

if in fact you use Resharper it will suggest you change the 'Any' to 'All' as mentioned above – Ejectment

@Lockjaw - it might be a bit unfair to criticize someone who correctly responds to a question. People shouldn't need to anticipate all the ways and contexts that future people might stumble onto the answer. In reality, you should direct that to nikie - who took the time to state that they knew of an alternative without providing it. – Unclassical

@ChrisRogers I agree with your point. Just to be clear, I didn't mean to criticize Klaus, I was merely pointing him to the problem I faced hoping he would improve his ansewer. I do apologize if I didn't do a good job expressing it correctly. – Lockjaw

FYI: I’ve updated the answer with notes from these comments. Notably, this includes the alternate formulation from @AntonK. I also included @Niki’s warning—though the alternate formulation is potentially faster, as it will stop if it finds a match. (Obviously, though, it’s only faster if there is actually overlap between the two sets.) – Ancylostomiasis

@Niki, so what is the O(m+n) approach@_@? – Thrasonical

@Thrasonical He is probably referring to implementing IEquatable on the object, which uses hash tables, and then using LINQ's .Except. This isn't always possible or practical; if the lists to be compared will always be small, might as well use .Where/.All instead of .Except. If it takes 0.2 seconds to iterate through the lists with .Where/.All and 0.07 seconds with .Except am I really going to spend 10 minutes implementing IEquatable, complicating the code base, and explaining IEquatable to the other devs on my team who aren't familiar with it? Probably not. – Dichlorodiphenyltrichloroethane

See CodesInChaos's answer for the more performant, non-LINQ version. – Hydrocele

I cannot tell you how many times I've come back to this answer. I wish I could upvote it for each time I've used it – Donaghue

Answer 2

If you override the equality of People then you can also use:

peopleList2.Except(peopleList1)

Except should be significantly faster than the Where(...Any) variant since it can put the second list into a hashtable. Where(...Any) has a runtime of O(peopleList1.Count * peopleList2.Count) whereas variants based on HashSet<T> (almost) have a runtime of O(peopleList1.Count + peopleList2.Count).

Except implicitly removes duplicates. That shouldn't affect your case, but might be an issue for similar cases.

Or if you want fast code but don't want to override the equality:

var excludedIDs = new HashSet<int>(peopleList1.Select(p => p.ID));
var result = peopleList2.Where(p => !excludedIDs.Contains(p.ID));

This variant does not remove duplicates.

Wynellwynn

That would only work if Equals had be overridden to compare ID's. – Stelliform

That's why I wrote that you need to override the equality. But I've added an example which works even without that. – Wynellwynn

It would also work if Person was a struct. As it is though, Person seems an incomplete class as it has a property called "ID" which does not identify it - if it did identify it, then equals would be overridden so that equal ID meant equal Person. Once that bug in Person is fixed, this approach is then better (unless the bug is fixed by renaming "ID" to something else that doesn't mislead by seeming to be an identifier). – Photocell

It also works great if you're talking about a list of strings (or other base objects), which was what I was searching for when I came upon this thread. – Picayune

@DanKorn Same, this a simpler solution, compared to the where, for basic comparison, int, objects ref, strings. – Frap

It seems you also need to override GetHashCode(). Which makes sense now, since you mentioned a hashtable. But implementing only Equals() returns incorrect results. – Arithmomancy

@Arithmomancy Actually you have to override both Equals() and GetHashCode(), no matter what – Essie

I tried the Where(...Any) solution on a dataset with ~200,000 records and my query timed out, every time. That's probably correct, according to the answer, but for those doing this in a live setting I would recommend using the Except() solution here. – Asset

I used your second code example with the hashset, it worked very well for me for the scenario where I am joining two different classes. – Caribou

Answer 3

Or if you want it without negation:

var result = peopleList2.Where(p => peopleList1.All(p2 => p2.ID != p.ID));

Basically it says get all from peopleList2 where all ids in peopleList1 are different from id in peoplesList2.

Just a little bit different approach from the accepted answer :)

Okie

This method (list of over 50,000 items) was significantly faster than the ANY method! – Leukoderma

This might be faster just because it is lazy. Note that this is not doing any real work just yet. It's not until you enumerate the list that it actually does the work (by calling ToList or using it as part of a foreach loop, etc.) – Included

Answer 4

Since all of the solutions to date used fluent syntax, here is a solution in query expression syntax, for those interested:

var peopleDifference = 
  from person2 in peopleList2
  where !(
      from person1 in peopleList1 
      select person1.ID
    ).Contains(person2.ID)
  select person2;

I think it is different enough from the answers given to be of interest to some, even thought it most likely would be suboptimal for Lists. Now for tables with indexed IDs, this would definitely be the way to go.

Carotid

Thank you. First answer that bothers with query expression syntax. – Buttonhole

Only answer I found with query expression syntax. Thank you! – Goulette

Answer 5

Bit late to the party but a good solution which is also Linq to SQL compatible is:

List<string> list1 = new List<string>() { "1", "2", "3" };
List<string> list2 = new List<string>() { "2", "4" };

List<string> inList1ButNotList2 = (from o in list1
                                   join p in list2 on o equals p into t
                                   from od in t.DefaultIfEmpty()
                                   where od == null
                                   select o).ToList<string>();

List<string> inList2ButNotList1 = (from o in list2
                                   join p in list1 on o equals p into t
                                   from od in t.DefaultIfEmpty()
                                   where od == null
                                   select o).ToList<string>();

List<string> inBoth = (from o in list1
                       join p in list2 on o equals p into t
                       from od in t.DefaultIfEmpty()
                       where od != null
                       select od).ToList<string>();

Kudos to http://www.dotnet-tricks.com/Tutorial/linq/UXPF181012-SQL-Joins-with-C

Furlani

Answer 6

This Enumerable Extension allow you to define a list of item to exclude and a function to use to find key to use to perform comparison.

public static class EnumerableExtensions
{
    public static IEnumerable<TSource> Exclude<TSource, TKey>(this IEnumerable<TSource> source,
    IEnumerable<TSource> exclude, Func<TSource, TKey> keySelector)
    {
       var excludedSet = new HashSet<TKey>(exclude.Select(keySelector));
       return source.Where(item => !excludedSet.Contains(keySelector(item)));
    }
}

You can use it this way

list1.Exclude(list2, i => i.ID);

Subinfeudation

By having the code that @BrianT has, how could I convert it to use your code? – Banish

Create a new class somewhere with the EnumerableExtensions code in Bertrand's reply. Add using statement in class where query is performed. Then change the selection code to var result = peopleList2.Exclude(peopleList1, i => i.ID); – Kibitzer

Answer 7

Klaus' answer was great, but ReSharper will ask you to "Simplify LINQ expression":

var result = peopleList2.Where(p => peopleList1.All(p2 => p2.ID != p.ID));

Bizarre

It's worth to note that this trick won't work if there's more than one property binding the two objects (think SQL composite key). – Icsh

Alrekr - If what you mean to say is "you will need to compare more properties if more properties need comparing" then I'd say that's pretty obvious. – Bandsman

Answer 8

Once you write a generic FuncEqualityComparer you can use it everywhere.

peopleList2.Except(peopleList1, new FuncEqualityComparer<Person>((p, q) => p.ID == q.ID));

public class FuncEqualityComparer<T> : IEqualityComparer<T>
{
    private readonly Func<T, T, bool> comparer;
    private readonly Func<T, int> hash;

    public FuncEqualityComparer(Func<T, T, bool> comparer)
    {
        this.comparer = comparer;
        if (typeof(T).GetMethod(nameof(object.GetHashCode)).DeclaringType == typeof(object))
            hash = (_) => 0;
        else
            hash = t => t.GetHashCode(); 
    }

    public bool Equals(T x, T y) => comparer(x, y);
    public int GetHashCode(T obj) => hash(obj);
}

Barefaced

Answer 9

As of DotNet 6 there is ExceptBy, like Except but allows a key provider function.

Looks like this.

static int PersonIdSelector(Person person) => person.ID;
    
var peopleList3 = peopleList2.ExceptBy(
    peopleList1.Select(PersonIdSelector),
    PersonIdSelector
    );

Palladio

Answer 10

first, extract ids from the collection where condition

List<int> indexes_Yes = this.Contenido.Where(x => x.key == 'TEST').Select(x => x.Id).ToList();

second, use "compare" estament to select ids diffent to the selection

List<int> indexes_No = this.Contenido.Where(x => !indexes_Yes.Contains(x.Id)).Select(x => x.Id).ToList();

Obviously you can use x.key != "TEST", but is only a example

Shelli

Answer 11

Here is a working example that get IT skills that a job candidate does not already have.

//Get a list of skills from the Skill table
IEnumerable<Skill> skillenum = skillrepository.Skill;
//Get a list of skills the candidate has                   
IEnumerable<CandSkill> candskillenum = candskillrepository.CandSkill
       .Where(p => p.Candidate_ID == Candidate_ID);             
//Using the enum lists with LINQ filter out the skills not in the candidate skill list
IEnumerable<Skill> skillenumresult = skillenum.Where(p => !candskillenum.Any(p2 => p2.Skill_ID == p.Skill_ID));
//Assign the selectable list to a viewBag
ViewBag.SelSkills = new SelectList(skillenumresult, "Skill_ID", "Skill_Name", 1);

Hound

Answer 12

{
    static void Main(string[] args)
    {
        List<Person> peopleList1 = new List<Person>();
        peopleList1.Add(new Person() { ID = 1 });
        peopleList1.Add(new Person() { ID = 2 });
        peopleList1.Add(new Person() { ID = 3 });

        List<Person> peopleList2 = new List<Person>();
        peopleList2.Add(new Person() { ID = 1 });
        peopleList2.Add(new Person() { ID = 2 });
        peopleList2.Add(new Person() { ID = 3 });
        peopleList2.Add(new Person() { ID = 4 });
        peopleList2.Add(new Person() { ID = 5 });
    }

    var leftPeeps = peopleList2.Where(x => !peopleList1.Select(y => y.ID).Contains(x.ID))?.ToList() ?? new List<Person>();
}

class Person
{
    public int ID { get; set; }
}

Notice the !peopleList1.Select(y => y.ID).Contains(x.ID) Select statement. This allows us to grab the indexer we want (ID) and see if it contains the ID of the previous list. ! means we don't want those. This may leave us with no entries. so, we can ensure we have something by checking for null and using a null coalesce.

Tress