3

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.

Improve this question

6 Answers 6

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

So in other words. To keep it more clean i should refactor to Set and override the equals() method?
Im very tempted to traverse the entire list instead even though it will become O(N).
That's a viable option too. If your list is fairly small (like I said in my answer, < 1000 elements) then doing all this stuff won't have much of a speed impact anyway. You can always write it to use contains and see if it's really that slow. If it starts getting too slow, then convert everything to Set.
1

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));
}
Improve this answer

Comments

0

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

Improve this answer

1 Comment

Don't forget to override equal() and hashCode() methods to check for the specific condition of equality that you want implemented
0

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.

Improve this answer

1 Comment

I already have a sort algorithm, but i am sorting a entirely different criteria. So perhaps i might be better off using a Set instead.
0

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);
}
Improve this answer

Comments

0

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.

Improve this answer

3 Comments

If i implement Set, how can i filter duplicates based on row and col and not the entire element?
Hmm, it appears that Pair<> is only in C++, and not Java. You can filter duplicates by overriding Node's .equals(): where you check if both the rows and columns are equal, then the Nodes themselves are equal.
But this is not possible with an ArrayList in same fashion by overriding the equals method?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.