CODEWITHSUNDEEP
c#
jmasterx
jmasterx

Reputation: 54123

Find elements added and removed from 2 lists

I have 

var list1 = new List<int> { 1, 2, 3 };
var list2 = new List<int> { 1, 2, 4 };

I want from this:

listAdded: {4}
listRemoved: {2}

The elements are distinct.

How can I:

*Quickly find if list1 and list2 are the same (no changes)
*Get the list of changes (added & removed)?

I'm currently using List<T> but I'm open to HashSet<T> if it will make things faster.

Upvotes: 0

Views: 1698

Answers (3)

Stef Geysels
Stef Geysels

Reputation: 1047

You can make a Class that derives from List<> and override the Add() and Remove().

Public class MyList<T> : List<T>
{

    private List<T> oldItems = new List<T>();
    private List<T> newItems = new List<T>();

    private List<T> items = new List<T>();
    public List<T> Items 
    {
        get { return items; }
        set { items = value; }
    }

    public void Add(T value)
    {
        Items.Add(value);
        newItems.Add(Items.Where(w=>w==value)); // must be the object in the "Items" list
    }

    public void Remove(T value)
    {
        Items.Remove(value);
        oldItems.Add(value); //value does not exist anymore in `Items`
    }

    public List<T> GetOldItems()
    {
        List<T> oldi = oldItems;
        oldItems.Clear();
        return oldi;
    }

    public List<T> GetNewItems() //
    {
        List<T> newi = newItems;
        newItems.Clear();
        return newi;
    }
}

Then you have a list with inside a list for both old items and new items.

When you add a item, it will be registered even so if you remove an item. When you get the new or old items, the register will be cleared.

Upvotes: 0

meJustAndrew
meJustAndrew

Reputation: 6623

Simply by using Except you can get the differences between two lists in a new collection, then you can check the count of the new collection to see if they are any differences.

var removed = list1.Except(list2).ToList();
var added = list2.Except(list1).ToList();

Then you are free to do a simple if on their Count:

bool areDifferent = removed.Count > 0 || added.Count > 0;

or as Kevin suggested:

bool areDifferent = removed.Any() || added.Any();

Upvotes: 2

3Dave
3Dave

Reputation: 29051

Pseudocode with LINQ - (removed - see @meJustAndrew's answer for a better LINQ implementation)

You could do something O(n) if the lists are sorted:

int i = 0;
int j = 0;

while(i < list1.Count && j < list2.Count)
{
   if (list1[i] == list2[j])
   {
     ++i;
     ++j;
   }
   else if (list1[i] < list2[j])
   {
     removed.Add(list1[i]);
     ++i;
   }
   else // if (list1[i] > list2[j])
   {
     added.Add(list2[j]);
     ++j;
   }
}

if (i < list1.Count)
{
  removed.AddRange(list1.GetRange(i,list1.Count));
}
if (j < list2.Count)
{
  added.AddRange(list2.GetRange(j,list2.Count));
}

Upvotes: 0

Related Questions