Maneira simples de descobrir se duas listas diferentes contêm exatamente os mesmos elementos?

Qual é a maneira mais simples de descobrir se duas listas contêm exatamente os mesmos elementos, nas bibliotecas Java padrão?

Não importa se as duas listas são da mesma instância ou não, e não importa se o parâmetro de tipo das listas é diferente.

por exemplo

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

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

Provavelmente há algo me encarando, eu sei :-)

Edição: Para esclarecer, eu estava procurando exatamente os mesmos elementos e número de elementos, em ordem.

Se você se preocupa com a ordem, basta usar o método equals:

list1.equals(list2)

Do javadoc:

Compara o objeto especificado com esta lista para igualdade. Retorna true se e somente se o objeto especificado também for uma lista, ambas as listas têm o mesmo tamanho e todos os pares de elementos correspondentes nas duas listas são iguais. (Dois elementos e1 e e2 são iguais se (e1 == null? E2 == null: e1.equals (e2)).) Em outras palavras, duas listas são definidas como iguais se contiverem os mesmos elementos na mesma ordem . Essa definição garante que o método equals funcione corretamente em diferentes implementações da interface List.

Se você deseja verificar independentemente da ordem, copie todos os elementos para Conjuntos e use iguais nos Conjuntos resultantes:

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

Uma limitação dessa abordagem é que ela não apenas ignora a ordem, mas também a frequência de elementos duplicados. Por exemplo, se list1fosse ["A", "B", "A"] e list2fosse ["A", "B", "B"], a Setabordagem os consideraria iguais.

Se você precisar ser insensível ao pedido, mas sensível à frequência de duplicatas, poderá:

• classifique as duas listas (ou cópias) antes de compará-las, conforme feito nesta resposta a outra pergunta
• ou copie todos os elementos para um Multiset

Publiquei um monte de coisas nos comentários que acho que justificam sua própria resposta.

Como todos dizem aqui, o uso de equals () depende da ordem. Se você não se importa com o pedido, tem 3 opções.

Opção 1

Use containsAll(). Esta opção não é ideal, na minha opinião, porque oferece o pior desempenho, O (n ^ 2).

opção 2

Existem duas variações para isso:

2a) Se você não se importa em manter a ordem de suas listas ... use Collections.sort()nas duas listas. Então use o equals(). Este é O (nlogn), porque você faz duas classificações e, em seguida, uma comparação O (n).

2b) Se você precisar manter a ordem das listas, poderá copiar as duas listas primeiro. ENTÃO, você pode usar a solução 2a nas duas listas copiadas. No entanto, isso pode não ser atraente se a cópia for muito cara.

Isto leva a:

Opção 3

Se seus requisitos forem os mesmos da parte 2b , mas a cópia é muito cara. Você pode usar um TreeSet para fazer a classificação para você. Despejar cada lista em seu próprio TreeSet. Ele será classificado no conjunto e as listas originais permanecerão intactas. Em seguida, faça uma equals()comparação nos dois TreeSets. Os TreeSetss podem ser construídos no tempo O (nlogn) e o equals()é O (n).

Faça sua escolha :-).

Edição: Eu quase esqueci a mesma ressalva que Laurence Gonsalves aponta. A implementação do TreeSet eliminará duplicatas. Se você se preocupa com duplicatas, precisará de algum tipo de conjunto múltiplo classificado.

Se você estiver usando (ou estiver satisfeito em usar) o Apache Commons Collections, poderá usar o CollectionUtils.isEqualCollection que "retorna verdadeiro se as coleções fornecidas contiverem exatamente os mesmos elementos com as mesmas cardinalidades".

Muito tarde para a festa, mas queria adicionar esta verificação segura nula:

Objects.equals(list1, list2)

Sei que esse é um encadeamento antigo, mas nenhuma das outras respostas resolveu completamente meu caso de uso (acho que o Guava Multiset pode fazer o mesmo, mas não há exemplo aqui). Por favor, desculpe minha formatação. Ainda sou novo em postar na troca de pilhas. Além disso, deixe-me saber se há algum erro

Vamos dizer que você tem List<T>um e List<T>b e quiser verificar se eles são iguais com as seguintes condições:

1) O (n) tempo de execução esperado
2) Igualdade é definida como: Para todos os elementos em a ou b, o número de vezes que o elemento ocorre em a é igual ao número de vezes que o elemento ocorre em b. Igualdade de elementos é definida 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;
}

O tempo de execução é O (n) porque estamos fazendo inserções O (2 * n) em um mapa de hash e O (3 * n) seleciona o hashmap. Eu não testei completamente esse código, então 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);

Experimente esta versão que não exige que o pedido seja o mesmo, mas suporta ter vários do mesmo valor. Eles correspondem apenas se cada um tiver a mesma quantidade de qualquer 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();
}

O método equals na lista fará isso; as listas são ordenadas; portanto, para serem iguais, duas listas devem ter os mesmos elementos na mesma ordem.

return list1.equals(list2);

Solução para casos em que duas listas têm os mesmos elementos, mas ordem 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());
}

A resposta de Tom é excelente. Concordo plenamente com as respostas dele!

Um aspecto interessante dessa pergunta é se você precisa do Listtipo em si e de sua ordem inerente.

Caso contrário, você poderá degradar para Iterableou o Collectionque lhe dará alguma flexibilidade ao passar pelas estruturas de dados classificadas no tempo de inserção, e não no momento em que você deseja verificar.

Se o pedido nunca for importante (e você não tiver elementos duplicados), considere usar a Set.

Se o pedido importa, mas é definido pelo tempo de inserção (e você não possui duplicatas), considere um LinkedHashSetque é como um TreeSet, mas que é ordenado pelo tempo de inserção (as duplicatas não são contadas). Isso também fornece a você O(1)acesso amortizado instalado O(log n).

Código de amostra:

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

Além da resposta de Laurence, se você também deseja torná-lo seguro para nulos:

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

Se sua lista contiver uma Classe MyClass personalizada, essa classe deverá substituir a equalsfunção.

 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: se você deseja testar iguais em um java.util.Set em vez de em um java.util.List, seu objeto deve substituir a hashCode função.

List.equals ()

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

Você pode usar a biblioteca org.apache.commons.collections do 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)

Verifique se as duas listas não são nulas. Se seus tamanhos forem diferentes, essas listas não serão iguais. Crie mapas que consistam nos elementos das listas como chaves e suas repetições como valores e compare os mapas.

Pressupostos, se ambas as listas são nulas, considero-as iguais.

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

Observe que o método igual deve ser definido corretamente para esses objetos. https://stackoverflow.com/a/24814634/4587961

Depende de qual classe List concreta você está usando. A classe abstrata AbstractCollection possui um método chamado containsAll (Collection) que recebe outra coleção (uma List é uma coleção) e:

Retorna true se esta coleção contiver todos os elementos na coleção especificada.

Portanto, se um ArrayList estiver sendo passado, você poderá chamar esse método para ver se eles são exatamente iguais.

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

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

    foo.containsAll(bar);

O motivo de containsAll () é porque ele percorre a primeira lista procurando a correspondência na segunda lista. Portanto, se estiverem fora de ordem, igual a () não será atendido.

Edição: Eu só quero fazer um comentário aqui sobre o tempo de execução amortizado de executar as várias opções oferecidas. O tempo de execução é importante? Certo. É a única coisa que você deve considerar? Não.

O custo de copiar TODOS os elementos únicos de suas listas para outras listas leva tempo e também ocupa um bom pedaço de memória (duplicando efetivamente a memória que você está usando).

Portanto, se a memória em sua JVM não for uma preocupação (o que geralmente deve ser), você ainda precisará considerar o tempo necessário para copiar cada elemento de duas listas em dois TreeSets. Lembre-se de que ele está classificando todos os elementos à medida que eles entram.

Meu conselho final? Você precisa considerar seu conjunto de dados e quantos elementos você possui em seu conjunto de dados e também qual o tamanho de cada objeto em seu conjunto de dados antes de tomar uma boa decisão aqui. Brinque com eles, crie um de cada lado e veja qual deles corre mais rápido. É um bom exercício.