How is a Java ArrayList modified when passed as parameter to function that returns void and modified in function? May be confused on pass-by-value

Question

I have a block of Java code that modifies an ArrayList by passing the ArrayList into a method, modifying the list in the method, and returns void. I thought that Java's pass-by-value would cause the original ArrayList to not be modified. What am I misunderstanding?

public class Question {

    public static void weaveLists(LinkedList<Integer> first, LinkedList<Integer> second, ArrayList<LinkedList<Integer>> results, LinkedList<Integer> prefix) {
        /* One list is empty. Add the remainder to [a cloned] prefix and
         * store result. */
        if (first.size() == 0 || second.size() == 0) {
            LinkedList<Integer> result = (LinkedList<Integer>) prefix.clone();
            result.addAll(first);
            result.addAll(second);
            results.add(result);
            return;
        }

        /* Recurse with head of first added to the prefix. Removing the
         * head will damage first, so we’ll need to put it back where we
         * found it afterwards. */
        int headFirst = first.removeFirst();
        prefix.addLast(headFirst);
        weaveLists(first, second, results, prefix);
        prefix.removeLast();
        first.addFirst(headFirst);

        /* Do the same thing with second, damaging and then restoring
         * the list.*/
        int headSecond = second.removeFirst();
        prefix.addLast(headSecond);
        weaveLists(first, second, results, prefix);
        prefix.removeLast();    
        second.addFirst(headSecond);
    }

    public static ArrayList<LinkedList<Integer>> allSequences(TreeNode node) {
        ArrayList<LinkedList<Integer>> result = new ArrayList<LinkedList<Integer>>();

        if (node == null) {
            result.add(new LinkedList<Integer>());
            return result;
        } 

        LinkedList<Integer> prefix = new LinkedList<Integer>();
        prefix.add(node.data);

        /* Recurse on left and right subtrees. */
        ArrayList<LinkedList<Integer>> leftSeq = allSequences(node.left);
        ArrayList<LinkedList<Integer>> rightSeq = allSequences(node.right);

        /* Weave together each list from the left and right sides. */
        for (LinkedList<Integer> left : leftSeq) {
            for (LinkedList<Integer> right : rightSeq) {
//This is the part I don't understand
                ArrayList<LinkedList<Integer>> weaved = new ArrayList<LinkedList<Integer>>();
                weaveLists(left, right, weaved, prefix);
                result.addAll(weaved);
            }
        }
        return result;
    }

}

I would expect that the weaved array would not be modified when the result.addAll(weaved) is called, but weaved array is modified after the call to weaveLists(), even though it returns void.

Answer 1

You create a weaved reference to an ArrayList object that stored in memory. When you call new operator then a new object allocated in the memory. Then you pass the reference weaved to the weaveLists() method. This method have a reference result, but this is only a reference that refer to the same object in the memory, because only new operator allocate a new memory. So, the weaveLists() method modify your original ArrayList. It is a major feature that you should understand, I suggest you to read the difference between pass-by-value and pass-by-reference.

Answer 2

To answer the question in short - you are misunderstanding what does the pass-by-value mean in Java.

If you pass an object (list in this case) and manipulate it's elements without changing it's reference, it is the same object you passed, nothing changed on the object (list) itself, it has the same reference it had when passed to function, but changes do apply to any of the elements being manipulated.

Pass by value in this context only means that if you created a new instance of a given list within the function and then manipulated it - no changes would apply on original list, since that would be observed as a local variable, not the passed one.

Check top answers to this question, or just read some java basics related to pass-by-value. Use this blog, or any other that you might like more.