Java：具有項目集合，其中每個項目都有一個字段「previousItem」，訂購集合的最有效方式是什麼？

我有位項目的集合未排序的收藏。每個項目都有一個字段previousItem：Java：具有項目集合，其中每個項目都有一個字段「previousItem」，訂購集合的最有效方式是什麼？

public class Item{ 
    public Item previousItem; 
}

什麼是處理這些物品的最有效的方式使輸出是一個集合，其中沒有任何previousItem該項目是集各subesequent中的第一項item的previousItem是集合中的前一個項目？

我的第一個想法是落實在項目類Comparable接口：通過項目

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

有沒有更有效的方法（減少處理時間/所需迭代的次數）來對集合進行排序，使它們處於邏輯層次順序？

來源

2012-03-12 simon

你的比較是行不通的：它不提供傳遞，即如果你在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); 
}

這將解開你的無序集合從沒有一個節點的項目開始。

這兩種方法都具有大致線性複雜w.r.t.項目的數量，但他們做兩個假設，可能無法在你的情況是有效的：

，每個項目只能最多一個其他節點的前一個項目，即你的項目是一個列表而不是樹。
那有項目的一個「線程」。

如果這些假設無效，您將需要一個更爲複雜的算法來對此進行分類。

來源

2012-03-12 09:13:50 thkala

從我所看到的，你的項目已經在實施一個鏈表（如果不上名字），所以自然（對我來說）的方式把它收集的是把它改造成一個真正的列表遞歸。項目轉換後，您可能需要根據您的規格反轉列表。

public class Item { 
    Item previousItem; 

    public void putToCollection(ArrayList<Item> list) { 
    list.add(this); 
    if (previousItem == null) { 
     Collections.reverse(list); 
    } else { 
     previousItem.putToCollection(list); 
    } 
    } 
}

來源

2012-03-12 09:16:21 Jonathan

如果我正確理解你，你有沒有以前的對象Item對象的句柄。您可以循環瀏覽項目（例如帶一個while循環）並將它們添加到一個ArrayList或一個LinkedList，因爲這些List實現的add（）方法只是在列表的末尾附加一個新的Item。這樣，你可以在O（n）時間內完成它。

來源

2012-03-12 09:16:44 ftr

您可以使用HashSet<Item>，其中您最初放置所有項目。然後你在一個循環中檢查項目，並從你的設置中刪除每個previousItem。在最後，你應該留下一個單一的元素，最後一個，這不是一個previousItem任何其他項目。然後你可以簡單地從這個項目開始添加項目並瀏覽鏈接。

來源

2012-03-12 09:20:07 Vlad

Java：具有項目集合，其中每個項目都有一個字段「previousItem」，訂購集合的最有效方式是什麼？

回答

相關問題