Java: .contains and .equals

Question

I'm trying to execute a program, to compare elements in two linked list with each other. one way, i can do this is by executing two for loops and iterating over both the lists comparing each element in list1 with list2 using .equals(). the other way is, just iterating over the first list and checking if list1.contains(list1.get(i)) .. the java documentation says, that .contains does .equals internally. if that's the case, how is that my running time for the former is longer when compared to the latter? Did I misinterpret the documentation? If I did, how exactly does the internal comparison take place when I use contains?

            using equals:
            for (int i = 0; i < list_one.size(); i++) {
              for (int j = 0; j < list_one.size(); j++) {
                  if (list_one.get(i).equals(list_two.get(j))) { count++; }

            using contains:
            for (int i = 0; i < list_one.size(); i++) {
                 if (list_two.contains(list_one.get(i)) == true) { count++; }

Solution 1

The implementation of contains will stop iterating once equals returns true, so it doesn't iterate the whole list if the element you're looking for is somewhere at the beginning of the list. If your version does not do that, that would explain why it is slower.

PS: Either way the running time will still be quadratic. There are smarter ways to solve this problem that do not involve iterating through the second list for every item in the first list (for example by sorting the two lists first or using a set).

Solution 2

I think, seeing get(i) that you are using get(j) in both loops. In a linked list that is inefficient. for (String s1 : list1) for (String s2 : list2) ... should have same speed as contains.

For instance get(3) would need to start with the first element, take the link to the next three times. Whereas the for-each uses an iterator pointing at the next element.