Java data structure that only indexes identical items once

Question

The following Java code:

public static void main(String args[]) {

    int[] x = new int[] {1, 2, 3};
    int[] y = new int[] {1, 2, 3};

    LinkedList<int[]> list = new LinkedList<int[]>();

    list.add(x);

    System.out.println("List contains y: " + list.contains(y));

}

gives the output

    List contains y: false

which makes sense as x and y are references to different memory locations, however there is also a sense in which they are equal (they have the the same elements in the same order).

Is there a data structure which would return true to the query list.contains(y) in this example?

Answer 1

I don't believe there is a Java data structure that would return true for contains() as you have described.

The issue, as you probably know, is that for Java arrays, equals() only tests for Object identity and not "equality" as most would define it.

Since contains() relies on equals() in this case (and most of the time), you're stuck with the given behaviour.

You would have to implement a List that specifically overrode contains() to provide your desired behaviour for Java arrays, probably using Arrays.equals().

My suggestion is to instead use a List instead of an array; you'd then have a List<List<Integer>>. contains() should work in this scenario as it'll use equals() on the underyling List implementation.

Answer 2

You need to define a comparator for your arrays. Then when the list looks up the elements, it will use your comparator to see if they're the same:

public static void main(String args[]) {

int[] x = new int[] {1, 2, 3};
int[] y = new int[] {1, 2, 3};

LinkedList<int[]> list = new LinkedList<int[]>(new Comparator<int[]>() {
  @Override
  public int compare(int[] a1, int[] a2) {
    if(a1 == a2) return 0;
    if(a1 == null && a2 != null) return -1;
    if(a1 != null && a2 == null) return 1;
    if(a1.size() < a2.size()) return -1;
    if(a1.size() > a2.size()) return 1;
    for(int i = 0; i < a1.size(); i++) {
      int comp = a1[i] - a2[i];
      if(comp < 0) return -1;
      if(comp > 0) return 1;
    }
    return 0;
  }
});

list.add(x);

System.out.println("List contains y: " + list.contains(y));

}

Answer 3

It looks like you're really looking for a Set implementation.

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element. As implied by its name, this interface models the mathematical set abstraction.

If you want to store sets of int values, you can use this Tuple class I wrote a while ago for another question on SO.

Set<Tuple> myTuples = new HashSet<Tuple>();
Tuple<Integer> x = Tuple.create(1, 2, 3);
Tuple<Integer> y = Tuple.create(1, 2, 3);

myTuples.add(x);
System.out.println("Set contains y: " + myTuples.contains(y)); // prints true

If order matters, you can use a SortedSet.

Answer 4

LinkedList uses equals to implement contains, so this should work:

public static void main(String args[]) {
    static class Ints {
        int[] array;
        public Ints(int[] array) {
            this.array = array;
        }
        public boolean equals(Object other) {
            if (other instanceof Ints) {
                return arraysEqual((Ints) other);
            }
        }
        public boolean arraysEqual(Ints other) {
            // check that this.array and other.array are same length and
            // have same values. Do a null check somewhere too. :)
        }
    }

    Ints x = new Ints(new int[] {1, 2, 3});
    Ints y = new Ints(new int[] {1, 2, 3});

    LinkedList<Ints> list = new LinkedList<int[]>();

    list.add(x);

    System.out.println("List contains y: " + list.contains(y));

}

Answer 5

You would probably want to extend LinkedList into your own custom data structure and define a custom equality method if you wanted anything outside of the standard checking that is in place.

Answer 6

If you could use a Set instead of an array it might be easier. Have a look here or here