I have not tested this for performance, but my gut feeling is that you should first sort the two lists. Then you can step through the lists key each removed, added or unchanged element as you progress.
1- Sort the Old and New list
2- Set up a pointer for each list lets call them p1 and p2
3- Step the pointers using the following algorithm
a) If Old[p1] = New[p2] the items are unchanged, increment p1 and p2
b) If Old[p1] < New[p2] then Old[p1] has been removed, increment p1
c) If Old[p1] > new[p2] then New[p2] is a new element, increment p2
d) If p1 > Old.ItemCount then break out of loop, rest of New contains new items
e) If p2 > New.ItemCount then break out of loop, rest of Old items have been removed
f) If p1 < Old.ItemCount and p2 < Old.ItemCount Goto step **a**
That was just off the top of my head, but the basics should be correct. The key to this is that the lists are sorted of course.
Here is a quick and dirty demo, I included the sort for demonstration purposed, of course in this case the data is already sorted.
static void Main(string[] args)
{
string[] oldList = { "a", "b", "c", "d", "e" };
string[] newList = { "d", "e", "f", "g" };
Array.Sort(oldList);
Array.Sort(newList);
int p1 = 0;
int p2 = 0;
while (p1 < oldList.Length && p2 < newList.Length)
{
if (string.Compare(oldList[p1], newList[p2]) == 0)
{
Console.WriteLine("Unchanged:\t{0}", oldList[p1]);
p1++;
p2++;
}
else if (string.Compare(oldList[p1], newList[p2]) < 0)
{
Console.WriteLine("Removed:\t{0}", oldList[p1]);
p1++;
}
else if (string.Compare(oldList[p1], newList[p2]) > 0)
{
Console.WriteLine("Added:\t\t{0}", newList[p2]);
p2++;
}
}
while (p1 < oldList.Length)
{
Console.WriteLine("Removed:\t{0}", oldList[p1]);
p1++;
}
while (p2 < newList.Length)
{
Console.WriteLine("Added :\t\t{0}", newList[p2]);
p2++;
}
Console.ReadKey();
}
The output from the above
Removed: a
Removed: b
Removed: c
Unchanged: d
Unchanged: e
Added : f
Added : g