Scope, Static, Linked Lists, Arrays

Discussion 03

CS 61B Fall 2023

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

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

Content Review

CS 61B Fall 2023

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

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

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

A Quick Example

int x = 5;

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

​

​

​

5

x

arr

CS 61B Fall 2023

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;

}

​

​

​

5

x

arr

9

y

other

CS 61B Fall 2023

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

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

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

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

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

Worksheet

CS 61B Fall 2023

1 Boxes and Pointers

1 IntList L1 = IntList.list(1, 2, 3);

2 IntList L2 = new IntList(4, L1.rest);

3 L2.rest.first = 13;

4 L1.rest.rest.rest = L2;

5 IntList L3 = IntList.list(50);

6 L2.rest.rest = L3;

​

CS 61B Fall 2023

1 Boxes and Pointers

1 IntList L1 = IntList.list(1, 2, 3);

2 IntList L2 = new IntList(4, L1.rest);

3 L2.rest.first = 13;

4 L1.rest.rest.rest = L2;

5 IntList L3 = IntList.list(50);

6 L2.rest.rest = L3;

L1

1

2

3

CS 61B Fall 2023

1 Boxes and Pointers

1 IntList L1 = IntList.list(1, 2, 3);

2 IntList L2 = new IntList(4, L1.rest);

3 L2.rest.first = 13;

4 L1.rest.rest.rest = L2;

5 IntList L3 = IntList.list(50);

6 L2.rest.rest = L3;

L1

L2

1

2

3

4

CS 61B Fall 2023

1 Boxes and Pointers

1 IntList L1 = IntList.list(1, 2, 3);

2 IntList L2 = new IntList(4, L1.rest);

3 L2.rest.first = 13;

4 L1.rest.rest.rest = L2;

5 IntList L3 = IntList.list(50);

6 L2.rest.rest = L3;

L1

L2

1

13

3

4

CS 61B Fall 2023

1 Boxes and Pointers

1 IntList L1 = IntList.list(1, 2, 3);

2 IntList L2 = new IntList(4, L1.rest);

3 L2.rest.first = 13;

4 L1.rest.rest.rest = L2;

5 IntList L3 = IntList.list(50);

6 L2.rest.rest = L3;

L1

L2

1

13

3

4

CS 61B Fall 2023

1 Boxes and Pointers

1 IntList L1 = IntList.list(1, 2, 3);

2 IntList L2 = new IntList(4, L1.rest);

3 L2.rest.first = 13;

4 L1.rest.rest.rest = L2;

5 IntList L3 = IntList.list(50);

6 L2.rest.rest = L3;

L1

L3

L2

1

13

3

4

50

CS 61B Fall 2023

1 Boxes and Pointers

1 IntList L1 = IntList.list(1, 2, 3);

2 IntList L2 = new IntList(4, L1.rest);

3 L2.rest.first = 13;

4 L1.rest.rest.rest = L2;

5 IntList L3 = IntList.list(50);

6 L2.rest.rest = L3;

L1

L3

L2

1

13

3

4

50

CS 61B Fall 2023

2 Partition

Implement partition, which takes in an IntList lst and an integer k, and destructively partitions lst into k IntLists such that each list has the following properties:

• It is the same length as the other lists. You may assume it is evenly divisible.
• Its ordering is consistent with the ordering of lst.

​

These lists should be put in an array of length k, and this array should be returned.

​

For instance, if lst contains the elements 5, 4, 3, 2, 1, and k = 2, then a possible partition is putting elements [5, 3, 2] at index 0, and elements [4, 1] at index 1.

​

You may assume you have the access to the method reverse, which destructively re-

verses the ordering of a given IntList and returns a pointer to the reversed IntList. You may not create any IntList instances.

​

CS 61B Fall 2023

2 Partition

public static IntList[] partition(IntList lst, int k) {

IntList[] array = new IntList[k];

int index = 0;

IntList L = _____________________________________

while (L != null) {

_____________________________________________

_____________________________________________

_____________________________________________

_____________________________________________

_____________________________________________

_____________________________________________

_____________________________________________

}

return array;

}

​

CS 61B Fall 2023

2 Partition

public static IntList[] partition(IntList lst, int k) {

IntList[] array = new IntList[k];

int index = 0;

IntList L = reverse(lst);

while (L != null) {

_____________________________________________

_____________________________________________

_____________________________________________

_____________________________________________

_____________________________________________

_____________________________________________

}

return array;

}

CS 61B Fall 2023

2 Partition

public static IntList[] partition(IntList lst, int k) {

IntList[] array = new IntList[k];

int index = 0;

IntList L = reverse(lst);

while (L != null) {

IntList prevAtIndex = array[index];

_____________________________________________

_____________________________________________

_____________________________________________

_____________________________________________

_____________________________________________

}

return array;

}

CS 61B Fall 2023

2 Partition

public static IntList[] partition(IntList lst, int k) {

IntList[] array = new IntList[k];

int index = 0;

IntList L = reverse(lst);

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = L.rest;

_____________________________________________

_____________________________________________

_____________________________________________

_____________________________________________

}

return array;

}

CS 61B Fall 2023

2 Partition

public static IntList[] partition(IntList lst, int k) {

IntList[] array = new IntList[k];

int index = 0;

IntList L = reverse(lst);

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = L.rest;

array[index] = L;

_____________________________________________

_____________________________________________

_____________________________________________

}

return array;

}

CS 61B Fall 2023

2 Partition

public static IntList[] partition(IntList lst, int k) {

IntList[] array = new IntList[k];

int index = 0;

IntList L = reverse(lst);

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = L.rest;

array[index] = L;

array[index].rest = prevAtIndex;

_____________________________________________

_____________________________________________

}

return array;

}

CS 61B Fall 2023

2 Partition

public static IntList[] partition(IntList lst, int k) {

IntList[] array = new IntList[k];

int index = 0;

IntList L = reverse(lst);

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = L.rest;

array[index] = L;

array[index].rest = prevAtIndex;

L = next;

_____________________________________________

}

return array;

}

CS 61B Fall 2023

2 Partition

public static IntList[] partition(IntList lst, int k) {

IntList[] array = new IntList[k];

int index = 0;

IntList L = reverse(lst);

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = L.rest;

array[index] = L;

array[index].rest = prevAtIndex;

L = next;

index = (index + 1) % array.length;

}

return array;

}

CS 61B Fall 2023

3 Remove Duplicates

Using the simplified DLList class, implement the removeDuplicates method.

​

removeDuplicates should remove all duplicate items from the DLList. For example, if our initial list [8, 4, 4, 6, 4, 10, 12, 12], our final list should be [8, 4, 6, 10, 12]. You may not assume that duplicate items are grouped together, or that the list is sorted!

​

​

​

public class DLList {

Node sentinel;

​

public DLList() {

// ...

}

​

public class Node {

int item;

Node prev;

Node next;

}

CS 61B Fall 2023

3 Remove Duplicates

Node ref = _________________________________________________________________;

Node checker;

while (_________________________________________________________________) {

checker = _________________________________________________________________;

while (_________________________________________________________________) {

if (_________________________________________________________________) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

_________________________________________________________________;

_________________________________________________________________;

_________________________________________________________________;

checker = _______________________________________________________;

} else {

checker = _______________________________________________________;

}

}

ref = _________________________________________________________________;

}

CS 61B Fall 2023

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (_________________________________________________________________) {

checker = _________________________________________________________________;

while (_________________________________________________________________) {

if (_________________________________________________________________) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

_________________________________________________________________;

_________________________________________________________________;

checker = _______________________________________________________;

} else {

checker = _______________________________________________________;

}

}

ref = _________________________________________________________________;

}

CS 61B Fall 2023

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (ref != sentinel) {

checker = _________________________________________________________________;

while (_________________________________________________________________) {

if (_________________________________________________________________) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

_________________________________________________________________;

_________________________________________________________________;

checker = _______________________________________________________;

} else {

checker = _______________________________________________________;

}

}

ref = _________________________________________________________________;

}

CS 61B Fall 2023

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (ref != sentinel) {

checker = ref.next;

while (_________________________________________________________________) {

if (_________________________________________________________________) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

_________________________________________________________________;

_________________________________________________________________;

checker = _______________________________________________________;

} else {

checker = _______________________________________________________;

}

}

ref = _________________________________________________________________;

}

CS 61B Fall 2023

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (ref != sentinel) {

checker = ref.next;

while (checker != sentinel) {

if (_________________________________________________________________) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

_________________________________________________________________;

_________________________________________________________________;

checker = _______________________________________________________;

} else {

checker = _______________________________________________________;

}

}

ref = _________________________________________________________________;

}

CS 61B Fall 2023

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (ref != sentinel) {

checker = ref.next;

while (checker != sentinel) {

if (ref.item == checker.item) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

_________________________________________________________________;

_________________________________________________________________;

checker = _______________________________________________________;

} else {

checker = _______________________________________________________;

}

}

ref = _________________________________________________________________;

}

CS 61B Fall 2023

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (ref != sentinel) {

checker = ref.next;

while (checker != sentinel) {

if (ref.item == checker.item) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

checkerPrev.next = checker.next;

_________________________________________________________________;

checker = _______________________________________________________;

} else {

checker = _______________________________________________________;

}

}

ref = _________________________________________________________________;

}

CS 61B Fall 2023

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (ref != sentinel) {

checker = ref.next;

while (checker != sentinel) {

if (ref.item == checker.item) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

checkerPrev.next = checker.next;

checkerNext.prev = checker.prev;

checker = _______________________________________________________;

} else {

checker = _______________________________________________________;

}

}

ref = _________________________________________________________________;

}

CS 61B Fall 2023

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (ref != sentinel) {

checker = ref.next;

while (checker != sentinel) {

if (ref.item == checker.item) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

checkerPrev.next = checker.next;

checkerNext.prev = checker.prev;

checker = checkerNext;

} else {

checker = _______________________________________________________;

}

}

ref = _________________________________________________________________;

}

CS 61B Fall 2023

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (ref != sentinel) {

checker = ref.next;

while (checker != sentinel) {

if (ref.item == checker.item) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

checkerPrev.next = checker.next;

checkerNext.prev = checker.prev;

checker = checkerNext;

} else {

checker = checker.next;

}

}

ref = _________________________________________________________________;

}

CS 61B Fall 2023

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (ref != sentinel) {

checker = ref.next;

while (checker != sentinel) {

if (ref.item == checker.item) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

checkerPrev.next = checker.next;

checkerNext.prev = checker.prev;

checker = checkerNext;

} else {

checker = checker.next;

}

}

ref = ref.next;

}

CS 61B Fall 2023