CODEWITHSUNDEEP
javadata-structureslinked-list
JavaDeveloper
JavaDeveloper

Reputation: 5660

Where to set references to null, if references are passed by value in java?

The following code constructs 2 linkedlists and passes both of them to construct a 3rd merged linkedlist. However once merged, the l1 and l2 ( initially constructed ) linkedlist have changed. Where in this peice of code should l1 and l2 be set to null ?

EDIT: The reason for setting it to null is we dont want client to use a modified l1 or l2 in future. We want to have a clear contract that once merged, we have a fresh new reference and previous references were made null and void so that someone does not use them believing they were linkedlists at time time of their construction.

public class MergeLinkedList {
    Node first;
    Node last;

    public void add (int val) {
        final Node l = last;
        final Node newNode = new Node(val, null);
        last = newNode;
        if (first == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
    }

    public void displayList() {
        Node tempFirst = first;
        while (tempFirst != null) {
            System.out.print(tempFirst.item + " ");
            tempFirst = tempFirst.next;
        }
    }

    private static class Node {
        int item;
        Node next;

        Node(int element, Node next) {
            this.item = element;
            this.next = next;
        }
    }

    private Node mergeLinkedListRecursive(Node list1, Node list2) {
        if (list1 == null) {
           return list2; 
        }

        if (list2 == null) {
            return list1;
        }

        if (list1.item < list2.item) {
            list1.next = mergeLinkedListRecursive(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeLinkedListRecursive(list1, list2.next);
            return list2;
        }
    }

    public void mergeLinkedListRecursion(MergeLinkedList list1, MergeLinkedList list2) {
        first = mergeLinkedListRecursive(list1.first, list2.first);
    }



    public static void main(String[] args) {

        int[] a1 = {1, 3, 5};
        int[] a2 = {2, 4};

        MergeLinkedList l1 = new MergeLinkedList();
        for (int val : a1 ) {
            l1.add(val); 
        }

        MergeLinkedList l2 = new MergeLinkedList();
        for (int val : a2) {
            l2.add(val);
        }

        MergeLinkedList l3 = new MergeLinkedList();
        l3.mergeLinkedListRecursion(l1, l2);
        l3.displayList();
    }
}

Upvotes: 1

Views: 133

Answers (3)

user2246674
user2246674

Reputation: 7719

The onus of correct usage of the objects named by l1 and l2 is on the caller.

That is, while the caller might assume that l1 and l2 always evaluate to the same sequence of items, after l3.mergeLinkedListRecursion(l1, l2); this is not the case. This is because the method performs side effects and mutates the objects.

After the method invocation it is up to the caller to ensure correct usage of l1 and l2. The "correct" usage would likely be to not use them at all. (The l1 and l2 variables still evaluate to heads of two lists, one being a sub-list; just not what might be expected.)

Even if it were possible to assign the arguments (l1 and l2) to null - i.e. with call-by-reference semantics - it would be impossible to ensure that all variables/fields evaluating to said (now mutated) objects were assigned null.

A variable/field is a name for a particular object: how is it possible to track down all the names for a given object, say Soda - or is it Pop? Cola? Coke? 코카인?

One way to prevent this issue is to use immutable lists; in this case the merged list would actually contain all new nodes and not intertwining existing nodes - that is, with an immutable list, next can only be set in the constructor. Some languages like Haskell and Scala follow this approach.

Another approach (which I hesitate to suggest) would be to make a "container container"; for a linked list it could simply be a "dummy head node" whose next would be assigned to null when an operation was performed on the list that "made it invalid". However, I find this a hackish and uneeded solution that is hard to implement correctly and dirties up an otherwise a simple mutable linked-list implementation.

The fundamental problem is mutations and side-effects and is just one of the ugly aspects of writing non-pure code - a little bit of documentation (and reading of such) can go a long way. Also, Unit Tests: testing can catch problems that might arise from incorrect assumptions.

Upvotes: 2

Oak
Oak

Reputation: 26878

If a Node object becomes invalid after being used as an argument to mergeLinkedListRecursive(), then this is something a node should remember:

class Node {
    ...
    boolean valid = true;
    void markInvalid() { valid = false; }
}

And then in mergeLinkedListRecursive() mark them as such:

list1.markInvalid();
list2.markInvalid();

And of course, make Node's methods first verify that it is in a valid state.

Upvotes: 0

TofuBeer
TofuBeer

Reputation: 61536

I have no idea why you would want to set l1 and l2 to null, but to do it you would need to put it after this line:

l3.mergeLinkedListRecursion(l1, l2);

Why exactly do you want them to be set to null?

Upvotes: 0

Related Questions