1 of 94

Arrays, Linked Lists

Exam-Level 02

CS61B Fall 2024

2 of 94

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

CS61B Fall 2024

3 of 94

Announcements

Weekly Survey 3 - due this Wednesday 9/11
Lab 3 - due this Friday 9/13
Proj 1A - due this Friday 9/13
Project Party Wednesday 9/11
Carefully read the OH guidelines if you attend

CS61B Fall 2024

4 of 94

Content Review

CS61B Fall 2024

5 of 94

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.

CS61B Fall 2024

6 of 94

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.

CS61B Fall 2024

7 of 94

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 ==

CS61B Fall 2024

8 of 94

A Quick Example

int x = 5;

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

1

2

3

5

x

arr

CS61B Fall 2024

9 of 94

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

CS61B Fall 2024

10 of 94

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.

CS61B Fall 2024

11 of 94

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?

CS61B Fall 2024

12 of 94

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)

CS61B Fall 2024

13 of 94

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

CS61B Fall 2024

14 of 94

Worksheet

CS61B Fall 2024

15 of 94

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;

CS61B Fall 2024

16 of 94

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

null

CS61B Fall 2024

17 of 94

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

null

4

CS61B Fall 2024

18 of 94

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

null

4

CS61B Fall 2024

19 of 94

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

CS61B Fall 2024

20 of 94

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

null

CS61B Fall 2024

21 of 94

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

null

CS61B Fall 2024

22 of 94

2 Interweave

Implement interweave, which takes in an IntList lst and an integer k, and destructively interweaves 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=[6, 5, 4, 3, 2, 1], and k=2, then you return an array of 2 linked lists, the first one [6, 4, 2], and the second one [5, 3, 1].

Destructively: instead of creating new IntList instances, you should focus on modifying the pointers in the existing IntList, lst.

CS61B Fall 2024

23 of 94

2 Interweave

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

IntList[] array = new IntList[k];

int index = k - 1;

IntList L = reverse(lst); // Assume reverse is implemented correctly

while (___________________) {

IntList prevAtIndex = ___________________;

IntList next = ___________________;

__________________________________;

L = ___________________;

index -= 1;

if (______________________) {

_______________________;

}

return array;

}

CS61B Fall 2024

24 of 94

2 Interweave

6

5

4

3

2

1

null

0

1

lst

CS61B Fall 2024

25 of 94

2 Interweave

1

2

3

4

5

6

null

0

1

L

CS61B Fall 2024

26 of 94

2 Interweave

1

2

3

4

5

6

null

0

1

L

k=1

CS61B Fall 2024

27 of 94

2 Interweave

1

2

3

4

5

6

null

0

1

L

k=1

prevAtIndex: null

CS61B Fall 2024

28 of 94

2 Interweave

1

2

3

4

5

6

null

0

1

L

k=1

CS61B Fall 2024

29 of 94

2 Interweave

1

2

3

4

5

6

null

0

1

L

k=1

CS61B Fall 2024

30 of 94

2 Interweave

1

2

3

4

5

6

null

0

1

L

k=1

null

CS61B Fall 2024

31 of 94

2 Interweave

1

2

3

4

5

6

null

0

1

L

k=1

null

CS61B Fall 2024

32 of 94

2 Interweave

1

2

3

4

5

6

null

0

1

L

k=0

null

CS61B Fall 2024

33 of 94

2 Interweave

1

2

3

4

5

6

null

0

1

L

k=0

null

CS61B Fall 2024

34 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

k=0

null

CS61B Fall 2024

35 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

k=0

null

CS61B Fall 2024

36 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

k=1

null

CS61B Fall 2024

37 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

k=1

null

CS61B Fall 2024

38 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

k=1

null

CS61B Fall 2024

39 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

k=1

null

CS61B Fall 2024

40 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

k=1

null

CS61B Fall 2024

41 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

k=1

null

CS61B Fall 2024

42 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

k=0

null

CS61B Fall 2024

43 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

null

k=0

CS61B Fall 2024

44 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

null

k=0

CS61B Fall 2024

45 of 94

2 Interweave

1

2

3

4

5

6

0

1

L

null

k=0

CS61B Fall 2024

46 of 94

2 Interweave

1

2

3

4

6

0

1

L

k=1

null

5

CS61B Fall 2024

47 of 94

2 Interweave

1

2

3

4

6

0

1

L

k=0

null

5

CS61B Fall 2024

48 of 94

2 Interweave

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

IntList[] array = new IntList[k];

int index = k - 1;

IntList L = reverse(lst); // Assume reverse is implemented correctly

while (L != null) {

IntList prevAtIndex = ___________________;

IntList next = ___________________;

__________________________________;

L = ___________________;

index -= 1;

if (______________________) {

_______________________;

}

return array;

}

CS61B Fall 2024

49 of 94

2 Interweave

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

IntList[] array = new IntList[k];

int index = k - 1;

IntList L = reverse(lst); // Assume reverse is implemented correctly

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = ___________________;

__________________________________;

L = ___________________;

index -= 1;

if (______________________) {

_______________________;

}

return array;

}

CS61B Fall 2024

50 of 94

2 Interweave

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

IntList[] array = new IntList[k];

int index = k - 1;

IntList L = reverse(lst); // Assume reverse is implemented correctly

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = L.rest;

__________________________________;

L = ___________________;

index -= 1;

if (______________________) {

_______________________;

}

return array;

}

CS61B Fall 2024

51 of 94

2 Interweave

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

IntList[] array = new IntList[k];

int index = k - 1;

IntList L = reverse(lst); // Assume reverse is implemented correctly

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = L.rest;

array[index] = L;

__________________________________;

L = ___________________;

index -= 1;

if (______________________) {

_______________________;

}

return array;

}

CS61B Fall 2024

52 of 94

2 Interweave

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

IntList[] array = new IntList[k];

int index = k - 1;

IntList L = reverse(lst); // Assume reverse is implemented correctly

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = L.rest;

array[index] = L;

array[index].rest = prevAtIndex;

L = ___________________;

index -= 1;

if (______________________) {

_______________________;

}

return array;

}

CS61B Fall 2024

53 of 94

2 Interweave

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

IntList[] array = new IntList[k];

int index = k - 1;

IntList L = reverse(lst); // Assume reverse is implemented correctly

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = L.rest;

array[index] = L;

array[index].rest = prevAtIndex;

L = next;

index -= 1;

if (______________________) {

_______________________;

}

return array;

}

CS61B Fall 2024

54 of 94

2 Interweave

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

IntList[] array = new IntList[k];

int index = k - 1;

IntList L = reverse(lst); // Assume reverse is implemented correctly

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = L.rest;

array[index] = L;

array[index].rest = prevAtIndex;

L = next;

index -= 1;

if (index < 0) {

_______________________;

}

return array;

}

CS61B Fall 2024

55 of 94

2 Interweave

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

IntList[] array = new IntList[k];

int index = k - 1;

IntList L = reverse(lst); // Assume reverse is implemented correctly

while (L != null) {

IntList prevAtIndex = array[index];

IntList next = L.rest;

array[index] = L;

array[index].rest = prevAtIndex;

L = next;

index -= 1;

if (index < 0) {

index = k - 1;

}

return array;

}

CS61B Fall 2024

56 of 94

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;

}

CS61B Fall 2024

57 of 94

3 Remove Duplicates

Node ref = _________________________________________________________________;

Node checker;

while (_________________________________________________________________) {

checker = _________________________________________________________________;

while (_________________________________________________________________) {

if (_________________________________________________________________) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

_________________________________________________________________;

}

checker = _______________________________________________________;

}

ref = _________________________________________________________________;

}

CS61B Fall 2024

58 of 94

3 Remove Duplicates

8

4

6

4

10

12

sentinel

CS61B Fall 2024

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

73 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

74 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

75 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

76 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

77 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

78 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

79 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

80 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

81 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

82 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

83 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

84 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

85 of 94

3 Remove Duplicates

8

4

6

10

12

sentinel

ref

checker

CS61B Fall 2024

86 of 94

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (_________________________________________________________________) {

checker = _________________________________________________________________;

while (_________________________________________________________________) {

if (_________________________________________________________________) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

_________________________________________________________________;

}

checker = _______________________________________________________;

}

ref = _________________________________________________________________;

}

CS61B Fall 2024

87 of 94

3 Remove Duplicates

Node ref = sentinel.next;

Node checker;

while (ref != sentinel) {

checker = _________________________________________________________________;

while (_________________________________________________________________) {

if (_________________________________________________________________) {

Node checkerPrev = checker.prev;

Node checkerNext = checker.next;

_________________________________________________________________;

}

checker = _______________________________________________________;

}

ref = _________________________________________________________________;

}

CS61B Fall 2024

88 of 94

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 = _______________________________________________________;

}

ref = _________________________________________________________________;

}

CS61B Fall 2024

89 of 94

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 = _______________________________________________________;

}

ref = _________________________________________________________________;

}

CS61B Fall 2024

90 of 94

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 = _______________________________________________________;

}

ref = _________________________________________________________________;

}

CS61B Fall 2024

91 of 94

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 = _______________________________________________________;

}

ref = _________________________________________________________________;

}

CS61B Fall 2024

92 of 94

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 = _______________________________________________________;

}

ref = _________________________________________________________________;

}

CS61B Fall 2024

93 of 94

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 = checker.next;

}

ref = _________________________________________________________________;

}

CS61B Fall 2024

94 of 94

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 = checker.next;

}

ref = ref.next;

}

CS61B Fall 2024