2

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?

Improve this question
2
  • Arrays have no sensible value-equality defined over them. This requires an array-aware structure (none standard or) or to wrap the array in a class which supports equals as desired -- in which case it will work as expected, albeit a bit more work. Some of the data-structures (HashMap, for instance) do allow one to specify a custom comparable. Commented May 26, 2011 at 23:08
  • As many here have said, there is no such built in data structure in the standard library. What are you trying to accomplish? Are you trying to implement isSubsetOf, isSubstringOf or something else? By isSubstringOf I mean the exact array should be a part of the original array. Commented May 27, 2011 at 4:58

6 Answers 6

Reset to default
9

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.

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

Comments

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

}

Improve this answer

3 Comments

LinkedList doesn't allow for a custom Comparator in it's constructor
@Bengt is right. Besides, what would such a comparator even do?
Omg, I'm thinking of TreeSet or ArrayList. You're right. I must've been thinking of Set or ArrayList. Yeah, Peter's answer is the right way to go a List of Lists instead of a List of Arrays.
2

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.

Improve this answer

Comments

1

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

}
Improve this answer

Comments

0

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.

Improve this answer

2 Comments

That's terrible advice. It's fixing the wrong problem. The arrays are the problem, not the List. Peter is right: use Lists of Lists, not Lists of Arrays.
I concede, using a List of Lists is definitely the way to go. Shows me for answering to quickly. For Chris's information, this way, the same as the first method Peter mentioned would obviously work, it just isn't the optimized way to handle this problem.
0

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

Improve this answer

Comments

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.