CODEWITHSUNDEEP
javaarraylistnodespriority-queue
Alisinna
Alisinna

Reputation: 121

Placing contents of ArrayList into PriorityQueue Java Issue

I have the following code which is causing a problem:

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

This code's basic aim is to get the children of the current node (by using current.dest) and for each Node in temp, it copies the contents of tempList into tempList2 (tempList contains Nodes as well). The problem arises when after the contents of tempList2 are added to priority queue pq (pq.add(n)) and then cleared by using tempList2.clear(). The contents of tempList2 within the priority queue pq are also being cleared by this line. Is there a way I can clear the contents of tempList2 array list without simultaneously clearing the contents of tempList2 within the priority queue (previously added to the priority queue through the use of line pq.add(n);)?

Upvotes: 0

Views: 837

Answers (2)

Judge Mental
Judge Mental

Reputation: 5239

When you add n to pq, you're creating an alias: the List field of n you've added refers to the exact same instance that tempList2 refers to. It stands to reason that if you mutate that instance by calling clear(), your queue loses the elements as well.

There are 2 ways to avoid the alias:

  1. Copy the list to a new list before inserting it, incurring a O(N) performance penalty on every insertion (where N is the length of tempList).
  2. Create a new, empty list instance and assign it to tempList2 instead of using clear() on each iteration, incurring a O(1) penalty.

I should point out that if tempList were ever non-empty, you would be wasting loads of cycles on copying it into tempList2 using a loop with get(). The addAll() method is generally more efficient.

Upvotes: 1

Socowi
Socowi

Reputation: 27235

Yes it is possible.

Solution 1

Add a copy of your list instead of the original list itself. The copy will remain unchanged after you clear() the original. Change

n = new Node(tempList2, cost);

to

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

Solution 2

It may be better (for both, efficency and readability) to create a new list instead of copying and clearing the same list in each iteration. Remove

tempList2.clear();

and move

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

to the first loop's body, such that you create a new list in each iteration.

Upvotes: 1

Related Questions