University of Toronto
Department of Computer Science
csc 148: Introduction to Computer Science

Online Homework: References and Memory

The purpose of this tutorial is to help you understand how objects can be linked together using references (or pointers). This tutorial will help you relate the box-and-arrow diagrams of linked structures to the code that operates on them.

A Basic Example

The first example shows what happens when variables and references are declared, and what happens when we call new on an object. Trace through the execution of this code by clicking on the step button to see how memory is allocated for each kind of statement.

Question A:

Assume that Rec has been defined as follows:

       class Rec {
            String name;
            int studentNum;
            float GPA;
       }

How do these two Java statements compare?
(1) int i; (2) Rec r;

Question B:

The next two Java statements continue the code from the previous question. How do they compare?
(1) i = new int(); (2) r = new Rec();

Copying References

When we use assignment to copy references, as in the statement

     b = a;

below, it's important to think very carefully about what this means. Step through the code below to find out. If you'd like a challenge, try tracing it on paper yourself first.

Hint: When writing code with references, diagrams like these can really help you avoid bugs.

Aliasing

Question C:

What are the values of x and y after the following code has been executed?

        int x;
        int y;
        x = 22;
        y = x;
        y = 33;

The answer to the above question seems pretty obvious when we use integer variables, but we need to think more carefully when we do the same thing using two reference variables that refer to the same object.

Question D:

Now consider the following code:

       Node a;
       Node b;
       a = new Node();
       a.key = 44;
       b = a;
       b.key = 55;

What is the value of a.key and b.key after this code has been executed?

When two or more variables refer to the same object one is the alias of the other. In other words, we can refer to the same object using more than one name (reference).

Trace the following code to see what happens when we use aliases:

Pitfalls of Aliasing

It can be quite useful to be able to refer to an object using more than one name, and we'll see lots of examples of this during the course. Just remember that any change made to an object using one reference will be seen by all other references to that object.

One way to think about this is to use an analogy of offices with blackboards in them. Suppose I tell you to go erase the blackboard in Room 7b and write your name on it. Then suppose I tell someone else to do the same. If you go back to room 7b afterwards, you will see their name, not yours. The office is like the object, and the room number is like the reference value -- it tells people where the office is.

You can avoid unwanted surprises and can save yourself many hours of debugging by drawing careful diagrams as you write and later trace your code.

Other Pitfalls with References

Another common problem that people have when learning how to program with references is that they forget to keep at least one reference to an object that they want to refer to again.

In Java it is okay drop the last reference to an object that will not be used again. Java's garbage collector will eventually reclaim that lost memory. However, if we want to access that object again, we cannot.

Here is a challenge. For each of the following pieces of code, select the potential problem that appears in the code, or select Okay if the code has no problems.

Question E:

What potential problem does this code have?

        Node a;
        Node b;
        b = new Node();
        a = new Node();
        a = b;
        a.key = 15;

Question F:

What potential problem does this code have?

        Node a;
        Node b;
        b.key = 22;
        a = new Node();
        a.key = 15;

Review Questions

Question G:

Select the diagram that correctly represents the state of memory after the following code has been executed.

        Node b;
        Node a;
        b = new Node();
        b.key = 10;
        a = b;
        a.key = 15;

Question H:

What is the value of b.key after the following code has been executed?

     Node b;
     Node a;
     b = new Node();
     b.key = 75;
     a = b;
     a.key = 22;
     a = new Node();
     a.key = 88;

Question I:

Given the following code,

     Node a;
     Node b;
     a = new Node();
     b = new Node();
     b.key = 10;
     a.link = null;

what two additional statements will lead to the following diagram?