CS61B, 2022

Lecture 4: References and Recursion

• Primitive Types
• Reference Types
• Linked Data Structures

datastructur.es

Starting today, we’ll have questions in lecture you can answer. Try it out at: www.yellkey.com/question

​

Each question will have its own special word. By total coincidence, this first one happened to be “question”.

Primitive Types

Quiz: www.yellkey.com/business and www.yellkey.com/dream

Will the change to b affect a?

A. Yes

B. No

Answer: Visualizer

Will the change to x affect y?

• A. Yes
• B. No

Walrus a = new Walrus(1000, 8.3);

Walrus b;

b = a;

b.weight = 5;

System.out.println(a);

System.out.println(b);

int x = 5;

int y;

y = x;

x = 2;

System.out.println("x is: " + x);

System.out.println("y is: " + y);

​

weight: 5, tusk size: 8.30

weight: 5, tusk size: 8.30

x is: 2

y is: 5

Bits

Your computer stores information in “memory”.

• Information is stored in memory as a sequence of ones and zeros.
• Example: 72 stored as 01001000
• Example: 205.75 stored as … 01000011 01001101 11000000 00000000
• Example: The letter H stored as 01001000 (same as the number 72)
• Example: True stored as 00000001

​

Each Java type has a different way to interpret the bits:

• 8 primitive types in Java: byte, short, int, long, float, double, boolean, char
• We won’t discuss the precise representations in much detail in 61B.
• Covered in much more detail in 61C.

Note: Precise representations may vary from machine to machine.

Declaring a Variable (Simplified)

When you declare a variable of a certain type in Java:

• Your computer sets aside exactly enough bits to hold a thing of that type.
• Example: Declaring an int sets aside a “box” of 32 bits.
• Example: Declaring a double sets aside a box of 64 bits.
• Java creates an internal table that maps each variable name to a location.
• Java does NOT write anything into the reserved boxes.
• For safety, Java will not let access a variable that is uninitialized.

int x;

double y;

x = -1431195969;

y = 567213.112;

​

Declaring a Variable (Simplified)

When you declare a variable of a certain type in Java:

• Your computer sets aside exactly enough bits to hold a thing of that type.
• Example: Declaring an int sets aside a “box” of 32 bits.
• Example: Declaring a double sets aside a box of 64 bits.
• Java creates an internal table that maps each variable name to a location.
• Java does NOT write anything into the reserved boxes.
• For safety, Java will not let access a variable that is uninitialized.

int x;

double y;

x = -1431195969;

y = 567213.112;

​

Declaring a Variable (Simplified)

When you declare a variable of a certain type in Java:

• Your computer sets aside exactly enough bits to hold a thing of that type.
• Example: Declaring an int sets aside a “box” of 32 bits.
• Example: Declaring a double sets aside a box of 64 bits.
• Java creates an internal table that maps each variable name to a location.
• Java does NOT write anything into the reserved boxes.
• For safety, Java will not let access a variable that is uninitialized.

int x;

double y;

x = -1431195969;

y = 567213.112;

​

Declaring a Variable (Simplified)

When you declare a variable of a certain type in Java:

• Your computer sets aside exactly enough bits to hold a thing of that type.
• Example: Declaring an int sets aside a “box” of 32 bits.
• Example: Declaring a double sets aside a box of 64 bits.
• Java creates an internal table that maps each variable name to a location.
• Java does NOT write anything into the reserved boxes.
• For safety, Java will not let access a variable that is uninitialized.

int x;

double y;

x = -1431195969;

y = 567213.112;

​

Simplified Box Notation

We’ll use simplified box notation from here on out:

• Instead of writing memory box contents in binary, we’ll write them in human readable symbols.

​

int x;

double y;

x = -1431195969;

y = 567213.112;

​

The Golden Rule of Equals (GRoE)

Given variables y and x:

• y = x copies all the bits from x into y.

�Example from earlier: Link

Reference Types

Reference Types

There are 8 primitive types in Java:

• byte, short, int, long, float, double, boolean, char

​

Everything else, including arrays, is a reference type.

​

Class Instantiations

When we instantiate an Object (e.g. Dog, Walrus, Planet):

• Java first allocates a box of bits for each instance variable of the class and fills them with a default value (e.g. 0, null).
• The constructor then usually fills every such box with some other value.

public static class Walrus {

public int weight;

public double tuskSize;

public Walrus(int w, double ts) {

weight = w;

tuskSize = ts;

}

}

Demo Link

Class Instantiations

When we instantiate an Object (e.g. Dog, Walrus, Planet):

• Java first allocates a box of bits for each instance variable of the class and fills them with a default value (e.g. 0, null).
• The constructor then usually fills every such box with some other value.

....00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111101000010000000010000010011001100110011001100110011001100110011001101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000....

Green is weight, blue is tuskSize.

(In reality, total Walrus size is slightly larger than 96 bits.)

Class Instantiations

Can think of new as returning the address of the newly created object.

• Addresses in Java are 64 bits.
• Example (rough picture): If object is created in memory location 2384723423, then new returns 2384723423.

new Walrus(1000, 8.3);

​

2384723423

....00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111101000010000000010000010011001100110011001100110011001100110011001101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000....

2384723423^th bit

Reference Type Variable Declarations

When we declare a variable of any reference type (Walrus, Dog, Planet):

• Java allocates exactly a box of size 64 bits, no matter what type of object.
• These bits can be either set to:
• Null (all zeros).
• The 64 bit “address” of a specific instance of that class (returned by new).

Reference Type Variable Declarations

The 64 bit addresses are meaningless to us as humans, so we’ll represent:

• All zero addresses with “null”.
• Non-zero addresses as arrows.

This is sometimes called “box and pointer” notation.

96 bits

64 bits

64 bits

Reference Types Obey the Golden Rule of Equals

Just as with primitive types, the equals sign copies the bits.

• In terms of our visual metaphor, we “copy” the arrow by making the arrow in the b box point at the same instance as a.

Walrus a;

a = new Walrus(1000, 8.3);

Walrus b;

b = a;

a is 64 bits

Reference Types Obey the Golden Rule of Equals

Just as with primitive types, the equals sign copies the bits.

• In terms of our visual metaphor, we “copy” the arrow by making the arrow in the b box point at the same instance as a.

Walrus a;

a = new Walrus(1000, 8.3);

Walrus b;

b = a;

a is 64 bits

The Walrus shown is 96 bits.

Reference Types Obey the Golden Rule of Equals

Just as with primitive types, the equals sign copies the bits.

• In terms of our visual metaphor, we “copy” the arrow by making the arrow in the b box point at the same instance as a.

Walrus a;

a = new Walrus(1000, 8.3);

Walrus b;

b = a;

Note: b is currently undefined, not null!

a and b are 64 bits

The Walrus shown is 96 bits.

Reference Types Obey the Golden Rule of Equals

Just as with primitive types, the equals sign copies the bits.

• In terms of our visual metaphor, we “copy” the arrow by making the arrow in the b box point at the same instance as a.

Walrus a;

a = new Walrus(1000, 8.3);

Walrus b;

b = a;

a and b are 64 bits

The Walrus shown is 96 bits.

Parameter Passing

The Golden Rule of Equals (and Parameter Passing)

Given variables b and a:

• b = a copies all the bits from a into b.

​

Passing parameters obeys the same rule: Simply copy the bits to the new scope.

public static double average(double a, double b) {

return (a + b) / 2;

}

public static void main(String[] args) {

double x = 5.5;

double y = 10.5;

double avg = average(x, y);

}

​

The Golden Rule of Equals (and Parameter Passing)

Given variables b and a:

• b = a copies all the bits from a into b.

​

Passing parameters obeys the same rule: Simply copy the bits to the new scope.

​

public static double average(double a, double b) {

return (a + b) / 2;

}

public static void main(String[] args) {

double x = 5.5;

double y = 10.5;

double avg = average(x, y);

}

​

The Golden Rule of Equals (and Parameter Passing)

Given variables b and a:

• b = a copies all the bits from a into b.

​

Passing parameters obeys the same rule: Simply copy the bits to the new scope.

​

public static double average(double a, double b) {

return (a + b) / 2;

}

public static void main(String[] args) {

double x = 5.5;

double y = 10.5;

double avg = average(x, y);

}

​

The Golden Rule of Equals (and Parameter Passing)

Given variables b and a:

• b = a copies all the bits from a into b.

​

Passing parameters obeys the same rule: Simply copy the bits to the new scope.

​

public static double average(double a, double b) {

return (a + b) / 2;

}

public static void main(String[] args) {

double x = 5.5;

double y = 10.5;

double avg = average(x, y);

}

​

The Golden Rule of Equals (and Parameter Passing)

Given variables b and a:

• b = a copies all the bits from a into b.

​

Passing parameters obeys the same rule: Simply copy the bits to the new scope.

​

public static double average(double a, double b) {

return (a + b) / 2;

}

public static void main(String[] args) {

double x = 5.5;

double y = 10.5;

double avg = average(x, y);

}

​

The Golden Rule: Summary

There are 9 types of variables in Java:

• 8 primitive types (byte, short, int, long, float, double, boolean, char).
• The 9th type is references to Objects (an arrow). References may be null.

​

In box-and-pointer notation, each variable is drawn as a labeled box and values are shown in the box.

• Addresses are represented by arrows to object instances.

​

The golden rule:

• b = a copies the bits from a into b.
• Passing parameters copies the bits.

​

Test Your Understanding: yellkey.com/evening

Does the call to doStuff(walrus, x) have an affect on walrus and/or main’s x?

1. Neither will change.
2. walrus will lose 100 lbs, but main’s x will not change.
3. walrus will not change, but main’s x will decrease by 5.
4. Both will decrease.

public static void main(String[] args) {

Walrus walrus = new Walrus(3500, 10.5);

int x = 9;

doStuff(walrus, x);

System.out.println(walrus);

System.out.println(x);

}

public static void doStuff(Walrus W, int x) {

W.weight = W.weight - 100;

x = x - 5;

}

Answer: http://goo.gl/ngsxkq

​

Try to convince neighbor of your answer: yellkey.com/make

Does the call to doStuff(walrus, x) have an affect on walrus and/or main’s x?

• Neither will change.
• walrus will lose 100 lbs, but main’s x will not change.
• walrus will not change, but main’s x will decrease by 5.
• Both will decrease.

Answer: http://goo.gl/ngsxkq

​

public static void main(String[] args) {

Walrus walrus = new Walrus(3500, 10.5);

int x = 9;

doStuff(walrus, x);

System.out.println(walrus);

System.out.println(x);

}

public static void doStuff(Walrus W, int x) {

W.weight = W.weight - 100;

x = x - 5;

}

Instantiation of Arrays

Declaration and Instantiation of Arrays

Arrays are also Objects. As we’ve seen, objects are (usually) instantiated using the new keyword.

• Planet p = new Planet(0, 0, 0, 0, 0, “blah.png”);
• int[] x = new int[]{0, 1, 2, 95, 4};

​

int[] a;

• Declaration creates a 64 bit box intended only for storing a reference to an int array. No object is instantiated.

​

new int[]{0, 1, 2, 95, 4};

• Instantiates a new Object, in this case an int array.
• Object is anonymous!

Declaration

Minor technical note: I’m abusing the term instantiate a little by applying it to arrays.

Assignment of Arrays

int[] a = new int[]{0, 1, 2, 95, 4};

• Creates a 64 bit box for storing an int array address. (declaration)
• Creates a new Object, in this case an int array. (instantiation)
• Puts the address of this new Object into the 64 bit box named a. (assignment)

​

Note: Instantiated objects can be lost!

• If we were to reassign a to something else, we’d never be able to get the original Object back!

​

Declaration, instantiation, and assignment.

Declaration

Instantiation

Assignment

IntList and Linked Data Structures

IntList

Let’s define an IntList as an object containing two member variables:

• int first;
• IntList rest;

​

​

And define two versions of the same method:

• size()
• iterativeSize()

​

Code not shown in slides. See lectureCode-fa22 repo or videos 7, 8, and 9 from https://www.youtube.com/watch?v=TzuAiXTZmYo&list=PL8FaHk7qbOD7lprwG_xdIMLrwibZDi-Ll&index=7.

Challenge

Write a method int get(int i) that returns the ith item in the list.

• For simplicity, OK to assume the item exists.
• Front item is the 0th item.

​

Ways to work:

• Paper (best)
• Laptop (see lectureCode repo)
• exercises/lists1/IntList.java
• In your head (worst)

public class IntList {

public int first;

public IntList rest;

public IntList(int f, IntList r) {

first = f;

rest = r;

}

/** Return the size of this IntList. */

public int size() {

if (rest == null) {

return 1;

}

return 1 + this.rest.size();

...

L.get(0): 5

L.get(1): 10

See the video online for a solution: https://www.youtube.com/watch?v=qnmxD_21DNk

​

Question: yellkey.com/nor

What is your comfort level with recursive data structure code?

1. Very comfortable.
2. Comfortable.
3. Somewhat comfortable.
4. I have never done this.

ExtraIntListPractice.java

For further practice with IntLists, fill out the code for the methods listed below in the lists1/exercises/ExtraIntListPractice.java in lectureCode github directory.

• public static IntList incrList(IntList L, int x)
• Returns an IntList identical to L, but with all values incremented by x.
• Values in L cannot change!

​

​

• public static IntList dincrList(IntList L, int x)
• Returns an IntList identical to L, but with all values incremented by x.
• Not allowed to use ‘new’ (to save memory).3

L

Q

Q

L

This week’s discussion also features optional IntList problems.

Old Deprecated Slides

Quick Aside on Class Instantiation

Any class that we’ve created so far in 61B can be instantiated.

• Would be silly (but possible) to instantiate HelloWorld.

(nothing happens) -- HelloWorld.main does not run!!

null

Java (for better or worse) allows null references.

• Danger lurks: null references do NOT have instance variables.
• Blame Sir Tony Hoare (more when we talk about Quicksort)

​

​

Example:

Java is “Pass by Value”

All method (and constructor) calls are pass by value!

• The exact contents of the container in the outside world are delivered to the containers in the function. If the container has an arrow, so be it.

Note

is in python equivalent to == in Java

• These check memory addresses.

​

== in python equivalent to .equals in Java

• In python we write a __eq__ function.
• In Java we write a equals() function (see lecture 12).
• These check the boolean return value of a special function written by a class author.

​

Question: If a class doesn’t define equals, and you call equals, what happens?

• It defaults to the implementation of equals in the “object” class (more on this later), but it uses ==!