比较两个列表的算法

Question

我有一个对象列表要显示在屏幕上。 用户可以随意更改它们，然后点击提交。 在提交方法中，我将原始列表与当前列表进行比较，并创建第三个列表，其中包含所有已添加、删除或更改的对象及其操作代码以指定其类型。 这些对象有一个用于标识它们的id，默认为0。

如何实现呢？以下是我能想到的最好方案（伪代码），但看起来有些笨重。

for (currentObject : objects in current list)
    if (currentObject.id is 0)
        //Was added
    for (oldObject : objects in original list)
        if (currentObject.id == oldObject.id)
            //Existed - compare other fields to see if changed

for (oldObject1 : objects in original list)
    boolean existed = false;
    for (currentObject1 : objects in current list)
        if(oldObject1.id == currentObject1.id)
            existed=true;
    if (!existed)
        //Was removed

- bhouse

---

对象ID是唯一的吗？ - Haney

如果您的对象ID是唯一的，那么在比较它们之前，对原始列表和当前列表进行排序可以获得很多好处。 - Olaf

@DavidH 对象ID是从数据库中唯一的。但是在UI上添加的所有对象都将具有ID为0。 - bhouse

Answer 1

如果顺序不重要，你只关心元素是否被添加或移除，那么你可能需要考虑更改数据结构并使用 `Set` 而不是 `List`。`Set` 类型专门设计用于有效地确定元素是否存在，代价是你不再记住元素的顺序。

例如，使用 `HashSet`，你可以执行以下操作：

Set<T> oldElems = new HashSet<T>(originalList);
Set<T> newElems = new HashSet<T>(currentList);

for (T obj : oldElems) {
    if (!newElems.contains(obj)) {
        /* ... this object was removed ... */
    }
}

for (T obj : newElems) {
    if (!oldElems.contains(obj)) {
        /* ... this object was added ... */
    }
}

希望这能帮到您！

- templatetypedef

---

另外，如果我没记错的话，Java有一种方法可以识别两个集合中共同的元素。 - Daniel

@Daniel- 有像 retainAll 和 removeAll 这样的操作，但它们会对原始容器进行破坏性修改。虽然也许这正是 OP 想要的？ - templatetypedef

为了让一个类型在 HashSet 中使用，你需要确保已经正确实现了 equals() 和 hashCode() 方法。我看到你只处理了添加和删除操作，那修改操作呢？ - Costi Ciudatu

@CostiCiudatu- 你可以将修改看作是添加后跟随着删除（或反之亦然）。这种方法在这里行不行？ - templatetypedef

@Daniel 我尝试使用retain all和remove all，但它们都没有起作用。例如，如果我使用oldList.removeAll(newList)来获取所有已删除的元素，它会将修改也计算为删除，但实际上并不是这样。 - bhouse

Answer 2

您可以通过持续维护三种情况的结果列表来使用一个循环实现。如果您可以重写equals()以依赖于id，那就太好了。否则，请检查下面的update代码。

以下是代码，详细解释请见下文：

List<T> origList = ...;
List<T> newList = ...;

List<T> addedList = new ArrayList<T>();
List<T> deletedList = new ArrayList<T>();
List<T> changedList = new ArrayList<T>();

deletedList.addAll(origList);

for(T t : newList) {
    int origIndex = deletedList.indexOf(t);
    if (origIndex < 0) {
        addedList.add(t);
    } else {
        T origT = deletedList.remove(origIndex);
        if(t.compareTo(origT) != 0) {
            changedList.add(t);
        }
    }
}

请注意，我假设equals()将检查id，而compareTo()将检查所有其他字段。 解释： 您从deletedList中删除了与newList中存在的所有元素，因此结果是已删除的项目。

您将所有新元素添加到addedList中，这些元素在原始列表中不存在。

如果两者都存在且对象不同，则它们将进入changedList。

如果两者都存在且对象相同，则我们不会将其添加到任何位置。 注： 如果新对象的ID为0，则它们不会出现在origList中（因为我们假设它们已经被创建）。

上次我实现它时，我创建了一个单独的方法来逐个比较对象的字段，以便我可以将比较逻辑与标准Java方法分离（实际上也声明在一个interface上）。

我使用List创建了这个，但实际上您可以将其用于任何类型的Collection。使用List将保留原始顺序。 更新： 尝试以这种方式覆盖您的equals（我跳过了类型检查和转换）：

public boolean equals(T other) {
    if (this.id == 0) {
        return this == other;
    }
    return this.id == other.id;
}

尚未创建的实例仅等于它们自己。已经创建的实例将通过ID进行检查。

- gaborsch

---

我在覆盖equals方法只检查id时遇到的问题是，当用户点击删除时，我的动作监听器会调用list.remove(Object o)。通过这样覆盖equals方法，会导致一个错误，因为UI上新添加的所有项目都具有id=0。所以当我移除它时，它只是移除找到的第一个id=0的对象，而不一定是他们选择要删除的对象。顺便说一下，这是一个JSF应用程序。 - bhouse

如果您无法使用equals()，那么可以用Iterator循环替换remove()。我会更新我的答案。 - gaborsch

好的，我会看一下。看了你的代码，我觉得你是想用addedList.add(t)而不是newList.add(t)，对吧？那部分让我有点困惑。 - bhouse

@bhouse 是的，我的错误。现在已经更正并添加了 remove() 的代码。 - gaborsch

你提供的equals覆盖很好，可以解决我的另一个问题。那么回到您最初的建议，这一行 T origT = deletedList.remove(t) 这是一个语法错误，因为remove(Obj)返回一个布尔值。基于您试图做什么看起来像，我认为我可以获取布尔值，并将下一个if更改为 if(!booleanReturnedAbove) 但是，我对接下来的一行代码感到困惑。 - bhouse

@bhouse 你是对的，我更新了代码（之前是凭记忆编写的）。现在应该更好了。同时删除了remove()替换的代码，但实际上那可能是一个比这个更有效的解决方案。 - gaborsch