Passing by reference vs Passing by value

Question

I'm currently studying Cracking the Coding interview, and I believe my basic understanding of pointers are being called into question. I am currently looking at a solution to make a linked list for every level of a binary tree. The solution is as follows:

void createLevelLinkedList(TreeNode root, ArrayList<LinkedList<TreeNode» lists, int level) {
    if (root == null) return; // base case
    LinkedList<TreeNode> list = null;
    if (lists.size() == level) { // Level not contained in list
        list = new LinkedList<TreeNode>();
        /* Levels are always traversed in order. So., if this is the
         * first time we've visited level i, we must have seen levels
         * 0 through i - 1. We can therefore safely add the level at
         * the end. */
        lists.add(list);
    } else {
        list = lists.get(level);
    }
    list.add(root);
    createLevelLinkedList(root.left, lists, level + 1);
    createLevelLinkedList(root.right, lists, level + 1);
}

ArrayList<LinkedList<TreeNode» createLevelLinkedList(TreeNode root) {
    ArrayList<LinkedList<TreeNode» lists = new ArrayList<LinkedList<TreeNode»();
    createLevelLinkedList(root, lists, 0);
    return lists;
}

This solution greatly confuses me, because in the createLeveLinkedList function with only the root parameter (the driver function), a new list of linked lists is created. From a java perspective, if it is passed by value, after createLevelLinkedLists(root, lists, 0) is called, to my understanding, lists should not have changed.

If it was C++, I could understand it if they passed the pointer of the lists object into the function.

Could someone please clarify this?

Apologies for the formatting, I'm still not sure how it works on stackoverflow.

Thanks

Possible duplicate of [Is Java "pass-by-reference" or "pass-by-value"?](http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value) — , Nov 04 '15 at 22:58
I actually read that post, and I still require clarification, as from what I understand, it states that lists should not have changed. I am assuming that the solution is written in Java. — Arthur Lee, Nov 04 '15 at 23:01
@ArthurLee In the C++ sense, Java only has pointers. If you have a `MyClass m = new MyClass();`, a `m = somethingElse;` won't change the value of the existing old object, but any passing around passes only a reference/pointer to the same old object instead of copying it. — deviantfan, Nov 04 '15 at 23:04
Does this even compile? `lists` is defined as a parameter, and then it's also defined as a variable (four lines from the bottom). — Andrew Shepherd, Nov 04 '15 at 23:04
in java and C# 'ArrayList>` is passed by reference (actually, in a way, by value since all class instances are references) in C++ it would depend on how the copy ctor is coded as it is passed by-value (no `*` or `&`) but it could cause changes to the original object if the copy ctor were written in the "right" wrong way. — GreatAndPowerfulOz, Nov 04 '15 at 23:05
@AndrewShepherd, that line is in a different function overload altogether. — GreatAndPowerfulOz, Nov 04 '15 at 23:06
lists is a reference to a complex data structure. While the reference itself is passed by value, it's a shallow copy of the reference, so whatever it references can still be modified (assuming it's modifiable, Strings aren't for example). — blm, Nov 04 '15 at 23:06
Java passes references by value. The "references" that are values in Java are unrelated to the "references" of "pass by reference". (It's an unfortunate naming collision.) C++ introduces yet another meaning for "reference". — molbdnilo, Nov 04 '15 at 23:12
So if I understand properly, in Java/C#, passing an object (not a primitive) as a parameter into a function is passing the value of the reference, not the value itself? On a side note then, why would int[] reference = { 1, 2, 3, 4, 5 }; int[] newReference = reference; reference[0] = 0; for (int i = 0; i < newReference.Length; i++) { Console.WriteLine(newReference[i]); } print out 0, 2, 3, 4, 5, whereas Node node = current; current = current.next; node would still point to what current originally was? — Arthur Lee, Nov 04 '15 at 23:20
`passing an object (not a primitive) as a parameter into a function is passing the value of the reference, not the value itself?` Yes. Assigning a completely new object to the variable name inside the function won't do anything outside, but changing the passed object does. — deviantfan, Nov 05 '15 at 20:41
`reference` and `newReference` are two distinct references to the same thing. `reference[0]` and `newReference[0]` *are* the same thing. (An array can be thought of as a single object. You're changing the content of a object here.).`Node node = current;` Now node and current are two references to the same thing. Then you change where current should reference to. It doesn't matter for node. — deviantfan, Nov 05 '15 at 20:45

score 0 · Answer 1 · edited May 23 '17 at 12:15

0

Java is always pass by value. However the value passed for complex datatypes is that of the reference, so the lists reference passed into createLevelLinkedList(...) refers to the same object as the original lists reference.

As long as you don't change the value of the reference in the createLevelLinkedList(...) method you will change the original object.

As Paul mentioned, it's all written down here:

https://stackoverflow.com/a/40523/1619628

edited May 23 '17 at 12:15

Community

1
1

answered Nov 04 '15 at 23:27

Hendrik Simon

231
2
10

I think that makes sense. So if I had a function for Binary Search Tree deletion, like so: public Node BSTDelete(Node root, int value) { delete(root, int value); return root; } Root would reflect the root of the BST after a node was deleted from it? – Arthur Lee Nov 05 '15 at 00:13
I'm not sure what you're doing in delete, but as long as you don't change the value of the reference all changes will happen on the same object. – Hendrik Simon Nov 05 '15 at 00:19
And if delete is recursive and root gets set to root.left/root.right, then the changes are ignored? – Arthur Lee Nov 05 '15 at 00:38
Recursion does not change the way java passes parameters. It's still passing the reference by value. – Hendrik Simon Nov 05 '15 at 00:44
If inside delete, during the traversal down to the node being deleted, root = root.left or root = root.right happens, and then it calls delete() again, would root in BSTDelete still point to the original root, or would it point to whatever root ended up being after being set to .left or .right a bunch of times? – Arthur Lee Nov 05 '15 at 01:27
This is purely a theoretical question, for if I were implementing delete, I would set root.left = delete(root.left, value) etc instead of making root = root.left. – Arthur Lee Nov 05 '15 at 01:33

Passing by reference vs Passing by value

1 Answers1