What is the most efficient pattern/algorithm to compare two lists and find the delta between those two lists?

Question

We have two lists, let's say students and their scores. I want to compare these two lists and find the delta between the new list and the old list, then find the least intrusive way to Insert or Update into the new list any changes. What is the best algorithm to approach this? Want to focus on minimal amount of changes to new list and performance.

Example code:

List<ListItem> existingList = new List<ListItem>();
List<ListItem> newList = new List<ListItem>();

public TopLists()
{
  InitTwoLists();
}

private void InitTwoLists()
{
  existingList.Add(new ListItem { Name = "Shane", Score = 100 });
  existingList.Add(new ListItem { Name = "Mark", Score = 95 });
  existingList.Add(new ListItem { Name = "Shane", Score = 94 });
  existingList.Add(new ListItem { Name = "Steve", Score = 90 });
  existingList.Add(new ListItem { Name = "Brian", Score = 85 });
  existingList.Add(new ListItem { Name = "Craig", Score = 85 });
  existingList.Add(new ListItem { Name = "John", Score = 82 });
  existingList.Add(new ListItem { Name = "Steve", Score = 81 });
  existingList.Add(new ListItem { Name = "Philip", Score = 79 });
  existingList.Add(new ListItem { Name = "Peter", Score = 70 });

  newList.Add(new ListItem { Name = "Shane", Score = 100 });
  newList.Add(new ListItem { Name = "Steve", Score = 96 });  // This is change
  newList.Add(new ListItem { Name = "Mark", Score = 95 });
  newList.Add(new ListItem { Name = "Shane", Score = 94 });
  newList.Add(new ListItem { Name = "Brian", Score = 85 });
  newList.Add(new ListItem { Name = "Craig", Score = 85 });
  newList.Add(new ListItem { Name = "John", Score = 82 });
  newList.Add(new ListItem { Name = "Steve", Score = 81 });
  newList.Add(new ListItem { Name = "Philip", Score = 79 });
  newList.Add(new ListItem { Name = "Peter", Score = 70 });
}
}

public void CompareLists()
{
  // How would I find the deltas and update the new list with any changes from old?
}
}

public class ListItem
{
  public string Name { get; set; }
  public int Score { get; set; }
}

** EDIT: Desired Output ***

The desired output is to actually change the newList with the deltas. For example in this scenario:

newList.Add(new ListItem { Name = "Shane", Score = 100 });
  newList.Add(new ListItem { Name = "Steve", Score = 96 });  // This is change
  newList.Add(new ListItem { Name = "Mark", Score = 95 });
  newList.Add(new ListItem { Name = "Shane", Score = 94 });
  newList.Add(new ListItem { Name = "Brian", Score = 85 });
  newList.Add(new ListItem { Name = "Craig", Score = 85 });
  newList.Add(new ListItem { Name = "John", Score = 82 });
  newList.Add(new ListItem { Name = "Steve", Score = 81 });
  newList.Add(new ListItem { Name = "Roger", Score = 80 });  // Roger is a new entry
  newList.Add(new ListItem { Name = "Phillip", Score = 79 });  // Philip moved down one

// Peter drops off this list with his score of 70, since I only want the top 10.

So the changes would be:

Update record 2 for "Steve", the score has changed Insert new record "Roger" at position 9 Drop record for "Peter" off of the top 10.

Answer 1

If you're looking for a general, language-agnostic solution, then you're looking for some kind of data synchronization of ordered lists. The basic algorithm would be:

i1 = 0
i2 = 0
while (i1 < list1.size && i2 < list2.size)
{
  if (list1[i1] < list2[i2])
  {
    //list1[i1] is not in list2
    i1++
  }
  else if (list1[i1] > list2[i2])
  {
    //list2[i2] is not in list1
    i2++
  }
  else
  {
    //item is in both lists
    i1++
    i2++
  }
}
if (i1 < list1.size)
   //all remaining list1 items are not in list2
if (i2 < list2.size)
   //all remaining list2 items are not in list1