Midterm Review
1
Lecture 12
CS 61B, Spring 2025 @ UC Berkeley
Review Lecture Topics Requested
2
Brief Review
Lecture 12, CS61B, Spring 2025
3
Topic Review
Let’s do a brief review of the topics you requested from the class.
4
Abstract Data Types That We Built
Abstract data types are defined by their operations.
5
List61B
AList
SLList
Deque61B
Array
Deque61B
LinkedList
Deque61B
Abstract Data Types in Java
Java has its own built-in list type.
6
List61B
AList
SLList
Deque61B
Array
Deque61B
LinkedList
Deque61B
List
ArrayList
LinkedList
Interface Hierarchies
Interfaces can be part of a hierarchy, e.g. Deque61B<T> extends Iterable<T>
7
Deque61B
Array
Deque61B
LinkedList
Deque61B
List
ArrayList
LinkedList
Collection
Iterable
Iterable
Extends - Deque61Bs must have an iterator method
implements
implements
Deque61B does not need to override Iterable’s methods†
Default Methods
If there are methods that have natural default implementations in terms of other methods, we can write a default method. Example from List.java (https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/List.java):
8
Iterables
An iterable can be iterated over using a for-each loop.
9
Set<Integer> javaset = new HashSet<>();
javaset.add(5);
javaset.add(23);
javaset.add(42);
for (int i : javaset) {
System.out.println(i);
}
Set
HashSet
Collection
Iterable
The Iterable Interface
An Iterable can be iterated over using a for-each loop.
The Iterable<T> interface:
The Iterator<T> interface:
10
Set
HashSet
Collection
Iterable
Iterator
Classes Can Implement Multiple Interfaces
11
public class SimpleArrayContainer<T> implements Iterable<T>, Iterator<T> {
private final T[] items;
private int currentIndex = 0;
public SimpleArrayContainer(T[] items) {
this.items = items;
}
public Iterator<T> iterator() {
// Reset the position each time iteration starts
currentIndex = 0;
return this;
}
public boolean hasNext() {
return currentIndex < items.length;
}
public T next() {
T itemToReturn = items[currentIndex];
currentIndex += 1;
return itemToReturn;
}
}
SimpleArrayContainer
Iterable
Iterator
Comparables and Comparators
The Comparable<T> interface is used to compare this to another thing:
The Comparator<T> interface:
Question: Since we’re comparing two other objects (and not to this), why isn’t the compare method static?
12
How do we specify generics?
Specify: If we mean pick a specific type, we ONLY do this for classes which have a <Blerf> at the top, example:�
Declaration:
public class OurList61B<Blerf> {
}
Specification (a.k.a. usage):
OurList61B<String> alist = new OurList61B<>();
13
Linked List Implementations
Linked list based data structures are recursive data structures.
So far, we’ve seen singly linked and doubly linked lists.
14
sentinel
3
2
size
9
??
next
item
prev
addLast()
getLast()
size()
removeLast()
Array Based Implementations
Array data structures are non-recursive data structures.
15
5
3
1
7
0
0
0
0
0
0
0
...
0 1 2 3 4 5 6 7 97 98 99
addLast()
getLast()
get(int i)
removeLast()
items
4
size
Syntax: For Inheritance
In Java, an interface enumerates all methods that a subclass must override.
16
List
ArrayList
Terminology
A member of a class is:
Subclasses inherit all members of their superclasses.
17
Syntax: Static vs. Non-Static
A static member of class X is associated with class X, rather than an instance of class X. We can think of this as “there is no instance of X called this”.
18
public class Dog {
public int size;
public static void bark() {
if (size > 0) {
System.out.println("bark");
}
}
}
Since we don’t specify where size comes from, Java implicitly checks to see if this.size exists. It does not, there is no this.
Syntax: Static vs. Non-Static
A static member of class X is associated with class X, rather than an instance of class X. We can think of this as “there is no instance of X called this”.
19
public class Dog {
public static int size;
public static void bark() {
if (size > 0) {
System.out.println("bark");
}
}
}
Question: If this variable was static, would this work? Java says “i have no local variable called size”, but is there a “this.size?”, no ok is there a “Dog.size”? Yes
IT WORKS, but you should write as Dog.size
Syntax: Static vs. Non-Static
A static member of class X is associated with class X, rather than an instance of class X. We can think of this as “there is no instance of X called this”.
20
public class Dog {
public static int size;
public void bark() {
if (size > 0) {
System.out.println("bark");
}
}
}
Question: If this variable was static, would this work? Java says “i have no local variable called size”, but is there a “this.size?”, no ok is there a “Dog.size”? yes
IT WORKS, but you should write as Dog.size
Syntax: Static vs. Non-Static
A static member of class X is associated with class X, rather than an instance of class X. We can think of this as “there is no instance of X called this”.
21
Syntax: Static vs. Non-Static
A static member of class X is associated with class X, rather than an instance of class X. We can think of this as “there is no instance of X called this”.
Question:
22
If you wanted ot make ArrayDequeIterator static, could you pass in the specific instance variables it needs to know?
If we are working in a nested class, say ArrayDequeIterator, and we use “this”, how do we know if this refers to the iterator object or the ArrayDeque enclosing it.
23
THE MOST IMPORTANT THING ABOUT ALL THIS
A static nested class cannot access the instance variables of an instance of the outer class.
Aret here weird edge cases and crazy things we might do?
24
Compilation vs. Interpretation
In Java, compilation and interpretation are two separate steps.
Hello.java
Hello.class
javac
java
stuff
happens
Compiler
Interpreter
Why make a class file at all?
You don’t see this process in 61B because IntellIJ compiles in the background secretly.
Java: Compilation vs. Runtime
Java’s type checking is done before you run the code. Will not compile otherwise.
26
Java: Compilation vs. Runtime Errors
Java’s type checking is done before you run the code. Will not compile otherwise.
Runtime errors that are (usually) impossible in Java:
27
Things Not In Scope
These things are not in scope, but might appear on old exams:
28
Default methods in interfaces - can you use this keyword?
Implements vs. extends
29
Is there a difference between
30
Whyat’s up with
public static <T> T max(Iterable<T> iterable, Comparator<T> comp)
We sometimes want static methods that can take any type.
31
Solving Some Problems
Lecture 12, CS61B, Spring 2025
32
Exam Problems
I’ll solve some problems cold from here. Hopefully seeing my thinking process is useful.
33