Aliasing in Java with Arrays and Reference Types

Question

There are many similar question on SO about this, but I haven't been able to find an answer that clearly lists the differences in aliasing, so I am asking here.

I know that a simple primitive assignment statement copies values:

int x = 1;
int y = x;
x = 2;
StdOut.print(x); // prints 2
StdOut.print(y); // prints 1

Then I was told that arrays are 'aliased' during assignment statements. So:

int[] x = {1, 2, 3, 4, 5};
int[] y = x;
x[0] = 6;
StdOut.print(x[0]); // prints 6
StdOut.print(y[0]); // prints 6

However, if you assign one of the variables a completely different array, this aliasing 'disappears':

int[] x = {1, 2, 3, 4, 5};
int[] y = x;
x = new int[]{1, 2, 3, 4, 5};
x[0] = 6;
StdOut.print(x[0]); // prints 1
StdOut.print(y[0]); // prints 6

What is the reason for this?

Then, I come to reference types. When using assignment statements, it is the reference which is copied, not the value. So:

Counter c1 = new Counter("ones");
Counter c1.incrememnt(); // 0 -> 1
Counter c2 = c1;
c2.increment();
StdOut.print(c1); // prints 2
StdOut.print(c2); // prints 2

But what about if I then assign c1 to a new Counter object? What happens to c2; does it reference the original Counter or the new Counter, why?

I ask because I originally thought that reference types worked like arrays. If I create a new Counter and assign it to c1, then both c1 and c2 point to the newly created Counter. However, after going through some exercises, I created an iterable Stack ADT which seems to violate this assumption. My code is below:

import java.util.Iterator;

public class MyStack<Item> implements Iterable<Item> {

    private Node first; // top of stack
    private int N; // number of items

    private class Node {
        Item item;
        Node next;
    }

    public MyStack() {}

    public Iterator<Item> iterator() {
        return new ListIterator();
    }

    private class ListIterator implements Iterator<Item> {

        private Node current = first;

        public boolean hasNext() {
            return current != null;
        }

        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }

    }

    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }

    public Item pop() {
        if(!isEmpty()) {
            Node oldfirst = first;
            first = first.next;
            return oldfirst.item;
        } else throw new RuntimeException("Stack underflow");
    }

    public boolean isEmpty() { return size() == 0; }

    public int size() { return N; }

    public static void main(String[] args) {
        MyStack<Integer> stack = new MyStack<>();
        stack.push(5);
        stack.push(6);
        stack.push(7);
        stack.push(8);
        stack.push(9);
        for(int i : stack) {
            StdOut.println(i);
        }
    }

}

It's a simple implementation, using a linked list data structure for the items. The main instance variable is first, which holds the first node in the linked list (top of the stack). If you look in the nested ListIterator class, there's an instance variable current which is assigned to first. Now, in the push method, first is reassigned to a newly created Node. Surely then the current variable is still assigned to the old first Node? Why then does this implementation work?

My hunch is that either a) I don't understand how reference values are passed (please explain) or b) when you run through the for loop in the main method, it implicitly calls creates a new ListIterator which, at that point, assigns current to whatever the current value of first is. If this is the real reason, then does that mean that a new iterator should be created whenever a method is called within the class? For example, if I create the iterator explicitly, then push a few items to the stack, and then reuse the iterator without re-initialising - will it work as intended?

Please explain!

Answer 1

Other people have explained well about the principles. I'll apply the rules to explain the behavior of your stack object.

So when you push a node, the 'first' refers to the new, real first node. (Because you created a new Node object and assigned 'first' to that new Node.)

Therefore, the 'current' which refers to 'first', also now refers to the real new first node, not the 'old first node'. That is why it works.

Similarly, when pop method is executed, 'first' now refers to next node of 'oldfirst'. Therefore first now refers to the new first node, which is basically old second node. So it works.

I see why you were confused that 'current' would point to 'old first' regardless of push and pop operations. Assuming the stack is created only once, 'current = first' operation is executed only once. And there is no other assignment to 'current' happening anywhere else. So we can say current is just another name of 'first' as long as it doesn't get re-assigned to something else. All it does is basically aliasing. It doesn't retain original value of 'first'. It always points to whatever the most recently updated version of 'first' is.

Answer 2

What is the reason for this?

int[] x = {1, 2, 3, 4, 5};
int[] y = x;
x[0] = 6;
StdOut.print(x[0]); // prints 6
StdOut.print(y[0]); // prints 6

x and y are both references that point to one object (an array is an object), so changing the state through any of the references will make changes to the actual object, then both the references will reflect the change.

x[0] = 6; // then y[0] = 6, too.

However, if you assign one of the variables a completely different array, this aliasing 'disappears':

int[] x = {1, 2, 3, 4, 5};
int[] y = x;
x = new int[]{1, 2, 3, 4, 5};
x[0] = 6;
StdOut.print(x[0]); // prints 6
StdOut.print(y[0]); // prints 1

Because:

When you point x to another object

x = new int[]{1, 2, 3, 4, 5};

y will still point to the original object. Remember that x and y are just references which point to objects.

int[] x = {1, 2, 3, 4, 5};
int[] y = x;

So, when we set

x[0] = 6; 

y[0] wasn’t effected.

StdOut.print(x[0]); // prints 6
StdOut.print(y[0]); // prints 1

Answer 3

One of my concerns about the way introductory Java tends to be taught is that often aliasing hardly gets mentioned. It is key to understanding Java to realise what it means, and therefore in my view should be a MAJOR aspect of introductory Java courses. So often I find students who think they know Java getting completely stuck later on because they were never properly taught it.

It really isn't difficult, all you have to know is that if v1 and v2 are two variables of an object type, the assignment v2=v1 means "v2 stops referring to what it used to refer to and starts referring to what v1 refers to".

So, if you have another variables of an object type v3, and after doing v2=v1 you do v1=v3 it means "v1 stops referring to what it used to refer to, and starts referring to what v3 refers to". It doesn't mean v2 also stops referring to what v1 used to refer to. Your misunderstanding comes down to thinking it does.

Answer 4

What is the reason for this?

The variables x and y are not arrays. They are array references. An array is an object, and you reassigned x to refer to a different array than y, and only changed x, thus you have different values in the two different arrays.

What happens to c2; does it reference the original Counter or the new Counter, why?

In your example there was only one Counter object created, when you called new Counter, there's no original, and you made the Counter reference c2 refer to the same instance that c1 refers to, so they are pointing to the same thing.

Surely then the current variable is still assigned to the old first Node? Why then does this implementation work?

Your for each loop invokes iterator() which returns a new ListIterator which instantiates it's own current which points to the latest value of first in your stack.