Eliminating or avoiding adding duplicates in a Arr

Question

I have a custom object in this structure

static class Node {
    int col;
    int row;
    int g;
    int h;
    int f;

    public Node(int col, int row, int g, int h) {
        this.col = col;
        this.row = row;
        this.g = g;
        this.h = h;
        this.f = g+h;
    }
}

The col and row variables are unique, and may only occur once in ArrayList<Node> myList.

Is there a way optimal way to avoid adding or checking for possible duplicate without having to make a nasty for-loop?

I am aware that Set interface possibly could be a solution for this as duplicates cannot occur, but i have alot of code right now, which i do not want to refactor unless it becomes necessary.

Answer 1

Ideally, you'd use Set, but if you'd like to avoid reimplementing your data structures from ArrayList<Node> to Set, you can implement Set as a gatekeeper:

• Each time an element is about to be inserted into your ArrayList, check if the row-col pair is already in the Set.
• If not, register the row-col pair into the Set
• If the pair already exists in the set, do not insert it
• Each time an element is about to be removed from your ArrayList, remove it from the Set.

And thus it's a "gatekeeper".

All of the Set operations are O(1) since they are hashed; minimal refactoring and no nasty loops as desired.

Answer 2

Keep both a Set and a List. Use the Set to check for duplicates. Add to both Set and List if no dupe.

...assuming that Node has an .equals method defined...

private final Set<Node> seen = new HashMap<Node>();
private final List<Node> uniqueNodes = new ArrayList<Node>();


public void insertIfUnique(final Node n) {
  if (seen.contains(n)) {
    return;
  }
  seen.add(n);
  uniqueNodes.add(n);
}

Answer 3

I always find weird to see cases where people want to use a List (for the get(int) method, I guess) when they require unicity, which is only achieved through Set.

Anyway, by manipulating a little the equals/hashcode (making equals return true when row and col are the same) method and adding calls to List#contains(Object), you could have your goal reached without sacrifying your List

EDIT

Notice you could also create a Comparator and rely upon Collections#sort(List, Comparator) to have your list sorted and items with the same value melted into only one value.

Answer 4

Add a equals method in Node if possible :

@Override
public boolean equals(Node n){
if(this.getRow().equals(n.getRow()) && this.getCol().equals(n.getCol())
return true;
else
return false;
}

And then use list-to-set-to-list trick.

Try this method:

List<Node> removeDuplicateNodes(List<Node> inputList){
return (inputList ==null or inputList.size()==0)? Collections.EMPTY_LIST: new ArrayList<Node>(new HashSet<Node>(inputList));
}

Update :

If you wan't to maintain input order, use LinkedHashSet

List<Node> removeDuplicateNodes(List<Node> inputList){
return (inputList ==null or inputList.size()==0)? Collections.EMPTY_LIST: new ArrayList<Node>(new LinkedHashSet<Node>(inputList));
}

Answer 5

Here are your options. All of these solutions require proper implementation of equals and hashCode. Since you want row and col to be unique:

public boolean equals(Object obj) {
    if (obj == null || obj.getClass() != Node.class) {
        return false;
    }
    Node other = (Node) obj;
    if (other.col != this.col) {
        return false;
    }
    if (other.row != this.row) {
        return false;
    }
    return true;
}

public int hashCode() {
    int result = 7;
    result += row * 31;
    result += col * 31;
    return result;
}

Iterate over the List

You don't have to do the iteration yourself, but that is exactly what calling List.contains will do. This one is pretty easy:

if (!myList.contains(node)) {
    myList.add(node);
}

This will iterate for you, so you don't have to write the loop.

List to Set to List

Here you have two sub-options. If you want to preserve the order of your input list, then you can use LinkedHashSet. If you don't care, you can just use HashSet. What I mean is if I have a List with elements A, B, C, converting it to a HashSet and back may produce a different list, like B, C, A. LinkedHashSet keeps the elements in insertion order, avoiding this problem. In any case, you'll just do this:

Set<Node> nodeSet = new [Linked]HashSet<Node>(myList);
nodeSet.add(node);
myList = new ArrayList<Node>(nodeSet);

Remember that this is essentially doing iteration as well, but it's using a hash-code shortcut instead of checking every element's equality, which may be a big deal with enough nodes. If your node list is small (less than 1000 elements) then I doubt this will make much of a difference, and you may as well use the first one.

Converting everything to Set

You mentioned that this would require a lot of refactoring in your code, but this isn't a bad thing, especially if you plan on working on this code a lot in the future. My rule of thumb is if the refactoring will make the code easier to maintain, adding a little extra development time is never a bad thing. Writing maintainable, readable, and understandable code is what the experts do (the question here isn't relevant, but this particular answer is). Since Set implies unique elements and List does not, then it makes sense to make the change. The compiler will pretty much tell you all the places you have to change with its errors, and it might take less time than you think.

Answer 6

Add all the elements to a new Set, then put all the elements from the Set to a new List. That will make it.