将 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

创建一个新列表而不是在每次迭代中复制和清除同一个列表可能更好（对于效率和可读性）。移除

tempList2.clear();

并移动

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

到第一个循环的主体，这样您就可以在每次迭代中创建一个新列表。

Answer 2

当您将 n 添加到 pq 时，您正在创建一个别名：您添加的 n 的列表字段指的是 tempList2 所指的完全相同的实例。按理说，如果您通过调用 clear() 来改变该实例，您的队列也会丢失元素。

有两种方法可以避免别名：

在插入之前将列表复制到新列表，每次插入都会导致 O(N) 性能损失（其中 N 是 tempList 的长度）。
创建一个新的空列表实例并将其分配给 tempList2 而不是在每次迭代中使用 clear()，从而导致 O(1) 的惩罚。

我应该指出，如果 tempList 曾经是非空的，那么使用带有 get() 的循环将其复制到 tempList2 会浪费大量循环。 addAll() 方法通常更有效。

将 ArrayList 的内容放入 PriorityQueue Java 问题

Placing contents of ArrayList into PriorityQueue Java Issue

java

arraylist

priority-queue

nodes

解决方案 1

解决方案 2