配售的ArrayList內容到PriorityQueue中的Java問題

Question

我有下面的代碼，這是造成了一個問題：

List<Node> tempList=new ArrayList<Node>(); //baseline 
//creation of another temporary list of type Node for temporary storage 
List<Node> tempList2=new ArrayList<Node>(); 

List<Node> temp = Adjacency_List.get(current.dest); 
for(Node node: temp){ 
    //testing 
    System.out.print(current.dest + " - " + node.dest); 
     System.out.println("\t\t("+Main.getEdge(current, node)+")"); 

    for(int i=0; i<tempList.size(); i++){ 
     //copying nodes from tempList into tempList2 
     tempList2.add(tempList.get(i)); 
     System.out.println("TEMP LIST2 : "+tempList2.size()); 
    } 

    tempList2.add(node); 
    System.out.println("TEMP LIST2 SIZE : "+tempList2.size()); 
    cost=tempCost; 
    cost+=Main.getEdge(current, node); 
    n=new Node(tempList2, cost); 
    pq.add(n); 
    tempList2.clear(); 
} 

這段代碼的基本目標是獲取當前節點的兒童（使用current.dest）和對於temp中的每個節點，它將tempList的內容複製到tempList2中（tempList也包含節點）。在將tempList2的內容添加到優先級隊列pq（pq.add（n））後，然後通過使用tempList2.clear()進行清除後，會出現問題。優先級隊列pq內的tempList2的內容也被該行清除。有沒有一種方法可以清除tempList2數組列表的內容，而無需同時清除優先級隊列中的tempList2內容（以前通過使用行pq.add（n）;添加到優先級隊列中）？

Answer 1

是的，這是可能的。

解決方案1 ​​

添加列表的副本，而不是原始列表本身。原件clear()後副本將保持不變。 更改

n = new Node(tempList2, cost); 

到

n = new Node(new ArrayList<>(tempList2), cost); 

解決方案2

這可能是更好的（兩個，efficency和可讀性）創建一個新的列表，而不是複製和清除各同一列表迭代。刪除

tempList2.clear(); 

和移動

List<Node> tempList2 = new ArrayList<Node>(); 

到第一循環的身體，這樣你在創建每個迭代一個新的列表。

Answer 2

當您添加n到pq，您要創建別名：您已添加n列表字段指的是完全相同的實例tempList2指。它的理由是，如果您通過調用clear()來改變該實例，那麼您的隊列也會丟失這些元素。

有2種方法，以避免別名：

1. 複製列表到新列表中插入它，招致O（N）的性能損失上的每個插入（其中N爲tempList的長度）之前。
2. 創建一個新的空列表實例，並將其分配給tempList2，而不是在每次迭代時使用clear()，產生O（1）懲罰。

我要指出的是，如果tempList是有史以來非空，你會使用一個循環與get()浪費週期的負載上覆製成tempList2。 addAll()方法通常更有效。