¿Manera simple de encontrar si dos listas diferentes contienen exactamente los mismos elementos?

¿Cuál es la forma más sencilla de encontrar si dos Listas contienen exactamente los mismos elementos, en las bibliotecas estándar de Java?

No debería importar si las dos Listas son la misma instancia o no, y no debería importar si el parámetro de tipo de las Listas es diferente.

p.ej

List list1
List<String> list2; 
// ... construct etc

list1.add("A");
list2.add("A"); 
// the function, given these two lists, should return true

Probablemente hay algo mirándome a la cara que sé :-)

EDITAR: Para aclarar, estaba buscando los mismos elementos EXACTOS y el número de elementos, en orden.

Si le importa el orden, simplemente use el método igual:

list1.equals(list2)

Desde el javadoc:

Compara el objeto especificado con esta lista para la igualdad. Devuelve verdadero si y solo si el objeto especificado es también una lista, ambas listas tienen el mismo tamaño y todos los pares de elementos correspondientes en las dos listas son iguales. (Dos elementos e1 y e2 son iguales si (e1 == null? E2 == null: e1.equals (e2)).) En otras palabras, dos listas se definen como iguales si contienen los mismos elementos en el mismo orden . Esta definición garantiza que el método equals funcione correctamente en diferentes implementaciones de la interfaz List.

Si desea verificar independientemente del orden, puede copiar todos los elementos en Conjuntos y usar iguales en los Conjuntos resultantes:

public static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}

Una limitación de este enfoque es que no solo ignora el orden, sino también la frecuencia de elementos duplicados. Por ejemplo, si list1fue ["A", "B", "A"] y list2fue ["A", "B", "B"], el Setenfoque los consideraría iguales.

Si necesita ser insensible al orden pero sensible a la frecuencia de los duplicados, puede:

• ordene ambas listas (o copias) antes de compararlas, como se hace en esta respuesta a otra pregunta
• o copie todos los elementos a un Multiset

Publiqué un montón de cosas en los comentarios, creo que justifica su propia respuesta.

Como todos dicen aquí, usar equals () depende del orden. Si no le importa el orden, tiene 3 opciones.

Opción 1

Uso containsAll(). Esta opción no es ideal, en mi opinión, porque ofrece el peor rendimiento posible, O (n ^ 2).

opcion 2

Hay dos variaciones a esto:

2a) Si no le importa mantener el orden de sus listas ... úselas Collections.sort()en ambas. Luego usa el equals(). Esto es O (nlogn), porque haces dos tipos, y luego una comparación O (n).

2b) Si necesita mantener el orden de las listas, puede copiar ambas listas primero. ENTONCES puede usar la solución 2a en ambas listas copiadas. Sin embargo, esto podría no ser atractivo si la copia es muy costosa.

Esto lleva a:

Opción 3

Si sus requisitos son los mismos que en la parte 2b , pero copiar es demasiado costoso. Puede usar un TreeSet para hacer la clasificación por usted. Volcar cada lista en su propio TreeSet. Se ordenará en el conjunto y las listas originales permanecerán intactas. Luego realice una equals()comparación en ambos TreeSets. El TreeSetss se puede construir en tiempo O (nlogn), y equals()es O (n).

Elige tu opción :-).

EDITAR: Casi olvido la misma advertencia queseñala Laurence Gonsalves . La implementación de TreeSet eliminará los duplicados. Si le interesan los duplicados, necesitará algún tipo de multiset ordenado.

Si está usando (o está contento de usar) Colecciones Apache Commons, puede usar CollectionUtils.isEqualCollection que "devuelve verdadero si las Colecciones dadas contienen exactamente los mismos elementos con exactamente las mismas cardinalidades".

Muy tarde a la fiesta, pero quería agregar este cheque seguro nulo:

Objects.equals(list1, list2)

Sé que este es un hilo viejo, pero ninguna de las otras respuestas resolvió por completo mi caso de uso (supongo que Guava Multiset podría hacer lo mismo, pero no hay ningún ejemplo aquí). Por favor disculpe mi formateo. Todavía soy nuevo en publicar en el intercambio de pila. Además, avíseme si hay algún error

Digamos que tiene List<T>una y List<T>b y desea comprobar si son iguales, con las siguientes condiciones:

1) O (n) tiempo de ejecución esperado
2) La igualdad se define como: Para todos los elementos en aob, el número de veces que el elemento ocurre en a es igual al número de veces que el elemento ocurre en b. La igualdad de elementos se define como T.equals ()

private boolean listsAreEquivelent(List<? extends Object> a, List<? extends Object> b) {
    if(a==null) {
        if(b==null) {
            //Here 2 null lists are equivelent. You may want to change this.
            return true;
        } else {
            return false;
        }
    }
    if(b==null) {
        return false;
    }
    Map<Object, Integer> tempMap = new HashMap<>();
    for(Object element : a) {
        Integer currentCount = tempMap.get(element);
        if(currentCount == null) {
            tempMap.put(element, 1);
        } else {
            tempMap.put(element, currentCount+1);
        }
    }
    for(Object element : b) {
        Integer currentCount = tempMap.get(element);
        if(currentCount == null) {
            return false;
        } else {
            tempMap.put(element, currentCount-1);
        }
    }
    for(Integer count : tempMap.values()) {
        if(count != 0) {
            return false;
        }
    }
    return true;
}

El tiempo de ejecución es O (n) porque estamos haciendo O (2 * n) inserciones en un hashmap y O (3 * n) selecciones de hashmap. No he probado completamente este código, así que ten cuidado :)

//Returns true:
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","A"));
listsAreEquivelent(null,null);
//Returns false:
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("B","A","B"));
listsAreEquivelent(Arrays.asList("A","A","B"),Arrays.asList("A","B"));
listsAreEquivelent(Arrays.asList("A","A","B"),null);

Pruebe esta versión que no requiere que el orden sea el mismo, pero admite tener múltiples del mismo valor. Solo coinciden si cada uno tiene la misma cantidad de cualquier valor.

public boolean arraysMatch(List<String> elements1, List<String> elements2) {
    // Optional quick test since size must match
    if (elements1.size() != elements2.size()) {
        return false;
    }
    List<String> work = newArrayList(elements2);
    for (String element : elements1) {
        if (!work.remove(element)) {
            return false;
        }
    }
    return work.isEmpty();
}

El método igual en Lista hará esto, las listas están ordenadas, por lo que para ser iguales, dos listas deben tener los mismos elementos en el mismo orden.

return list1.equals(list2);

Solución para el caso cuando dos listas tienen los mismos elementos, pero un orden diferente:

public boolean isDifferentLists(List<Integer> listOne, List<Integer> listTwo) {
    if(isNullLists(listOne, listTwo)) {
        return false;
    }

    if (hasDifferentSize(listOne, listTwo)) {
        return true;
    }

    List<Integer> listOneCopy = Lists.newArrayList(listOne);
    List<Integer> listTwoCopy = Lists.newArrayList(listTwo);
    listOneCopy.removeAll(listTwoCopy);

    return CollectionUtils.isNotEmpty(listOneCopy);
}

private boolean isNullLists(List<Integer> listOne, List<Integer> listTwo) {
    return listOne == null && listTwo == null;
}

private boolean hasDifferentSize(List<Integer> listOne, List<Integer> listTwo) {
    return (listOne == null && listTwo != null) || (listOne != null && listTwo == null) || (listOne.size() != listTwo.size());
}

La respuesta de Tom es excelente. ¡Estoy totalmente de acuerdo con sus respuestas!

Un aspecto interesante de esta pregunta es si necesita el Listtipo en sí y su ordenamiento inherente.

De lo contrario, puede degradarse Iterableo Collectionle da cierta flexibilidad para pasar estructuras de datos que se ordenan en el momento de la inserción, en lugar de en el momento en que desea verificar.

Si el orden nunca importa (y no tiene elementos duplicados) considere usar a Set.

Si el orden importa pero está definido por el tiempo de inserción (y no tiene duplicados) considere uno LinkedHashSetque es como un TreeSet pero está ordenado por tiempo de inserción (los duplicados no se cuentan). Esto también le da O(1)acceso amortizado en lugar de O(log n).

Código de muestra:

public static '<'T'>' boolean isListDifferent(List'<'T'>' previousList,
        List'<'T'>' newList) {

    int sizePrevoisList = -1;
    int sizeNewList = -1;

    if (previousList != null && !previousList.isEmpty()) {
        sizePrevoisList = previousList.size();
    }
    if (newList != null && !newList.isEmpty()) {
        sizeNewList = newList.size();
    }

    if ((sizePrevoisList == -1) && (sizeNewList == -1)) {
        return false;
    }

    if (sizeNewList != sizePrevoisList) {
        return true;
    }

    List n_prevois = new ArrayList(previousList);
    List n_new = new ArrayList(newList);

    try {
        Collections.sort(n_prevois);
        Collections.sort(n_new);
    } catch (ClassCastException exp) {
        return true;
    }

    for (int i = 0; i < sizeNewList; i++) {
        Object obj_prevois = n_prevois.get(i);
        Object obj_new = n_new.get(i);
        if (obj_new.equals(obj_prevois)) {
            // Object are same
        } else {
            return true;
        }
    }

    return false;
}

Además de la respuesta de Laurence, si también desea que sea nulo seguro:

private static <T> boolean listEqualsIgnoreOrder(List<T> list1, List<T> list2) {
    if (list1 == null)
        return list2==null;
    if (list2 == null)
        return list1 == null;
    return new HashSet<>(list1).equals(new HashSet<>(list2));
}

list1.equals(list2);

Si su lista contiene una clase personalizada MyClass, esta clase debe anular la equalsfunción.

 class MyClass
  {
  int field=0;
  @0verride
  public boolean equals(Object other)
        {
        if(this==other) return true;
        if(other==null || !(other instanceof MyClass)) return false;
        return this.field== MyClass.class.cast(other).field;
        }
  }

Nota: si desea probar iguales en java.util.Set en lugar de a java.util.List, entonces su objeto debe anular la hashCode función.

List.equals ()

http://java.sun.com/j2se/1.5/docs/api/java/util/List.html#equals(java.lang.Object)

Puede usar la biblioteca org.apache.commons.collections de Apache: http://commons.apache.org/collections/apidocs/org/apache/commons/collections/ListUtils.html

public static boolean isEqualList(java.util.Collection list1,
                              java.util.Collection list2)

Compruebe que ambas listas no son nulas. Si sus tamaños son diferentes, entonces estas listas no son iguales. Cree mapas que consten de los elementos de las listas como claves y sus repeticiones como valores y compare los mapas.

Suposiciones, si ambas listas son nulas, las considero iguales.

private boolean compareLists(List<?> l1, List<?> l2) {
    if (l1 == null && l2 == null) {
        return true;
    } else if (l1 == null || l2 == null) {
        return false;
    }

    if (l1.size() != l2.size()) {
        return false;
    }

    Map<?, Integer> m1 = toMap(l1);
    Map<?, Integer> m2 = toMap(l2);

    return m1.equals(m2);
}

private Map<Object, Integer> toMap(List<?> list) {
    //Effective size, not to resize in the future.
    int mapSize = (int) (list.size() / 0.75 + 1);
    Map<Object, Integer> map = new HashMap<>(mapSize);

    for (Object o : list) {
        Integer count = map.get(o);
        if (count == null) {
            map.put(o, 1);
        } else {
            map.put(o, ++count);
        }
    }

    System.out.println(map);
    return map;
}

Tenga en cuenta que los métodos iguales deben definirse adecuadamente para estos objetos. https://stackoverflow.com/a/24814634/4587961

Depende de qué clase de Lista concreta esté utilizando. La clase abstracta AbstractCollection tiene un método llamado contiene todo (Colección) que toma otra colección (una Lista es una colección) y:

Devuelve verdadero si esta colección contiene todos los elementos de la colección especificada.

Entonces, si se pasa una ArrayList, puede llamar a este método para ver si son exactamente iguales.

       List foo = new ArrayList();
    List bar = new ArrayList();
    String str = "foobar";

    foo.add(str);
    bar.add(str);

    foo.containsAll(bar);

La razón de contieneTodo () es porque itera a través de la primera lista buscando la coincidencia en la segunda lista. Entonces, si están fuera de servicio, igual a () no lo recogerá.

EDITAR: Solo quiero hacer un comentario aquí sobre el tiempo de ejecución amortizado de realizar las diversas opciones que se ofrecen. ¿Es importante el tiempo de ejecución? Por supuesto. ¿Es lo único que debes considerar? No.

El costo de copiar CADA elemento individual de sus listas en otras listas lleva tiempo, y también ocupa una buena parte de la memoria (duplicando efectivamente la memoria que está utilizando).

Entonces, si la memoria en su JVM no es una preocupación (que generalmente debería serlo), entonces aún debe considerar el tiempo que lleva copiar cada elemento de dos listas en dos TreeSets. Recuerde que está ordenando cada elemento a medida que ingresa en ellos.

¿Mi último consejo? Debe considerar su conjunto de datos y cuántos elementos tiene en su conjunto de datos, y también qué tan grande es cada objeto en su conjunto de datos antes de poder tomar una buena decisión aquí. Juegue con ellos, cree uno en cada sentido y vea cuál corre más rápido. Es un buen ejercicio.