Java:有一个项目集合，其中每个项目都有一个字段 "previousItem"，对集合进行排序的最有效方法是什么？

Question

我有一个未排序集合中的分层项目集合。每个项目都有一个字段 previousItem:

public class Item{
   public Item previousItem;
}

处理这些项目的最有效方法是什么，以便输出是一个集合，其中没有任何 previousItem 的 Item 是集合中的第一个 Item，而每个后续项目的 previousItem 是集合中的前一个项目？

我的第一个想法是在 Item 类中实现 Comparable 接口(interface):

public int compareTo(Item that) {
    final int BEFORE = -1;
    final int EQUAL = 0;
    final int AFTER = 1;

    if(this.previousItem==null){
        return BEFORE;
    }

    if(that.previousItem==null){
        return AFTER;
    }

    if(this.previousItem.equals(that){
        return AFTER;
    }else if(that.previousItem.equals(this){
        return BEFORE;
    }

    return EQUAL;
}

然后循环遍历这些项目并将它们添加到 TreeSet 中:

SortedSet<Item> itemSortedSet = new TreeSet<Item>();
for (Item item : itemCollection) {
    itemSortedSet.add(item);
}

是否有更有效的方法(更少的处理时间/所需的迭代次数)来对集合进行排序，以便它们按逻辑、分层顺序排列？

Answer 1

您的比较器将不起作用:它不提供传递性，即如果您在 A->B->C 的情况下比较项目 A 和 C，它会做错误的事情。

如果没有项目可以具有相同的前一个项目，则您的Item对象本质上形成一个基本的链接列表。如果您碰巧知道哪一项是最后一项，您可以从那里开始使用单个循环并解开整个结构:

Item last = ...;

while (last != null) {
    result.add(last)
    last = last.previousItem
}

如果您无法找出哪一项是最后一项，那么您可以使用 IdentityHashMap将每个 previousItem 值映射到使用它的 Item 对象:

IdentityHashMap<Item,Item> m = new IdentityHashMap<Item,Item>(itemset.size());

for (Item i : itemset)
    m.put(i.previousItem, i);

Item i = m.get(null);

while (i != null) {
    result.add(i);

    i = m.get(i);
}

这将从没有前一个节点的项目开始解开未排序的集合。

这两种方法都具有大致线性的复杂度。项目的数量，但他们做出了两个假设，这些假设在您的情况下可能无效:

• 每个项目只能是最多一个个其他节点的前一项，即您的项目是一个列表而不是树。

• 只有一个项目“线程”。

如果这些假设中的任何一个都不成立，您将需要一个更复杂的算法来解决这个问题。