# Comparing list elements in an effective way

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)) {
}
}
}
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.

-

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>();

List<GameState> list = current.neighbours;
for (GameState state : list) {
}
}


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

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

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

-
+1. Conceptually two objects where "isSame" is true should also be "equals". If this would not be true, I would not change the "equals" semantics (and hashCode) just for performance issues. – robermann Mar 18 '14 at 14:08
One more question about this: Whenever a.equals(b), then a.hashCode() must be same as b.hashCode(). The opposite doesn't hold right? So would there be any consecunces if I were to implement hashCode() to always return 1 for example? – Sunny Mar 18 '14 at 14:52
@Sunny: Yes, you're right. hashCode could be constant but performance will suffer (it won't be faster than the original code) so don't do it. You can generate good hashCode methods with Eclipse easily but there are libraries for that too. (See the linked Stack Overflow question.) – palacsint Mar 18 '14 at 15:05

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() {
}


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

public void replaceEverything() {

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