1 of 55

Scope, Static, Linked Lists, Arrays

Discussion 03

CS 61B Fall 2023

2 of 55

Example Agenda

1:10 - 1:15 ~ announcements
1:15 - 1:30 ~ content review
1:30 - 1:40 ~ question 1
1:40 - 1:55 ~ question 2
Question 3 if time

CS 61B Fall 2023

3 of 55

Announcements

Weekly Survey 2 - due this Tuesday 9/5
Lab 3 - due next Monday 9/11
Proj 1A - due next Monday 9/11
Project Party 9/6
Carefully read the OH guidelines if you attend

CS 61B Fall 2023

4 of 55

Content Review

CS 61B Fall 2023

5 of 55

GRoE: Golden Rule of Equals

“Given variables y and x:

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

Java is pass-by-value: when you call a function and give it some arguments, the function called receives an exact copy of those arguments, tied to its own local variables.

“Copies all the bits” means different things for primitive vs. reference types.

CS 61B Fall 2023

6 of 55

Primitive vs. Reference Types

Primitive Types are represented by a certain number of bytes stored at the location of the variable in memory. There are only 8 in Java.

Examples: byte, short, int, long, float, double, boolean, char

Reference Types are represented by a memory address stored at the location of the variable which points to where the full object is (all objects are stored at addresses in memory). This memory address is often referred to as a pointer.

Examples: Strings, Arrays, Linked Lists, Dogs, etc.

CS 61B Fall 2023

7 of 55

Back to the GRoE

“Given variables y and x:

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

The value of a primitive type gets copied directly upon variable assignment

Ex. int x = 5; means that variable x stores the value of 5

The value of a reference type is a “shallow” copy upon variable assignment: the pointer (memory address) is copied, and the object itself in memory is not

Exception: null is a special pointer that we compare with ==

CS 61B Fall 2023

8 of 55

A Quick Example

int x = 5;

int[] arr = new int[]{1, 2, 3, 5};

1

2

3

5

x

arr

CS 61B Fall 2023

9 of 55

A Quick Example

int x = 5;

int[] arr = new int[]{1, 2, 3, 5};

doSomething(x, arr);

...

public void doSomething(int y, int[] other) {

y = 9;

other[2] = 4;

}

1

2

3

5

x

arr

5

y

other

CS 61B Fall 2023

10 of 55

A Quick Example

int x = 5;

int[] arr = new int[]{1, 2, 3, 5};

doSomething(x, arr);

...

public void doSomething(int y, int[] other) {

y = 9;

other[2] = 4;

}

1

2

4

5

x

arr

9

y

other

CS 61B Fall 2023

11 of 55

Static vs. Instance, Revisited

Static variables and functions belong to the whole class.

Example: Every 61B Student shares the same professor, and if the professor were to change it would change for everyone.

Instance variables and functions belong to each individual instance.

Example: Each 61B Student has their own ID number, and changing a student’s ID number doesn’t change anything for any other student.

CS 61B Fall 2023

12 of 55

this vs. static

this

Non-static methods can only be called using an instance of that object, so during evaluation of that function, you will always have access to this instance of the object, referred to as this

static methods

do not require an instance of that object in order to be called, so during evaluation of that function, you cannot rely on access to this instance of the object

static variables

shared by all instances of the class; each instance does not get its own copy but can access

Check for understanding: can you reference this in static methods? Can you reference static variables in instance methods? Why or why not?

CS 61B Fall 2023

13 of 55

Arrays

Arrays are data structures that can only hold elements of the same (primitive or reference) type of value.

arr[i] holds a value in the ith position of the array (zero-indexed). We can also have n-dimensional

arrays (ie. int[][] a = new int[3][2]; you can index into these like a[2][1])

4

1

8

0

1

2

0

1

2

Cat

2

id

5

age

Cat

4

id

9

age

Cat

8

id

1

age

Arrays have a set length when instantiated, so they cannot be extended / shortened with pointers like a Linked List. To resize, we need to copy over all elements to a new array (ie. System.arraycopy)

CS 61B Fall 2023

14 of 55

Linked Lists

Linked Lists are modular lists that are made up of nodes that each contain a value and a pointer to the next node. To access values in a Linked List, you must use dot notation.

Example: intList.get(2)

Can be extended or shortened by changing the pointers of its nodes (unlike arrays)

Can’t be indexed directly into like an array: instead, the computer has to iterate through all of the nodes up to that point and follow their next pointers
A sentinel is a special type of node that is often used as an empty placeholder for ease of adding / deleting nodes, especially from the front or back of the Linked List

In a circular doubly-linked implementation, the sentinel’s next and prev pointers are the first and last nodes respectively

CS 61B Fall 2023

15 of 55

Worksheet

CS 61B Fall 2023

16 of 55

1 Static Electricity

public class Pokemon {
public String name;
public int level;
public static String trainer = "Ash";
public static int partySize = 0;
public Pokemon(String name, int level) {
this.name = name;
this.level = level;
this.partySize += 1;
}
public static void main(String[] args) {
Pokemon p = new Pokemon("Pikachu", 17);
Pokemon j = new Pokemon("Jolteon", 99);
System.out.println("Party size: " + Pokemon.partySize);
p.printStats()
int level = 18;
Pokemon.change(p, level);
p.printStats()
Pokemon.trainer = "Ash";
j.trainer = "Cynthia";
p.printStats();
}

public static void change(Pokemon poke, int level) {
poke.level = level;
level = 50;
poke = new Pokemon("Luxray", 1);
poke.trainer = "Team Rocket";
}
public void printStats() {
System.out.print(name + " " + level + " " + trainer);
}
}

Write what would be printed after the main method is executed.

Java visualizer: https://ktinyurl.com/48uk72kc

CS 61B Fall 2023

17 of 55

1 Static Electricity

public class Pokemon {
public String name;
public int level;
public static String trainer = "Ash";
public static int partySize = 0;
public Pokemon(String name, int level) {
this.name = name;
this.level = level;
this.partySize += 1;
}
public static void main(String[] args) {
Pokemon p = new Pokemon("Pikachu", 17);
Pokemon j = new Pokemon("Jolteon", 99);
System.out.println("Party size: " + Pokemon.partySize);
p.printStats()
int level = 18;
Pokemon.change(p, level);
p.printStats()
Pokemon.trainer = "Ash";
j.trainer = "Cynthia";
p.printStats();
}

public static void change(Pokemon poke, int level) {
poke.level = level;
level = 50;
poke = new Pokemon("Luxray", 1);
poke.trainer = "Team Rocket";
}
public void printStats() {
System.out.print(name + " " + level + " " + trainer);
}
}

Party size: 2

Pikachu 17 Ash

Pikachu 18 Team Rocket

Pikachu 18 Cynthia

Java visualizer: https://tinyurl.com/48uk72kc

CS 61B Fall 2023

18 of 55

1 Static Electricity

public class Pokemon {
public String name;
public int level;
public static String trainer = "Ash";
public static int partySize = 0;
public Pokemon(String name, int level) {
this.name = name;
this.level = level;
this.partySize += 1;
}
public static void main(String[] args) {
Pokemon p = new Pokemon("Pikachu", 17);
Pokemon j = new Pokemon("Jolteon", 99);
System.out.println("Party size: " + Pokemon.partySize);
p.printStats()
int level = 18;
Pokemon.change(p, level);
p.printStats()
Pokemon.trainer = "Ash";
j.trainer = "Cynthia";
p.printStats();
}

public static void change(Pokemon poke, int level) {
poke.level = level;
level = 50;
poke = new Pokemon("Luxray", 1);
poke.trainer = "Team Rocket";
}
public void printStats() {
System.out.print(name + " " + level + " " + trainer);
}
}

On line 28, is level:

An instance variable of the Pokemon object?
The local variable containing the parameter to the change method?
The local variable in the main method?
Something else?

CS 61B Fall 2023

19 of 55

1 Static Electricity

public class Pokemon {
public String name;
public int level;
public static String trainer = "Ash";
public static int partySize = 0;
public Pokemon(String name, int level) {
this.name = name;
this.level = level;
this.partySize += 1;
}
public static void main(String[] args) {
Pokemon p = new Pokemon("Pikachu", 17);
Pokemon j = new Pokemon("Jolteon", 99);
System.out.println("Party size: " + Pokemon.partySize);
p.printStats()
int level = 18;
Pokemon.change(p, level);
p.printStats()
Pokemon.trainer = "Ash";
j.trainer = "Cynthia";
p.printStats();
}

public static void change(Pokemon poke, int level) {
poke.level = level;
level = 50;
poke = new Pokemon("Luxray", 1);
poke.trainer = "Team Rocket";
}
public void printStats() {
System.out.print(name + " " + level + " " + trainer);
}
}

On line 28, is level:

An instance variable of the Pokemon object
The local variable containing the parameter to the change method
The local variable in the main method
Something else?

CS 61B Fall 2023

20 of 55

1 Static Electricity

public class Pokemon {
public String name;
public int level;
public static String trainer = "Ash";
public static int partySize = 0;
public Pokemon(String name, int level) {
this.name = name;
this.level = level;
this.partySize += 1;
}
public static void main(String[] args) {
Pokemon p = new Pokemon("Pikachu", 17);
Pokemon j = new Pokemon("Jolteon", 99);
System.out.println("Party size: " + Pokemon.partySize);
p.printStats()
int level = 18;
Pokemon.change(p, level);
p.printStats()
Pokemon.trainer = "Ash";
j.trainer = "Cynthia";
p.printStats();
}

public static void change(Pokemon poke, int level) {
poke.level = level;
level = 50;
poke = new Pokemon("Luxray", 1);
poke.trainer = "Team Rocket";
}
public void printStats() {
System.out.print(name + " " + level + " " + trainer);
}
}

If we were to call Pokemon.printStats() at the end of our main method, what would happen?

CS 61B Fall 2023

21 of 55

1 Static Electricity

public class Pokemon {
public String name;
public int level;
public static String trainer = "Ash";
public static int partySize = 0;
public Pokemon(String name, int level) {
this.name = name;
this.level = level;
this.partySize += 1;
}
public static void main(String[] args) {
Pokemon p = new Pokemon("Pikachu", 17);
Pokemon j = new Pokemon("Jolteon", 99);
System.out.println("Party size: " + Pokemon.partySize);
p.printStats()
int level = 18;
Pokemon.change(p, level);
p.printStats()
Pokemon.trainer = "Ash";
j.trainer = "Cynthia";
p.printStats();
}

public static void change(Pokemon poke, int level) {
poke.level = level;
level = 50;
poke = new Pokemon("Luxray", 1);
poke.trainer = "Team Rocket";
}
public void printStats() {
System.out.print(name + " " + level + " " + trainer);
}
}

Error!

printStats() is an instance method
Only static methods can be called using the name of the class (ie. Pokemon)
static methods can only modify static variables, but instance methods can modify both

CS 61B Fall 2023

22 of 55

2 Rotate Extra

Implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, without modifying A. Note: the modulo of a negative number is still negative

public static int[] rotate(int[] A, int k) {

int rightShift = _______________________________;

if (_________________________) {

_____________________________________________;

}

int[] newArr = ____________________________________;

for (__________________________________________) {

int newIndex = ________________________________;

_____________________________________________;

}

return newArr;

}

CS 61B Fall 2023

23 of 55

2 Rotate Extra

Implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, without modifying A. Note: the modulo of a negative number is still negative

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (_________________________) {

_____________________________________________;

}

int[] newArr = ____________________________________;

for (__________________________________________) {

int newIndex = ________________________________;

_____________________________________________;

}

return newArr;

}

CS 61B Fall 2023

24 of 55

2 Rotate Extra

Implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, without modifying A. Note: the modulo of a negative number is still negative

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (rightShift < 0) {

rightShift += A.length;;

}

int[] newArr = ____________________________________;

for (__________________________________________) {

int newIndex = ________________________________;

_____________________________________________;

}

return newArr;

}

CS 61B Fall 2023

25 of 55

2 Rotate Extra

Implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, without modifying A. Note: the modulo of a negative number is still negative

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (rightShift < 0) {

rightShift += A.length;

}

int[] newArr = new int[A.length];

for (__________________________________________) {

int newIndex = ________________________________;

_____________________________________________;

}

return newArr;

}

CS 61B Fall 2023

26 of 55

2 Rotate Extra

Implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, without modifying A. Note: the modulo of a negative number is still negative

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (rightShift < 0) {

rightShift += A.length;

}

int[] newArr = new int[A.length];

for (int i = 0; i < A.length; i++) {

int newIndex = ________________________________;

_____________________________________________;

}

return newArr;

}

CS 61B Fall 2023

27 of 55

2 Rotate Extra

Implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, without modifying A. Note: the modulo of a negative number is still negative

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (rightShift < 0) {

rightShift += A.length;

}

int[] newArr = new int[A.length];

for (int i = 0; i < A.length; i++) {

int newIndex = (i + rightShift) % A.length;

_____________________________________________;

}

return newArr;

}

CS 61B Fall 2023

28 of 55

2 Rotate Extra

Implement rotate such that it returns a new array containing the elements in A have shifted k positions to the right, without modifying A. Note: the modulo of a negative number is still negative

public static int[] rotate(int[] A, int k) {

int rightShift = k % A.length;

if (rightShift < 0) {

rightShift += A.length;

}

int[] newArr = new int[A.length];

for (int i = 0; i < A.length; i++) {

int newIndex = (i + rightShift) % A.length;

newArr[newIndex] = A[i];

}

return newArr;

}

CS 61B Fall 2023

29 of 55

3 Cardinal Directions

DLLStringNode L = new DLLStringNode(null, "eat", null);
L = new DLLStringNode(null, "bananas", L);
L = new DLLStringNode(null, "never", L);
L = new DLLStringNode(null, "sometimes", L);
DLLStringNode M = L.next;
DLLStringNode R = new DLLStringNode(null, "shredded", null);
R = new DLLStringNode(null, "wheat", R);
R.next.next = R;
M.next.next.next = R.next;
L.next.next = L.next.next.next;
L = M.next;
M.next.next.prev = R;
L.prev = M;
L.next.prev = L;
R.prev = L.next.next;

Draw out the resulting diagram after executing all the lines.

CS 61B Fall 2023

30 of 55

3 Cardinal Directions

DLLStringNode L = new DLLStringNode(null, "eat", null);

“eat”

L

CS 61B Fall 2023

31 of 55

3 Cardinal Directions

L = new DLLStringNode(null, "bananas", L);

“bananas”

“eat”

L

CS 61B Fall 2023

32 of 55

3 Cardinal Directions

L = new DLLStringNode(null, "never", L);

“never”

“bananas”

L

“eat”

CS 61B Fall 2023

33 of 55

3 Cardinal Directions

L = new DLLStringNode(null, "sometimes", L);

“sometimes”

“never”

L

“bananas”

“eat”

CS 61B Fall 2023

34 of 55

3 Cardinal Directions

DLLStringNode M = L.next;

“sometimes”

“never”

L

“bananas”

“eat”

M

CS 61B Fall 2023

35 of 55

3 Cardinal Directions

DLLStringNode R = new DLLStringNode(null, "shredded", null);

“sometimes”

“never”

L

“bananas”

“eat”

M

R

“shredded”

CS 61B Fall 2023

36 of 55

3 Cardinal Directions

R = new DLLStringNode(null, "wheat", R);

“sometimes”

“never”

L

“bananas”

“eat”

M

R

“wheat”

“shredded”

CS 61B Fall 2023

37 of 55

3 Cardinal Directions

R.next.next = R;

“sometimes”

“never”

L

“bananas”

“eat”

M

R

“wheat”

“shredded”

CS 61B Fall 2023

38 of 55

3 Cardinal Directions

M.next.next.next = R.next;

“sometimes”

“never”

L

“bananas”

“eat”

M

R

“wheat”

“shredded”

CS 61B Fall 2023

39 of 55

3 Cardinal Directions

L.next.next = L.next.next.next;

“sometimes”

“never”

L

“eat”

M

R

“wheat”

“shredded”

CS 61B Fall 2023

40 of 55

3 Cardinal Directions

“sometimes”

“never”

L

“eat”

M

R

“wheat”

“shredded”

CS 61B Fall 2023

41 of 55

3 Cardinal Directions

L = M.next;

“never”

L

“eat”

M

R

“wheat”

“shredded”

CS 61B Fall 2023

42 of 55

3 Cardinal Directions

M.next.next.prev = R;

“never”

L

“eat”

M

R

“wheat”

“shredded”

CS 61B Fall 2023

43 of 55

3 Cardinal Directions

L.prev = M;

“never”

L

“eat”

M

R

“wheat”

“shredded”

CS 61B Fall 2023

44 of 55

3 Cardinal Directions

L.next.prev = L;

“never”

L

“eat”

M

R

“wheat”

“shredded”

CS 61B Fall 2023

45 of 55

3 Cardinal Directions

R.prev = L.next.next;

“never”

L

“eat”

M

R

“wheat”

“shredded”

Java visualizer: https://tinyurl.com/3hy6n934

CS 61B Fall 2023

46 of 55

4 Gridify

public class SLList {
Node sentinel;
public SLList() {
this.sentinel = new Node();
}
private static class Node {
int item;
Node next;
}
public int[][] gridify(int rows, int cols) {
int[][] grid = ____________________________;
___________________________________________;
return grid;
}

private void gridifyHelper(int[][] grid, Node curr, int numFilled) {
if (_________________________) {
return;
}
int row = ______________________;
int col = ______________________;
_________________ = _______________;
___________________________________;
}

CS 61B Fall 2023

47 of 55

4 Gridify

public class SLList {
Node sentinel;
public SLList() {
this.sentinel = new Node();
}
private static class Node {
int item;
Node next;
}
public int[][] gridify(int rows, int cols) {
int[][] grid = new int[rows][cols];
___________________________________________;
return grid;
}

private void gridifyHelper(int[][] grid, Node curr, int numFilled) {
if (_________________________) {
return;
}
int row = ______________________;
int col = ______________________;
_________________ = _______________;
___________________________________;
}

CS 61B Fall 2023

48 of 55

4 Gridify

public class SLList {
Node sentinel;
public SLList() {
this.sentinel = new Node();
}
private static class Node {
int item;
Node next;
}
public int[][] gridify(int rows, int cols) {
int[][] grid = new int[rows][cols];
gridifyHelper(grid, sentinel.next, 0);
return grid;
}

private void gridifyHelper(int[][] grid, Node curr, int numFilled) {
if (_________________________) {
return;
}
int row = ______________________;
int col = ______________________;
grid[row][col] = _______________;
___________________________________;
}

CS 61B Fall 2023

49 of 55

4 Gridify

public class SLList {
Node sentinel;
public SLList() {
this.sentinel = new Node();
}
private static class Node {
int item;
Node next;
}
public int[][] gridify(int rows, int cols) {
int[][] grid = new int[rows][cols];
gridifyHelper(grid, sentinel.next, 0);
return grid;
}

private void gridifyHelper(int[][] grid, Node curr, int numFilled) {
if (curr == sentinel || numFilled >= grid.length * grid[0].length) {
return;
}
int row = ______________________;
int col = ______________________;
grid[row][col] = _______________;
___________________________________;
}

CS 61B Fall 2023

50 of 55

4 Gridify

public class SLList {
Node sentinel;
public SLList() {
this.sentinel = new Node();
}
private static class Node {
int item;
Node next;
}
public int[][] gridify(int rows, int cols) {
int[][] grid = new int[rows][cols];
gridifyHelper(grid, sentinel.next, 0);
return grid;
}

private void gridifyHelper(int[][] grid, Node curr, int numFilled) {
if (curr == sentinel || numFilled >= grid.length * grid[0].length) {
return;
}
int row = numFilled / grid[0].length;
int col = ______________________;
grid[row][col] = _______________;
___________________________________;
}

CS 61B Fall 2023

51 of 55

4 Gridify

public class SLList {
Node sentinel;
public SLList() {
this.sentinel = new Node();
}
private static class Node {
int item;
Node next;
}
public int[][] gridify(int rows, int cols) {
int[][] grid = new int[rows][cols];
gridifyHelper(grid, sentinel.next, 0);
return grid;
}

private void gridifyHelper(int[][] grid, Node curr, int numFilled) {
if (curr == sentinel || numFilled >= grid.length * grid[0].length) {
return;
}
int row = numFilled / grid[0].length;
int col = numFilled % grid[0].length;
grid[row][col] = _______________;
___________________________________;
}

CS 61B Fall 2023

52 of 55

4 Gridify

public class SLList {
Node sentinel;
public SLList() {
this.sentinel = new Node();
}
private static class Node {
int item;
Node next;
}
public int[][] gridify(int rows, int cols) {
int[][] grid = new int[rows][cols];
gridifyHelper(grid, sentinel.next, 0);
return grid;
}

private void gridifyHelper(int[][] grid, Node curr, int numFilled) {
if (curr == sentinel || numFilled >= grid.length * grid[0].length) {
return;
}
int row = numFilled / grid[0].length;
int col = numFilled % grid[0].length;
grid[row][col] = curr.item;
___________________________________;
}

CS 61B Fall 2023

53 of 55

4 Gridify

public class SLList {
Node sentinel;
public SLList() {
this.sentinel = new Node();
}
private static class Node {
int item;
Node next;
}
public int[][] gridify(int rows, int cols) {
int[][] grid = new int[rows][cols];
gridifyHelper(grid, sentinel.next, 0);
return grid;
}

private void gridifyHelper(int[][] grid, Node curr, int numFilled) {
if (curr == sentinel || numFilled >= grid.length * grid[0].length) {
return;
}
int row = numFilled / grid[0].length;
int col = numFilled % grid[0].length;
grid[row][col] = curr.item;
gridifyHelper(grid, curr.next, numFilled + 1);
}

CS 61B Fall 2023

54 of 55

4 Gridify

public class SLList {
Node sentinel;
public SLList() {
this.sentinel = new Node();
}
private static class Node {
int item;
Node next;
}
public int[][] gridify(int rows, int cols) {
int[][] grid = new int[rows][cols];
gridifyHelper(grid, sentinel.next, 0);
return grid;
}

private void gridifyHelper(int[][] grid, Node curr, int numFilled) {
if (curr == sentinel || numFilled >= grid.length * grid[0].length) {
return;
}
int row = numFilled / grid[0].length;
int col = numFilled % grid[0].length;
grid[row][col] = curr.item;
gridifyHelper(grid, curr.next, numFilled + 1);
}

Why helper method here? Why can’t we just have the signature for gridify also have a pointer to the curr node, such that the user of the function passes in the sentinel each time?

CS 61B Fall 2023

55 of 55

4 Gridify

public class SLList {
Node sentinel;
public SLList() {
this.sentinel = new Node();
}
private static class Node {
int item;
Node next;
}
public int[][] gridify(int rows, int cols) {
int[][] grid = new int[rows][cols];
gridifyHelper(grid, sentinel.next, 0);
return grid;
}

private void gridifyHelper(int[][] grid, Node curr, int numFilled) {
if (curr == sentinel || numFilled >= grid.length * grid[0].length) {
return;
}
int row = numFilled / grid[0].length;
int col = numFilled % grid[0].length;
grid[row][col] = curr.item;
gridifyHelper(grid, curr.next, numFilled + 1);
}

Why helper method here? Why can’t we just have the signature for gridify also have a pointer to the curr node, such that the user of the function passes in the sentinel each time?

We need a helper to keep track of which node and index we’re on.

If we make the change: it breaks the abstraction barrier - requires our user to understand sentinels.

If they pass in random values - incorrect answer.

CS 61B Fall 2023