Primitive Types, Reference Types, and Linked Data Structures
1
Lecture 3
CS61B, Fall 2023 @ UC Berkeley
Slides credit: Josh Hug
Announcements
Goals: Building a List
Lecture 3, CS61B, Fall 2023
Goals: Building a List
Primitive Types
Reference Types
Parameter Passing
Instantiation of Arrays
IntList and Linked Data Structures
Lists
Today, we’ll begin our 3 lecture journey towards building our own list implementation.
import java.util.List;
import java.util.LinkedList;
List<String> L = new LinkedList<>();
L.add("a");
L.add("b");
Primitive Types
Lecture 3, CS61B, Fall 2023
Goals: Building a List
Primitive Types
Reference Types
Parameter Passing
Instantiation of Arrays
IntList and Linked Data Structures
Quiz: yellkey.com/material
int x = 5;
int y;
y = x;
x = 2;
System.out.println("x is: " + x);
System.out.println("y is: " + y);
Walrus a = new Walrus(1000, 8.3);
Walrus b;
b = a;
b.weight = 5;
System.out.println(a);
System.out.println(b);
Will the change to b affect a?
A. Yes
B. No
Answer: Visualizer
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
Bits
Your computer stores information in “memory”.
Each Java type has a different way to interpret the bits:
Note: Precise representations may vary from machine to machine.
Declaring a Variable (Simplified)
When you declare a variable of a certain type in Java:
int x;
double y;
x = -1431195969;
y = 567213.112;
Declaring a Variable (Simplified)
When you declare a variable of a certain type in Java:
int x;
double y;
x = -1431195969;
y = 567213.112;
Declaring a Variable (Simplified)
When you declare a variable of a certain type in Java:
int x;
double y;
x = -1431195969;
y = 567213.112;
Declaring a Variable (Simplified)
When you declare a variable of a certain type in Java:
int x;
double y;
x = -1431195969;
y = 567213.112;
Simplified Box Notation
We’ll use simplified box notation from here on out:
int x;
double y;
x = -1431195969;
y = 567213.112;
The Golden Rule of Equals (GRoE)
Reference Types
Lecture 3, CS61B, Fall 2023
Goals: Building a List
Primitive Types
Reference Types
Parameter Passing
Instantiation of Arrays
IntList and Linked Data Structures
Reference Types
There are 8 primitive types in Java:
Everything else, including arrays, is a reference type.
Class Instantiations
When we instantiate an Object (e.g. Dog, Walrus, Planet):
public static class Walrus {
public int weight;
public double tuskSize;
public Walrus(int w, double ts) {
weight = w;
tuskSize = ts;
}
}
32 bits
64 bits
new Walrus(1000, 8.3);
Class Instantiations
When we instantiate an Object (e.g. Dog, Walrus, Planet):
32 bits
64 bits
....00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111101000010000000010000010011001100110011001100110011001100110011001101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000....
Green is weight, blue is tuskSize.
(In reality, total Walrus size is slightly larger than 96 bits.)
new Walrus(1000, 8.3);
Class Instantiations
Can think of new as returning the address of the newly created object.
32 bits
64 bits
2384723423
....00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111101000010000000010000010011001100110011001100110011001100110011001101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000....
2384723423th bit
new Walrus(1000, 8.3);
Reference Type Variable Declarations
When we declare a variable of any reference type (Walrus, Dog, Planet):
Walrus someWalrus;
someWalrus = new Walrus(1000, 8.3);
96 bits
64 bits
Walrus someWalrus;
someWalrus = null;
64 bits
Reference Type Variable Declarations
The 64 bit addresses are meaningless to us as humans, so we’ll represent:
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.
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.
a is 64 bits
The Walrus shown is 96 bits.
Walrus a;
a = new Walrus(1000, 8.3);
Walrus b;
b = a;
Reference Types Obey the Golden Rule of Equals
Just as with primitive types, the equals sign copies the bits.
Note: b is currently undefined, not null!
a and b are 64 bits
The Walrus shown is 96 bits.
Walrus a;
a = new Walrus(1000, 8.3);
Walrus b;
b = a;
Reference Types Obey the Golden Rule of Equals
Just as with primitive types, the equals sign copies the bits.
a and b are 64 bits
The Walrus shown is 96 bits.
Walrus a;
a = new Walrus(1000, 8.3);
Walrus b;
b = a;
Parameter Passing
Lecture 3, CS61B, Fall 2023
Goals: Building a List
Primitive Types
Reference Types
Parameter Passing
Instantiation of Arrays
IntList and Linked Data Structures
The Golden Rule of Equals (and Parameter Passing)
Given variables b and a:
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:
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:
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:
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:
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);
}
This is also called pass by value.
The Golden Rule: Summary
There are 9 types of variables in Java:
In box-and-pointer notation, each variable is drawn as a labeled box and values are shown in the box.
The golden rule:
Test Your Understanding: yellkey.com/however
Does the call to doStuff(walrus, x) have an affect on walrus and/or main’s x?
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
Instantiation of Arrays
Lecture 3, CS61B, Fall 2023
Goals: Building a List
Primitive Types
Reference Types
Parameter Passing
Instantiation of Arrays
IntList and Linked Data Structures
Declaration and Instantiation of Arrays
Arrays are also Objects. As we’ve seen, objects are (usually) instantiated using the new keyword.
int[] a;
new int[]{0, 1, 2, 95, 4};
Declaration
Instantiation (HW0 covers this syntax)
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};
Note: Instantiated objects can be lost!
Declaration, instantiation, and assignment.
Declaration
Instantiation
Assignment
IntList and Linked Data Structures
Lecture 3, CS61B, Fall 2023
Goals: Building a List
Primitive Types
Reference Types
Parameter Passing
Instantiation of Arrays
IntList and Linked Data Structures
IntList
Let’s define an IntList as an object containing two member variables:
And define two versions of the same method:
Coding Demo: Adding to End of IntList
public class IntList {
public int first;
public IntList rest;
}
IntList.java
Coding Demo: Adding to End of IntList
public class IntList {
public int first;
public IntList rest;
public static void main(String[] args) {
IntList L = new IntList();
L.first = 5;
L.rest = null;
}
}
IntList.java
Coding Demo: Adding to End of IntList
public class IntList {
public int first;
public IntList rest;
public static void main(String[] args) {
IntList L = new IntList();
L.first = 5;
L.rest = null;
L.rest = new IntList();
L.rest.first = 10;
}
}
IntList.java
Coding Demo: Adding to End of IntList
public class IntList {
public int first;
public IntList rest;
public static void main(String[] args) {
IntList L = new IntList();
L.first = 5;
L.rest = null;
L.rest = new IntList();
L.rest.first = 10;
L.rest.rest = new IntList();
L.rest.rest.first = 15;
}
}
IntList.java
Coding Demo: Adding to Start of IntList
public class IntList {
public int first;
public IntList rest;
}
IntList.java
Coding Demo: Adding to Start of IntList
public class IntList {
public int first;
public IntList rest;
public IntList(int f, IntList r) {
first = f;
rest = r;
}
}
IntList.java
Coding Demo: Adding to Start of IntList
public class IntList {
public int first;
public IntList rest;
public IntList(int f, IntList r) {
first = f;
rest = r;
}
public static void main(String[] args) {
IntList L = new IntList(15, null);
L = new IntList(10, L);
L = new IntList(5, L);
}
}
IntList.java
Coding Demo: IntList size
public class IntList {
public int first;
public IntList rest;
public IntList(int f, IntList r) {
first = f;
rest = r;
}
public static void main(String[] args) {
IntList L = new IntList(15, null);
L = new IntList(10, L);
L = new IntList(5, L);
System.out.println(L.size()); // should print out 3
}
}
IntList.java
Coding Demo: IntList size
public class IntList {
public int first;
public IntList rest;
/** Return the size of the list using... recursion! */
public int size() {
}
}
IntList.java
Coding Demo: IntList size
public class IntList {
public int first;
public IntList rest;
/** Return the size of the list using... recursion! */
public int size() {
if (rest == null) {
}
}
}
IntList.java
Coding Demo: IntList size
public class IntList {
public int first;
public IntList rest;
/** Return the size of the list using... recursion! */
public int size() {
if (rest == null) {
return 1;
}
}
}
IntList.java
Coding Demo: IntList size
public class IntList {
public int first;
public IntList rest;
/** Return the size of the list using... recursion! */
public int size() {
if (rest == null) {
return 1;
}
return 1 + this.rest.size();
}
}
IntList.java
Coding Demo: IntList iterativeSize
public class IntList {
public int first;
public IntList rest;
public IntList(int f, IntList r) {
first = f;
rest = r;
}
public static void main(String[] args) {
IntList L = new IntList(15, null);
L = new IntList(10, L);
L = new IntList(5, L);
System.out.println(L.iterativeSize()); // should also print out 3
}
}
IntList.java
Coding Demo: IntList iterativeSize
public class IntList {
public int first;
public IntList rest;
/** Return the size of the list using no recursion! */
public int iterativeSize() {
}
}
IntList.java
Coding Demo: IntList iterativeSize
public class IntList {
public int first;
public IntList rest;
/** Return the size of the list using no recursion! */
public int iterativeSize() {
IntList p = this;
}
}
IntList.java
Coding Demo: IntList iterativeSize
public class IntList {
public int first;
public IntList rest;
/** Return the size of the list using no recursion! */
public int iterativeSize() {
IntList p = this;
int totalSize = 0;
}
}
IntList.java
Coding Demo: IntList iterativeSize
public class IntList {
public int first;
public IntList rest;
/** Return the size of the list using no recursion! */
public int iterativeSize() {
IntList p = this;
int totalSize = 0;
while (p != null) {
}
}
}
IntList.java
Coding Demo: IntList iterativeSize
public class IntList {
public int first;
public IntList rest;
/** Return the size of the list using no recursion! */
public int iterativeSize() {
IntList p = this;
int totalSize = 0;
while (p != null) {
totalSize += 1;
}
}
}
IntList.java
Coding Demo: IntList iterativeSize
public class IntList {
public int first;
public IntList rest;
/** Return the size of the list using no recursion! */
public int iterativeSize() {
IntList p = this;
int totalSize = 0;
while (p != null) {
totalSize += 1;
p = p.rest;
}
}
}
IntList.java
Coding Demo: IntList iterativeSize
public class IntList {
public int first;
public IntList rest;
/** Return the size of the list using no recursion! */
public int iterativeSize() {
IntList p = this;
int totalSize = 0;
while (p != null) {
totalSize += 1;
p = p.rest;
}
return totalSize;
}
}
IntList.java
Challenge
Write a method int get(int i) that returns the ith item in the list.
Ways to work:
L.get(0): 5
L.get(1): 10
See the video online for a solution: https://www.youtube.com/watch?v=qnmxD_21DNk
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();
...
Coding Demo: IntList get
public class IntList {
public int first;
public IntList rest;
public IntList(int f, IntList r) {
first = f;
rest = r;
}
public static void main(String[] args) {
IntList L = new IntList(15, null);
L = new IntList(10, L);
L = new IntList(5, L);
System.out.println(L.get(1)); // should print out 10
}
}
IntList.java
Coding Demo: IntList get
public class IntList {
public int first;
public IntList rest;
/** Return the ith item of this IntList. */
public int get(int i) {
}
}
IntList.java
Coding Demo: IntList get
public class IntList {
public int first;
public IntList rest;
/** Return the ith item of this IntList. */
public int get(int i) {
if (i == 0) {
}
}
}
IntList.java
Coding Demo: IntList get
public class IntList {
public int first;
public IntList rest;
/** Return the ith item of this IntList. */
public int get(int i) {
if (i == 0) {
return first;
}
}
}
IntList.java
Coding Demo: IntList get
public class IntList {
public int first;
public IntList rest;
/** Return the ith item of this IntList. */
public int get(int i) {
if (i == 0) {
return first;
}
return rest.get(i - 1);
}
}
IntList.java
Question: yellkey.com/until
What is your comfort level with recursive data structure code?
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.
L
Q
Q
L
This week’s discussion also features optional IntList problems.