比较两个链表

Question

比较 Java 中两个链表的最佳方法是什么？我有两个列表，想确保一个列表中的 none 个元素在另一个列表中。像这样的工作两个列表都是 LocalDates 列表。

boolean doesNotContain (LinkedList L1, LinkedList L2) { 
        for(LocalDate d:L1) { 
            if(l2.contains(d){
                return false; 

            } 
        }
       return true;    
}

Answer 1

您的解决方案适用于 N^2 复杂度。如果对两个列表进行排序并在一个循环中迭代它们，则可以在 N log N 中执行 int（即排序复杂度）。

您还可以创建两个包含两个列表中的元素的新 Set，然后使用 containsAll() 方法 - 它会完成所有工作。这是一个干净且易于理解的解决方案。不过可能会占用内存。

比较方法取决于方法 equals() 和 hashCode() - 如果您没有在 LocalDate class 中正确覆盖它们，您将不会得到好的结果。

BTW1：在 return 之后中断是死代码

BTW2：用 "not" 命名方法似乎不是个好主意。您很快就会发现自己在使用 !notFulfills( !notContains(sdflasdf))。祝你好运，想弄清楚它的作用。

Answer 2

由于您对 doesNotContain(..) 的实现与 containsAll(..) 的实现很接近，所以我建议使用那个。如果您执行 list1.containsAll(list2)，该实现将遍历 list2 的所有元素以检查 list1 中是否存在相等的对象。这就是您需要在 LocalDate.

中覆盖 public boolean equals(Object obj) 的原因

在下面找到一个小示例来说明 containsAll(..)

所做的工作

主程序运行检查

public static void main(String[] args) throws Exception {
    List<LocalDate> list1 = new LinkedList<>();
    list1.add(new LocalDate("112233"));
    list1.add(new LocalDate("223344"));

    List<LocalDate> list2 = new LinkedList<>();
    list2.add(new LocalDate("112233"));
    list2.add(new LocalDate("112233"));

    System.out.println("list1 = " + list1);
    System.out.println("list2 = " + list2);

    System.out.println("list1.containsAll(list2) = " + list1.containsAll(list2));
    System.out.println("list2.containsAll(list1) = " + list2.containsAll(list1));
}

如果您实现 LocalDate 而不重写 equals 方法，则只有当您比较相同对象的引用时，equals 才会为真。

// a naive implementation for demonstration purpose
class LocalDate {

    String hour;
    String minute;
    String second;

    LocalDate(String string) {
        hour = string.substring(0, 2);
        minute = string.substring(2, 4);
        second = string.substring(4, 6);
    }

    @Override
    public String toString() {
        return String.format("LocalDate{%s%s%s} - hashcode: %d", hour, minute, second, this.hashCode());
    }
}

结果会是

list1 = [LocalDate{112233} - hashcode: 33039820, LocalDate{223344} - hashcode: 31311199]
list2 = [LocalDate{112233} - hashcode: 13177912, LocalDate{112233} - hashcode: 21924553]
list1.containsAll(list2) = false
list2.containsAll(list1) = false

如果您覆盖 equals 方法（出于演示目的省略了 hashcode）

@Override
public boolean equals(Object obj) {
    if (obj == null) {
        return false;
    }
    if (getClass() != obj.getClass()) {
        return false;
    }
    final LocalDate other = (LocalDate) obj;
    System.out.println(toString() + ".equals(" + obj.toString() + ')');
    if (!Objects.equals(this.hour, other.hour)) {
        return false;
    }
    if (!Objects.equals(this.minute, other.minute)) {
        return false;
    }
    if (!Objects.equals(this.second, other.second)) {
        return false;
    }
    return true;
}

输出将是

list1 = [LocalDate{112233} - hashcode: 33336787, LocalDate{223344} - hashcode: 12767201]
list2 = [LocalDate{112233} - hashcode: 31311199, LocalDate{112233} - hashcode: 13177912]
// generated output by the method containsAll(..)
LocalDate{112233} - hashcode: 31311199.equals(LocalDate{112233} - hashcode: 33336787)
LocalDate{112233} - hashcode: 13177912.equals(LocalDate{112233} - hashcode: 33336787)
list1.containsAll(list2) = true
// generated output by the method containsAll(..)
LocalDate{112233} - hashcode: 33336787.equals(LocalDate{112233} - hashcode: 31311199)
LocalDate{223344} - hashcode: 12767201.equals(LocalDate{112233} - hashcode: 31311199)
LocalDate{223344} - hashcode: 12767201.equals(LocalDate{112233} - hashcode: 13177912)
list2.containsAll(list1) = false

根据打印的 Object.hashcode()，您可以很容易地看到 containsAll() 方法循环遍历您调用该方法的列表中的所有元素。

如果你想改进检查你需要先弄清楚以下几点 - 列表中的元素是否唯一 -> 那么最好使用 Set - 列表必须具有相同数量的元素 -> 如果是，您可以在第一步中比较它们的大小 - 如果您只需要检查 list2 仅包含 list1 中的元素（意味着列表包含唯一值）-> 调用 list2 上的 containsAll 方法 - 之前对列表进行排序可能也是值得的（取决于包含的数据）

如果没有这些信息，就不可能给出在所有情况下都会 the best 的建议。

比较两个链表

Compare two Linked Lists

java

linked-list