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

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.