Algorithm for comparing two lists

Question

I have a list of objects that I am displaying on the screen. The user can change them as they like, and then hit submit. In the submit method I am taking the original list, which I stored, and the current list, and comparing them. I have to create a third list that contains all the objects that were added, removed, or changed with an action code to specify which it was. The objects have an id to identify them, which defaults to 0.

How can I do this? This is the best I could come up with (pseudocode) but it seems sloppy.

for (currentObject : objects in current list)
    if (currentObject.id is 0)
        //Was added
    for (oldObject : objects in original list)
        if (currentObject.id == oldObject.id)
            //Existed - compare other fields to see if changed

for (oldObject1 : objects in original list)
    boolean existed = false;
    for (currentObject1 : objects in current list)
        if(oldObject1.id == currentObject1.id)
            existed=true;
    if (!existed)
        //Was removed

Answer 1

If ordering doesn't matter and all you care about is whether the elements were added or removed, you might want to consider changing your data structures and using Set rather than List. The Set type is specifically designed to determine whether or not elements exist and to do so efficiently, at the cost that you no longer remember the order of the elements.

For example, using HashSet, you could do the following:

Set<T> oldElems = new HashSet<T>(originalList);
Set<T> newElems = new HashSet<T>(currentList);

for (T obj : oldElems) {
    if (!newElems.contains(obj)) {
        /* ... this object was removed ... */
    }
}

for (T obj : newElems) {
    if (!oldElems.contains(obj)) {
        /* ... this object was added ... */
    }
}

Hope this helps!

Answer 2

You can do it with one loop, by continuously maintaining the 3-way result list. If you can override equals() to depend on ids, that's fine. If not, check the code under update.

Here's the code, see the explanation below:

List<T> origList = ...;
List<T> newList = ...;

List<T> addedList = new ArrayList<T>();
List<T> deletedList = new ArrayList<T>();
List<T> changedList = new ArrayList<T>();

deletedList.addAll(origList);

for(T t : newList) {
    int origIndex = deletedList.indexOf(t);
    if (origIndex < 0) {
        addedList.add(t);
    } else {
        T origT = deletedList.remove(origIndex);
        if(t.compareTo(origT) != 0) {
            changedList.add(t);
        }
    }
}

Note that I presumed that equals() will check the id, and compareTo() will check all other fields.

Explanation:

You remove all elements from deletedList that were also present in newList, so the result is the deleted items.

You add all new elements to the addedList that were not present in the original list.

If both are present and the objects differ, they'll go to the changedList.

If both are present and the objects are the same then we don't add it anywhere.

Notes:

If new objects have an ID of 0, they will not be present in origList (since we suppose they have been already created).

When I last time implemented this, I created a separate method to compare the objects field-by-field, so I could separate the comparison logic from standard Java methods (actually it was also declared on an interface)

I created this with Lists, but actually you can use it with any type of Collection. Using with List will preserve the original order.

Update:

Try overriding your equals this way (I skipped the typecheck and the casting):

public boolean equals(T other) {
    if (this.id == 0) {
        return this == other;
    }
    return this.id == other.id;
}

The not-yet-created instances are equal to themselves only. The already-created ones are checked by id.