CS61B, 2021
Lecture 4: References and Recursion
¡ñ Primitive Types
¡ñ Reference Types
¡ñ Linked Data Structures
datastructur.es
Primitive Types
Quiz
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);
Will the change to b affect a? A. Yes
B. No
Will the change to x affect y? ¡ñ A. Yes
¡ñ B. No
weight: 5, tusk size: 8.30
weight: 5, tusk size: 8.30
x is: 2 y is: 5
Answer: Visualizer
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 = xcopies 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.
new Walrus(1000, 8.3); Demo Link
32 bits 64 bits
public static class Walrus { public int weight; public double tuskSize;
public Walrus(int w, double ts) { weight = w;
tuskSize = ts;
}
}
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.
….00000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
0000000000000000
00000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000….
new Walrus(1000, 8.3);
32 bits 64 bits
Green is weight, blue is tuskSize.
(In reality, total Walrus size is slightly larger than 96 bits.)
00000000000000000000001111101
000010000000010000010011001100110011001100110
0110011001100110011010
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.
2384723423th bit
….00000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
0000000000000000
00000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000
000000000000000000000000….
2384723423
new Walrus(1000, 8.3);
00000000000000000000001111101
000010000000010000010011001100110011001100110
0110011001100110011010
32 bits 64 bits
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).
Walrus someWalrus;
someWalrus = null;
64 bits
Walrus someWalrus;
someWalrus = new Walrus(1000, 8.3);
64 bits
96 bits
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.
64 bits
64 bits
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 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;
The Walrus shown is 96 bits.
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;
The Walrus shown is 96 bits.
Note: b is currently undefined, not null!
a and b are 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;
The Walrus shown is 96 bits.
a and b are 64 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);
}
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.
This is also called pass by value.
Passing parameters obeys the same rule: Simply copy the bits to the new scope.
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/others
Does the call to doStuff(walrus, x) have an affect on walrus and/or main¡¯s x?
A. Neither will change.
B. walrus will lose 100 lbs, but main¡¯s x will not change.
C. walrus will not change, but main¡¯s x will decrease by 5.
D. 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;
}
Try to convince neighbor of your answer: yellkey.com/public Does the call to doStuff(walrus, x) have an affect on walrus and/or main¡¯s x?
A. Neither will change.
B. walrus will lose 100 lbs, but main¡¯s x will not change.
C. walrus will not change, but main¡¯s x will decrease by 5.
D. Both will decrease.
Answer: http://goo.gl/ngsxkq
public static void doStuff(Walrus W, int x) { W = new Walrus(W);
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};
Declaration
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};
Instantiation (HW0 covers this syntax)
¡ñ Instantiates a new Object, in this case an int array.
¡ñ Object is anonymous!
Minor technical note: I¡¯m abusing the term instantiate a little by applying it to arrays.
Assignment of Arrays
Declaration, instantiation, and assignment.
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!
Assignment
Instantiation
Declaration
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()
Challenge
See the video online for a solution:
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
Question: yellkey.com/iterate
What is your comfort level with recursive data structure code?
A. Very comfortable.
B. Comfortable.
C. Somewhat comfortable. D. 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!
L Q
¡ñ 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).
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 ==!