java - 检查多个列表中公共(public)元素的最佳方法？

Question

我明白 ArrayList<>的搜索速度最快( O(1) 与 O(n) )和 LinkedList<>的插入和删除速度最快( O(1) 与 O(n) )。

我的问题是，如果结合使用这两者，检查多个列表 (>2) 中常见元素的最佳方法是什么？

当前方法 使用三个列表和迭代方法:

out:
for(int a = 0; a < list1.size(); a++) {
    for(int b = 0; b < list2.size(); b++) {
        for(int c = 0; c < list3.size(); c++) {
            if(list1.get(a) == list2.get(b) && list1.get(a) == list3.get(c) ) {
                System.out.println(list1.get(a)); // list2.get(b) or list3.get(c) could have been subbed
                break out;
            }
        }
    } 
}

如何优化以提高效率？

---

编辑

感谢许多有用的回复:) 我发现最好的方法是使用列表 .retainAll()功能。

同样，为了找到三个列表之间的共同元素，我改进了下面的方法。

list1.retainAll(list2);
list1.retainAll(list3);
for(int i : list1) {
    System.out.println(i);
}

Answer 1

假设元素实现hashCode，您可以获得与所有列表中的元素数量成线性关系的预期时间:

public static <T> Set<T> commonElements(List<? extends T> list1, List<? extends T>... lists) {
    // use LinkedList for efficient delete operation
    // make sure elements are distinct to not check the same element multiple times
    List<T> commonElements = new LinkedList<>(new HashSet<>(list1));
    for (List<? extends T> l : lists) {
        // use HashSet for fast contains check
        // keep only elements in the list
        commonElements.retainAll(new HashSet<>(l));
    }
    return new HashSet<>(commonElements);
}

这比您的方法更快，因为 HashSet 允许在 O(1) 预期时间内查找。

请注意，对于较小的输入列表，这种方法的性能可能会更差。