Overview

In these notes, we will be covering pointers, arrays, and the relationship between the two. To fully understand the topics of these notes, we will discuss Java primitives versus reference types and build up from here the notion of arrays and linked lists. Once we have these concepts down, we will discuss how to work with these data structures.

Java Primitives versus Reference Types

Java, like Python, has types. Everything we work with is of some type; however, unlike Python, the typing system in Java is static and is not hidden from us programmers. We must therefore become familiar with these types. In general there are two "umbrella" types, and you might have guessed that they are primitive types and reference types. Let’s dive right in.

Primitive Types

Java primitives are the most basic types in that they are built into the language. These types include:

boolean: Truthy and falsey values.
char: 16-bit Unicode characters.
byte: Java’s 8-bit integers.
short: Java’s 16-bit integers.
int: Java’s 32-bit integers. Note that this is different from Integer objects!
long: Java’s 64-bit integers.
float: Java’s 32-bit floating point number. A floating point number is based on a format that is meant to represent some range of decimal numbers. More on this in 61C!
double: Java’s 64-bit floating point number.

These are the basic building blocks that we work with regularly.

Reference Types

Now, we have reference types which are essential for working with and understanding Java’s Object Oriented Programming designs. We introduce the idea of reference types by discussing how they work in the context of the "String" object. Consider the following block of code:

            String a = new String("");
            String b = a;

What is going on under the hood? First, we have a, but what is it? It is a reference to the String object. We have to ask now, what does it mean for a variable to be a reference to an object? Well without going into the nitty gritty details of memory, we wil say that a contains the address in memory for which the String object is stored. In terms of an environment diagram, this would look something like: \[Insert environment diagram graphic here\] So what happens when execute the second line? We want and expect that b will have the same value as a, and what is the value of a? It is the address of a location in memory storing a String object! Therefore, we copy that address into b in our environment diagram as follows: \[Insert environment diagram graphic here\] Now, this is a really clunky and not very useful diagram. Why? Because who wants to be copying memory addresses from variable to variable? This is work that is best left for the last class in the 61 series. So what we do instead is represent these memory addresses using pointers. In effect, instead of using an address in memory, we draw an arrow to the object a variable references. So after the first line of code above, our environment diagram will be: \[Insert environment diagram graphic here\] After the second step, we again copy the value of a into b. What is the value of a? It is the pointer because a pointer is simply just an address in memory. Therefore, we copy the pointer into b. This looks like: \[Insert environment diagram graphic here\] To summarize:

When we declare a variable to be of some object, we are really saying it is a reference to an object of some type in memory.
The value of a reference type is the address in memory of the object it was assigned.
We represent these addresses with pointers in diagrams
When assigning a variable to another variable of the same type, we copy of the pointer over.

Case Study: IntLists

This course is on data structures. It seems appropriate to make our own data structure!

        public class IntList {
            public int _val;
            public IntList _next;

            public IntList(int val, IntList next) {
                int _val = val;
                IntList _next = next;
            }

            public static void main(String[] args) {
                IntList a = new IntList(1, new IntList(2, null));
            }
        }

Based on the above class declaration, we know the following about any IntList object L:

L has a _val field attribute that is an int.
L has a _next field attribute that is a reference to another IntList object

After executing the main method of the IntList class, we have the following environment diagram: \[Insert environment diagram graph here\] This is a very bare bones IntList class, but it can still store multiple items. It does so by using the knowledge of pointers to chain together multiple instances of the IntList class!