Behaviour of ArrayList in recursive method

Question

I have an ArrayList of vectors which I am trying to find all possible distinct paths (without repeating the same node). But the ArrayList keeping record of the path seems to be shared and therefore leaking across all paths. My question is, is there an alternative list type that I should be using which prevents this? Thanks.

The available paths are (A->B, B->C, C->D, D->A, A->C)

For a start, I decided to deal with just paths with starting node A.

The output should be:
ABCD
ACD

I've written the code below with additional output to check what is going on as it is not working right. The output for the code below is:

Previous vector: SA
vector history size: 1
Next vector: AB
Previous vector: AB
vector history size: 2
Next vector: BC
Previous vector: BC
vector history size: 3
Next vector: CD
Previous vector: CD
vector history size: 4
Next vector: DA
Looped - ABCDA
ABCDA
ABC
AB
vector history size: 4
Next vector: AC
Looped - AC
AC

As you can see the last 4 lines from the second iteration of the while loop are wrong because the vector history size should be 1 (SA only) and "C" should not have been visited before but somehow the ArrayList for vector history from the first while loop's recursion has leaked over. Is this suppose to happen and what alternatives are there?

public static void main(String[] args) {

    ArrayList<vector> vectorList = new ArrayList();
    vectorList.add(new vector("A", "B"));
    vectorList.add(new vector("B", "C"));
    vectorList.add(new vector("C", "D"));
    vectorList.add(new vector("D", "A"));
    vectorList.add(new vector("A", "C"));

    //to record vector history and initialize the start vector
    ArrayList<vector> vectorHistory = new ArrayList();

    //record the path 
    String path = "";

    //method call
    pathFinder(new vector("S", "A"), vectorHistory, vectorList, path);
}

//Recursive method. moves one node forward until there is no more nodes OR the next node is the same as a previously taken node

public static void pathFinder(vector prevVector, ArrayList<vector>  vectorHistory, ArrayList<vector> vectorList, String path) {

    vectorHistory.add(prevVector);

    //add the current node to the path
    path = path + prevVector.child;
    System.out.println("Previous vector: "+ prevVector.parent+prevVector.child);

    // search if there is a next node.  looped to search all possible paths
    while (vectorList.contains(prevVector)) {
        System.out.println("vector history size: "+ vectorHistory.size());

        //retrieve the next vector
        vector nextVector = vectorList.get(vectorList.indexOf(prevVector));
        System.out.println("Next vector: " + nextVector.parent + nextVector.child);

        //remove current node so while loop can move to another possible path
        vectorList.remove(vectorList.indexOf(prevVector));

        //check if the next node has already been visited before
        if (vectorHistory.contains(nextVector)) {
            path=path+nextVector.child;
            System.out.println("Looped - " + path);


        } else {
            pathFinder(nextVector, vectorHistory, vectorList, path);
        }
    }

    System.out.println(path);

}

/*object vector */  
public static class vector {
    String parent, child;

    public vector(String parent, String child) {
        this.parent = parent;
        this.child = child;

    }

    @Override
    public boolean equals(Object o) {

        vector x = (vector) o;
        if (x.parent.equalsIgnoreCase(child)) {
            return true;
        } else {
            return false;
        }
    }

}

Answer 1

Java is "pass by value" so it passes a copy of the reference of the actual object. But it is a bit strange to understand when using a collection because the copy of the reference that is sent points to the same memory as the original one!

So if you pass a list to a method and you modify the method in the list it modifies the original list.

For example:

method b(List aList){
  aList.add(new Object());
}

method c(List aList){
  aList=new ArrayList ();
  aList.add(new Object());
}


List a=new ArrayList();
b(a); -> it will add an object to a;
c(a); -> it will not add an object to a or modify it in any way

So in your case when you call pathFinder(nextVector, vectorHistory, vectorList, path); you don't get that "stack" behaviour you expect with recursion because the successor calls of path finder modify the lists for the previous ones.

You can modify your call like that:

pathFinder(nextVector, new ArrayList<>(vectorHistory), new ArrayList<>(vectorList), path);

to avoid that problem but it will lose some additional memory copying the whole list every time ;) and it still won't get the results you want because I guess you have another error in the algorithm.

Your program seems very strange ;) The magic you are doing with vector's equal is not great because you cannot actually compare two equal objects. For example with your code AB is different than AB (which is not the case). So for places you have been you don't need vectors but points. So here is a bit modified program just to illustrate what I mean. It is still far from perfect:

import java.util.ArrayList;
import java.util.List;

public class MainClass {
    public static void main(String[] args) {

        List<MyVector> vectorList = new ArrayList<MyVector>();
        vectorList.add(new MyVector("A", "B"));
        vectorList.add(new MyVector("B", "C"));
        vectorList.add(new MyVector("C", "D"));
        vectorList.add(new MyVector("D", "A"));
        vectorList.add(new MyVector("A", "C"));

        List<String> pointsHistory=new ArrayList<String>();
        //to record points that have been visited
        //record the path 
        String path = "";
        //method call
        pathFinder(new MyVector(null, "A"), pointsHistory, vectorList, path);
    }

    //Recursive method. moves one node forward until there is no more nodes OR the next node is the same as a previously taken node

    public static void pathFinder(MyVector prevVector, List<String>  pointsHistory, List<MyVector> vectorList, String path) {
        pointsHistory.add(prevVector.child);
        //add the current node to the path
        path = path + prevVector.child;
        // search if there is a next node.  looped to search all possible paths -> no need to do magic with equals
        for(MyVector vector:vectorList)
            if(vector.parent.equals(prevVector.child)) {
                  System.out.println("Next vector: " + vector.parent + vector.child);
                  if (pointsHistory.contains(vector.child)) {
                    System.out.println("Result " + path);  //You get the end result here -> if we have reached a loop
                } else {
                    pointsHistory.add(vector.child);
                     pathFinder(vector, new ArrayList<>(pointsHistory), vectorList, path);
                }
            }          
    }

    /*object vector */  
    public static class MyVector {
        String parent, child;

        public MyVector(String parent, String child) {
            this.parent = parent;
            this.child = child;
        }
    }
}

You will get the results you want like that. See how I copy the visited points here: pathFinder(vector, new ArrayList<>(pointsHistory), vectorList, path); in order for that the work. And please name your classes with a Capital letter.