Java: .contains y .equals

Question

Estoy tratando de ejecutar un programa, para comparar elementos en dos listas vinculadas entre sí. unidireccional, puedo hacerlo ejecutando dos loops e iterando sobre las listas que comparan cada elemento en list1 con list2 usando .equals(). a la inversa, simplemente iterando sobre la primera lista y comprobando si list1.contains (list1.get (i)) ... la documentación de Java dice que .contains hace .equals internamente. si ese es el caso, ¿cómo es que mi tiempo de ejecución para el primero es más largo en comparación con este último? ¿He malinterpretado la documentación? Si lo hice, ¿cómo exactamente tiene lugar la comparación interna cuando uso contiene?

  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++; } 

Answer 1

creo, viendo get(i) que está utilizando get(j) en ambos bucles. En una lista vinculada que es ineficiente. for (String s1 : list1) for (String s2 : list2) ... debe tener la misma velocidad que contains.

Por ejemplo get (3) necesitaría comenzar con el primer elemento, lleve el enlace a las siguientes tres veces. Mientras que el for-each usa un iterador que apunta al siguiente elemento.

Answer 2

La implementación de contains dejará de iterar una vez que equals devuelve verdadero, por lo que no itera toda la lista si el elemento que está buscando está en algún lugar al principio de la lista. Si su versión no hace eso, eso explicaría por qué es más lento.

PD: De cualquier forma, el tiempo de ejecución seguirá siendo cuadrático. Hay formas más inteligentes de resolver este problema que no implican iterar a través de la segunda lista para cada elemento en la primera lista (por ejemplo, ordenando las dos listas primero o usando un conjunto).