What is the least amount of code needed to update one list with another list?

Question

Suppose I have one list:

IList<int> originalList = new List<int>();
originalList.add(1);
originalList.add(5);
originalList.add(10);

And another list...

IList<int> newList = new List<int>();
newList.add(1);
newList.add(5);
newList.add(7);  
newList.add(11);

How can I update originalList so that:

1. If the int appears in newList, keep
2. If the int does not appear in newList, remove
3. Add any ints from newList into originalList that aren't there already

Thus - making the contents of originalList:

{ 1, 5, 7, 11 }

The reason I'm asking is because I have an object with a collection of children. When the user updates this collection, instead of just deleting all children, then inserting their selections, I think it would be more efficient if I just acted on the children that were added or removed, rather than tearing down the whole collection, and inserting the newList children as if they are all new.

EDIT - Sorry - I wrote a horrible title... I should have written 'least amount of code' instead of 'efficient'. I think that threw off alot of the answers I've gotten. They are all great... thank you!

Answer 1

Sorry, wrote my first response before I saw your last paragraph.

for(int i = originalList.length-1; i >=0; --i)
{
     if (!newList.Contains(originalList[i])
            originalList.RemoveAt(i);
}

foreach(int n in newList)
{
     if (!originaList.Contains(n))
           originalList.Add(n);
}

Answer 2

originalList = newList;

Or if you prefer them being distinct lists:

originalList = new List<int>(newList);

But, either way does what you want. By your rules, after updating, originalList will be identical to newList.

UPDATE: I thank you all for the support of this answer, but after a closer reading of the question, I believe my other response (below) is the correct one.

Answer 3

If you use some LINQ extension methods, you can do it in two lines:

originalList.RemoveAll(x => !newList.Contains(x));
originalList.AddRange(newList.Where(x => !originalList.Contains(x)));

This assumes (as do other people's solutions) that you've overridden Equals in your original object. But if you can't override Equals for some reason, you can create an IEqualityOperator like this:

class EqualThingTester : IEqualityComparer<Thing>
{
    public bool Equals(Thing x, Thing y)
    {
        return x.ParentID.Equals(y.ParentID);
    }

    public int GetHashCode(Thing obj)
    {
        return obj.ParentID.GetHashCode();
    }
}

Then the above lines become:

originalList.RemoveAll(x => !newList.Contains(x, new EqualThingTester()));
originalList.AddRange(newList.Where(x => !originalList.Contains(x, new EqualThingTester())));

And if you're passing in an IEqualityOperator anyway, you can make the second line even shorter:

originalList.RemoveAll(x => !newList.Contains(x, new EqualThingTester()));
originalList.AddRange(newList.Except(originalList, new EqualThingTester()));

Answer 4

If you are not worried about the eventual ordering, a Hashtable/HashSet will likely be the fastest.

Answer 5

LINQ solution:

originalList = new List<int>(
                      from x in newList
                      join y in originalList on x equals y into z
                      from y in z.DefaultIfEmpty()
                      select x);

Answer 6

My initial thought was that you could call originalList.AddRange(newList) and then remove the duplicates - but i'm not sure if that would be any more efficient than clearing the list and repopulating it.

Answer 7

List<int> firstList = new List<int>() {1, 2, 3, 4, 5};
List<int> secondList = new List<int>() {1, 3, 5, 7, 9};

List<int> newList = new List<int>();

foreach (int i in firstList)
{
  newList.Add(i);
}

foreach (int i in secondList)
{
  if (!newList.Contains(i))
  {
    newList.Add(i);
  }
}

Not very clean -- but it works.

Answer 8

There is no built in way of doing this, the closest I can think of is the way DataTable handles new and deleted items.

What @James Curran suggests is merely replace the originalList object with the newList object. It will dump the oldList, but keep the variable (i.e. the pointer is still there).

Regardless, you should consider if optimising this is time well spent. Is the majority of the run time spent copying values from one list to the next, it might be worth it. If it's not, but rather some premature optimising you are doing, you should ignore it.

Spend time polishing the GUI or profile the application before you start optimising is my $.02.

Answer 9

This is a common problem developers encounter when writing UIs to maintain many-to-many database relationships. I don't know how efficient this is, but I wrote a helper class to handle this scenario:

public class IEnumerableDiff<T>
{
    private delegate bool Compare(T x, T y);

    private List<T> _inXAndY;
    private List<T> _inXNotY;
    private List<T> _InYNotX;

    /// <summary>
    /// Compare two IEnumerables.
    /// </summary>
    /// <param name="x"></param>
    /// <param name="y"></param>
    /// <param name="compareKeys">True to compare objects by their keys using Data.GetObjectKey(); false to use object.Equals comparison.</param>
    public IEnumerableDiff(IEnumerable<T> x, IEnumerable<T> y, bool compareKeys)
    {
        _inXAndY = new List<T>();
        _inXNotY = new List<T>();
        _InYNotX = new List<T>();
        Compare comparer = null;
        bool hit = false;

        if (compareKeys)
        {
            comparer = CompareKeyEquality;
        }
        else
        {
            comparer = CompareObjectEquality;
        }


        foreach (T xItem in x)
        {
            hit = false;
            foreach (T yItem in y)
            {
                if (comparer(xItem, yItem))
                {
                    _inXAndY.Add(xItem);
                    hit = true;
                    break;
                }
            }
            if (!hit)
            {
                _inXNotY.Add(xItem);
            }
        }

        foreach (T yItem in y)
        {
            hit = false;
            foreach (T xItem in x)
            {
                if (comparer(yItem, xItem))
                {
                    hit = true;
                    break;
                }
            }
            if (!hit)
            {
                _InYNotX.Add(yItem);
            }
        }
    }

    /// <summary>
    /// Adds and removes items from the x (current) list so that the contents match the y (new) list.
    /// </summary>
    /// <param name="x"></param>
    /// <param name="y"></param>
    /// <param name="compareKeys"></param>
    public static void SyncXList(IList<T> x, IList<T> y, bool compareKeys)
    {
        var diff = new IEnumerableDiff<T>(x, y, compareKeys);
        foreach (T item in diff.InXNotY)
        {
            x.Remove(item);
        }
        foreach (T item in diff.InYNotX)
        {
            x.Add(item);
        }
    }

    public IList<T> InXAndY
    {
        get { return _inXAndY; }
    }

    public IList<T> InXNotY
    {
        get { return _inXNotY; }
    }

    public IList<T> InYNotX
    {
        get { return _InYNotX; }
    }

    public bool ContainSameItems
    {
        get { return _inXNotY.Count == 0 && _InYNotX.Count == 0; }
    }

    private bool CompareObjectEquality(T x, T y)
    {
        return x.Equals(y);
    }

    private bool CompareKeyEquality(T x, T y)
    {
        object xKey = Data.GetObjectKey(x);
        object yKey = Data.GetObjectKey(y);
        return xKey.Equals(yKey);
    }

}

Answer 10

if your using .Net 3.5

var List3 = List1.Intersect(List2);

Creates a new list that contains the intersection of the two lists, which is what I believe you are shooting for here.