CSE 373 Su23 Section 1
Welcome, 12X/14X Review��TA: [insert TA name here]
Who Am I?
[insert TA intro here]
Ice-breaker
Administrivia
Course Logistics
Course Logistics (cont.)
Golden Rule of Section
MicroTeach:
Passing by Value and Reference
Note: The underlined code has just been executed.��Code for main is underlined in red. Code in functions called by main is underlined in blue.
main
x
y
1
0
1
Note 2: x is an int (primitive type). y and z are arrays (reference type). Hence the arrows.
z
0
1
2
2
Note 1: Each method in Java gets its own set of variables to operate on. This is called a stack frame (you don’t need to know the name).
main
x
y
1
0
1
z
0
1
2
2
foo
1
x
z
y
Note: The int is passed by value, the arrays by reference. This is because an int is a primitive type, while an array is not!
main
x
y
1
0
1
z
0
1
2
2
foo
2
x
z
y
Because it was passed by value, each method gets its own copy of the int!
main
x
y
1
0
1
z
0
1
2
2
foo
2
x
z
y
1
2
3
main
x
y
1
0
1
z
0
1
2
2
Go To Worksheet��Do Problem 1.1A
Problem 1.1a Reference Semantics
Note: The underlined code has just been executed.��Code for main is underlined in red. Code in functions called by main is underlined in blue.
main
x
a
1
0
0
Output:
Note: When an array is born, it holds the default value for its data type unless otherwise specified. (The default for int is 0!)
main
x
a
1
0
0
Output:
mystery1
x
list
1
Note: The int is passed by value, the array by reference.This is because an int is a primitive type, while an array is not!
main
x
a
1
0
1
Output:
mystery1
x
list
1
main
x
a
1
0
1
Output:
mystery1
x
list
2
Note: Each method has its own set of variables that it acts on!�(So the x in the mystery1 method changes).
main
x
a
1
0
1
Output:
2 [0, 1]
mystery1
x
list
2
main
x
a
1
0
1
Output:
1 [0, 1]
main
x
a
0
0
2
Output:
main
x
a
0
0
2
Output:
mystery1
x
list
0
main
x
a
0
1
2
Output:
mystery1
x
list
0
main
x
a
0
1
2
Output:
mystery1
x
list
1
main
x
a
0
1
2
Output:
1 [1, 2]
mystery1
x
list
1
main
x
a
0
1
2
Output:
0 [1, 2]
main
x
a
0
1
2
Output:
mystery2
x
list
0
main
x
a
0
1
2
Output:
Note: list is a reference (or pointer) to an array, so here we change the reference to point to a new array.
mystery2
x
list
0
0
0
main
x
a
0
1
2
Output:
0 [0, 0]
mystery2
x
list
0
0
0
main
x
a
0
1
2
Output:
0 [1, 2]
Generics
Overview of Generics
Making a Class Generic
Generic MyArrayList Example
Don’t worry if generics are still confusing. You’ll have an opportunity to practice in Friday’s lecture! :)
Go To Worksheet��Do Problems 1.2A and 1.3A��(Both removeFront() problems)
Problem 1.2a MyArrayList removeFront()
Example: MyArrayList removeFront(4)
data = [8, 17, 9, 24, 42, 3, 8]
size = 7
list.removeFront(4)
data = [42, 3, 8]
size = 3
Note: Remember that we’re implementing the MyArrayList data structure, so when we write the code for removeFront(k), we need to make sure to modify our data and size fields accordingly!
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
0
1
2
3
4
5
6
9
24
42
3
8
8
17
k = 4
size = 7
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
0
1
2
3
4
5
6
9
24
42
3
8
8
17
Intuition: We want our array to contain valid data in the first size - k indices!
k = 4
size = 7
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
0
1
2
3
4
5
6
9
24
42
3
8
8
17
k = 4
size = 7
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
0
1
2
3
4
5
6
9
24
42
3
8
8 42
17
k = 4
size = 7
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
0
1
2
3
4
5
6
9
24
42
3
8
8 42
17
k = 4
size = 7
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
0
1
2
3
4
5
6
9
24
42
3
8
8 42
17 3
k = 4
size = 7
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
0
1
2
3
4
5
6
9
24
42
3
8
8 42
17 3
k = 4
size = 7
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
0
1
2
3
4
5
6
9 8
24
42
3
8
8 42
17 3
k = 4
size = 7
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
k = 4
size = 7
The first 3 indices of data now have what we want!
0
1
2
3
4
5
6
9 8
24
42
3
8
8 42
17 3
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
k = 4
size = 7
What about the remaining elements in data?
0
1
2
3
4
5
6
8
24
42
3
8
42
3
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
0
1
2
3
4
5
6
8
24
42
3
8
42
3
k = 4
size = 7 - 4
We can just get rid of them by reducing size!
Walkthrough: MyArrayList removeFront(4)
Expected behavior:
[8, 17, 9, 24, 42, 3, 8] → [42, 3, 8]
public void removeFront(int k) {...}
0
1
2
3
4
5
6
8
24
42
3
8
42
3
Note: The last 4 indices still exist in data. Remember that data.length != size. Since it’s an expectation that all our MyArrayList methods will only access indices of data between 0 and size - 1, we don’t have to worry about what values live beyond that! As such, the client of our class can only interact with indices 0 to size - 1.
k = 4
size = 3
Solution: MyArrayList removeFront(k)
public class MyArrayList<T> {
private T[] data;
private int size;
public void removeFront(int k) {
for (int i = 0; i < this.size - k; i++) {
this.data[i] = this.data[i + k];
}
this.size -= k;
}
// other methods commented out
}
Problem 1.3a MyLinkedList removeFront()
Example: MyLinkedList removeFront(2)
8
front
null
data
11
data
91
data
2
data
next
next
next
next
list.removeFront(2)
91
front
null
data
2
data
next
next
Note: Remember that we’re implementing the MyLinkedList data structure, so when we write the code for removeFront(k), we need to make sure to modify our front field accordingly!
Walkthrough: MyLinkedList removeFront(2)
public void removeFront(int k) {...}
8
f
null
11
91
2
Expected behavior:
91
f
null
2
Before:
After:
8
f
null
11
91
2
Walkthrough: MyLinkedList removeFront(2)
public void removeFront(int k) {...}
8
f
null
11
91
2
Expected behavior:
91
f
null
2
Before:
After:
8
f
null
11
91
2
Intuition: Advance the front pointer k times.
Walkthrough: MyLinkedList removeFront(2)
public void removeFront(int k) {...}
8
f
null
11
91
2
Expected behavior:
91
f
null
2
Before:
After:
8
f
null
11
91
2
curr
Walkthrough: MyLinkedList removeFront(2)
public void removeFront(int k) {...}
8
f
null
11
91
2
Expected behavior:
91
f
null
2
Before:
After:
8
f
null
11
91
2
curr
Walkthrough: MyLinkedList removeFront(2)
public void removeFront(int k) {...}
8
f
null
11
91
2
Expected behavior:
91
f
null
2
Before:
After:
8
f
null
11
91
2
curr
Walkthrough: MyLinkedList removeFront(2)
public void removeFront(int k) {...}
8
f
null
11
91
2
Expected behavior:
91
f
null
2
Before:
After:
8
f
null
11
91
2
curr
curr now points to what we want!
Walkthrough: MyLinkedList removeFront(2)
public void removeFront(int k) {...}
8
f
null
11
91
2
Expected behavior:
91
f
null
2
Before:
After:
8
f
null
11
91
2
curr
Walkthrough: MyLinkedList removeFront(2)
public void removeFront(int k) {...}
8
f
null
11
91
2
Expected behavior:
91
f
null
2
Before:
After:
8
null
11
91
2
f
Note: This part gets automatically deleted when Java runs its garbage collector because there’s nothing pointing to it!
Walkthrough: MyLinkedList removeFront(2)
public void removeFront(int k) {...}
8
f
null
11
91
2
Expected behavior:
91
f
null
2
Before:
After:
f
null
91
2
Solution: MyLinkedList removeFront(k)
public class MyLinkedList<T> {
private Node<T> front;
private static class Node<T> {
public final T data;
public Node<T> next;
}
public void removeFront(int k) {
Node<T> curr = this.front;
for (int i = 0; i < k; i++) {
curr = curr.next;
}
this.front = curr;
}
// other methods commented out
}