What's an efficient algorithm to make one list equal to another one?

Question

Let's say I have a list A that needs to look exactly like list B. All the objects that B has but A does not have need to be added to A. And all the objects that A has but not B, need to be removed from A.

The reason why I need this is because I have an ArrayList of Players that I'm saving to a file. Every time I update an attribute of a Player, I save the changes to the file by calling a method that looks to the ArrayList of Players and saves it. This works because the ArrayList has the references to the Players.

However, whenever I search for a Player in the list, I first update the list by reading the file where its stored. This replaces all the references with whole new objects. After I do this, if I make a change to a previously fetched user and try to save it. The new instance of the Player gets saved instead of the one I made the changes in.

Would coming up with a good algorithm to make a list equal to another the solution? Or is there a better way to update an entire list while keeping references in use there?

UPDATE: Updated solution, runs in O(nlogm) time. Loops through each element in destination, searches for it in source. If it's found, removed from source. If not, removed from destination. Then add remaining elements in source to destination. List needs to be sorted of course, but the list that I get from the file will already be sorted because I sort as I add.

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class CopyList {
    public static void copyList(List dest, List src) {
        copy(dest, src);

        // the remaining elements in src list will be those that were originally
        // in src but not in dest and so they need to be added
        dest.addAll(src);
    }

    public static void copyList(List dest, List src, Verify v) {
        copy(dest, src);

        // the remaining elements in src list will be those that were originally
        // in src but not in dest and so they need to be added
        addAll(dest, src, v);
    }

    public static void copyList(List dest, List src, Comparator c) {
        copy(dest, src, c);

        // the remaining elements in src list will be those that were originally
        // in src but not in dest and so they need to be added
        dest.addAll(src);
    }

    public static void copyList(List dest, List src, Comparator c, Verify v) {
        copy(dest, src, c);

        // the remaining elements in src list will be those that were originally
        // in src but not in dest and so they need to be added
        addAll(dest, src, v);
    }

    private static void copy(List dest, List src) {
        // go through dest list to search if every element is in the new list
        // travel backwards through dest because we will be removing elements from it
        for(int i = dest.size()-1; i >= 0 ; i--) {
            int src_i = Collections.binarySearch(src, dest.get(i));
            if(src_i >= 0)
                // if element is found in src list, remove it from src list
                src.remove(src_i);
            else
                // if element is NOT found in src list, remove it from dest list
                dest.remove(i);
        }
    }

    private static void copy(List dest, List src, Comparator c) {
        // go through dest list to search if every element is in the new list
        // travel backwards through dest because elements might be removed
        for(int i = dest.size()-1; i >= 0 ; i--) {
            int src_i = Collections.binarySearch(src, dest.get(i), c);
            if(src_i >= 0)
                // if element is found in src list, remove it from src list
                src.remove(src_i);
            else
                // if element is NOT found in src list, remove it from dest list
                dest.remove(i);
        }
    }

    private static void addAll(List dest, List src, Verify v) {
        // verify each element in src list before adding it to dest list
        for(Object o: src)
            if(v.verify(o))
                dest.add(o);
    }
}

Answer 1

Wouldn't the simplest solution be to create a copy of list B? This would only involve creating a copy of the underlying array which would require much less time and effort than a complicated algorithm (not to mention much easier to maintain).

Answer 2

However, whenever I search for a Player in the list, I first update the list by reading the file where its stored.

Why are you doing this? It would make much more sense to search the in-memory copy.

Oh, and there's a really easy way to make a contain the same things as b:

a = b;

Answer 3

I'd step back and think about the design of your program. It sounds like it would be more reasonable to have a class that manages all your Players -- saving them, updating them, handing out references to them. Then just don't hold a reference to a Player anywhere else, hold a reference to your PlayerManager (or whatever you want to call it), and query it to get Players.

This will give you one canonical list, and you won't need to worry about out-of-date references.

Answer 4

I agree with the other submission here that this seems unnecessary for your application, but out of interest if you want an algorithm that does what you describe in better than n^2 time, there is one (and it runs in n*log n time)

sort list users (n log n)
sort list new_users (n log n)
iterate through users and new_users in parallel, adding or removing items from users as necessary ( n )

Answer 5

Did you consider using HashSet for your lists? This way you can just do addAll() and have a union of these lists. Use LinkedHashSet if you want to preserve original order. Would be much faster. You'd just have to override hashCode() in Player class to return hash of their name.

Answer 6

Your program would be faster if you used sets instead of lists i.e. O(1) time complexity assuming no hash collisions.

for(User u : new_users) {
    if (!users.contains(u)) {
        users.add(u);
    }
}
for(User u : users) {
    if (!new_users.contains(u)) {
        users.remove(u);
    }
}