Comparing list elements in an effective way

Question

I have a list of opened nodes, with each step about 3000 nodes are opened and I want to put to the opened list only those nodes that are not already there. For now I'm just comparing each new one to all of the ones already in the opened list and only add it if it's not there. But that is around n*3000^2 comparisons for the nth step and makes the progress slower and slower each step. Is there a way to do it faster. Or at least is there a structure that would be better than ArrayList.

This is part of the bigger code, but basically the method I use:

public void addEverything() {
    List<gameState> list = current.neighbours;
    for (gameState state : list) {
        if (!isOpened(state)) {
            opened.add(state);
        }
    }
}
public boolean isOpened(gameState state) {
    for (int i = 0; i < opened.size(); i++) {
        if (state.isSame(opened.get(i)))
            return true;
    }
    return false;
}

As for the isSame() method from the gameState class, it just returns true when the two gameStates are considered the same.

Answer 1

1. Instead of implementing isSame implement equals and hashCode. After that you could use a HashSet (or LinkedHashSet if the order of elements is important). Set is a collection that contains no duplicate elements and inserting/searching is much faster than searching in a list.

   Set<GameState> opened = new LinkedHashSet<GameState>();
   
   public void addEverything() {
       List<GameState> list = current.neighbours;
       for (GameState state : list) {
           opened.add(state);
       }
   }
   

   If you need a list, you can convert it back after the loop:

   List<GameState> openedList = new ArrayList<GameState>(opened);
   

   See also: Overriding equals and hashCode in Java

2. According to the Java Code Conventions, class names in Java usually starts with uppercase letters.

Answer 2

palacsint's answer is good, but it's missing just a few things.

All in-built Java collection classes I can think of has copy-constructors, and an addAll method. So your addEverything method can be a one liner, when using a Set<GameState>:

public void addEverything() {
    opened.addAll(current.neighbours);
}

Or, if you would like to reset the contents and create an entirely new Set, use the copy-constructor:

public void replaceEverything() {
    opened = new LinkedHashSet<GameState>(current.neighbours);
}

Since it can become a one-liner, you might not need to have it in it's own method.

Most importantly, if you are not interested in the order of the opened set, use a HashSet rather than a LinkedHashSet.