CS61B SP24 Notes (Consistent Update)

Posted on 2024-03-15

English notes for CS61B Spring 2024.

Preface

As a student who is not majoring in CS and hasnt systematically learned CS tech, my technical knowledge is limited to some basic programming and data structures. To secure a software-dev job, I need to deepen my understanding of CS Knowledges, so I decided to take the CS61B course to learn more, Taking notes in English is a good way.

The CS61B SP24 course is taught by Justin Yokota and Peyrin Kao. They use Java as the main lang. Since I have never learned Java before (although I once developed a Minecraft plugin using Java when I was in primary, but I forgot all = =), I will take this course as an opportunity to learn it.

Skipped Lec 1. Intro

Week 1

Lec 1. Defining and Using Classes

1.1 Defining Classes

Class: a blueprint for creating objects.
Object: an instance of a class.
Instance Variables: data that is unique to each object.
Methods: functions that operate on the object’s data.


public class Dog {
    public int weightInPounds; // instance variable
    public Dog(int w) { 
        // constructor
        weightInPounds = w;
    }
    // instance method
    public void makeNoise() { 
        if (weightInPounds < 10)
            System.out.println("Wang!");
        else
            System.out.println("Meow!");
    }
}

In the above code, we define a class Dog with an instance variable weightInPounds, a constructor Dog(int w), and a method makeNoise().

We can create different Dog objects with different weights and call the makeNoise() method on them.

// Object creation
Dog wangwang = new Dog(5);
Dog lili = new Dog(15);

// Method call
wangwang.makeNoise(); // Wang!
lili.makeNoise(); // Meow!

the new keyword is similar to C#, which creates a new object of the class.

1.2 Static Methods

static methods that do not require an object to be called. In other words, they are not associated with any instance of the class. It’s ‘general’ and can be called directly from the class.

e.g

public class Dog {
    public static void bark() {
        System.out.println("Wang!");
    }
}

Then we can call the bark() method directly from the class. No need to create an object.
It’s about all dog objects to bark, not a specific dog object.

1	Dog.bark(); // Wang!

Sometimes, classes may have a mix of static and non-static methods.

e.g

public static Dog largerDog(Dog dog1, Dog dog2){
    if(dog1.weightInPounds > dog2.weightInPounds)
        return dog1;
    else
        return dog2;
}

public Dog largerDog(Dog dog2){
    if(this.weightInPounds > dog2.weightInPounds)
        return this;
    else
        return dog2;
}
...

/* Call the static method */
Dog dog1 = new Dog(5);
Dog dog2 = new Dog(15);
Dog larger = Dog.largerDog(dog1, dog2);
larger.makeNoise(); // This will print the noise of the larger dog.

/* Call the instance method */
Dog d3 = new Dog(25);
larger = d1.largerDog(d3);
larger.makeNoise(); // This will print the noise of the d3 dog

Yes! the instance method meaning that it’s about the specific object, so we use this to refer to the object itself.

So the code larger = d1.largerDog(d3); means that we compare the weight of d1 and d3, and then return the larger one.

Static Variables: variables that are shared among all instances of a class. They are declared with the static keyword.

E.g, all dogs have the same species name.

1
2
3

public class Dog {
    public static String species = "Canis lupus";
}

Then we can access the species variable directly from the class.

1	System.out.println(Dog.species); // Canis lupus

1.3 Review

In this lecture, we learned how to define classes in Java, including:

Instance Variables,
Constructors
Methods

We also learned about Static Methods and Variables.

Generally speaking, the Static keyword is used to define a class-level variable or method. It means that the variable or method is shared among all instances of the class.

Non-Static Methods and Variables are associated with a specific instance of the class. They are used to operate on the object’s data.

Week 2

Lec 2. Lists I: References, Recursion, and Lists

2.1 References

Let’s review the Dog class we defined in the previous lecture.

In DogLauncher, we create a Dog object by using the new keyword.

1	Dog wangwang = new Dog(15);

The Dog object is stored in memory, and the variable wangwang stores the memory address of the object.

It means, wangwang is a reference to the Dog object, not the object itself. It just points to the object. Yes , it’s like a pointer in CPP.

We call the Reference Type in Java, which is different from the Primitive Type.

We may list all the primitive types in Java:

Primitive Type	Size(bytes)	Range
byte	1	-128 to 127
short	2	-32,768 to 32,767
int	4	-2^31 to 2^31-1
long	8	-2^63 to 2^63-1
float	4	1.4E-45 to 3.4E38
double	8	4.9E-324 to 1.8E308
char	2	0 to 65,535
boolean	1	true or false

and the reference types:

All classes
Arrays
Interfaces
Strings
Enum
Null
All other objects

2.2 Recursion

I’m skipping this part because am already familiar with recursion.

2.3 Lists

2.3.1 Create a list

Establish a new class IntList to represent a list of integers.

public class IntList{
    public int first;
    public IntList rest;
}

In the IntList class, we define two instance variables first and rest. first stores the first element of the list, and rest stores the rest of the list.

We can create a list of integers like this:

1
2
3

IntList L = new IntList();
L.first = 5;
L.rest = null;

Hey, you know what, we can also let the L.rest point to another IntList object.

1
2
3

L.rest = new IntList();
L.rest.first = 10;
L.rest.rest = null;

Using the visualizer tools can clearly show the structure of the list.

if you like, you can create any length of the list by using the above method.
but it’s not a good way to create a list, so we can use the constructor to create a list.

public class IntList{
    public int first;
    public IntList rest;

    public IntList(int f, IntList r){
        first = f;
        rest = r;
    }
}

Then we can create a list like this, the result is the same as the previous one.

1
2
3

IntList L = new IntList(5, null);
L = new IntList(10, L);
L = new IntList(15, L);

2.3.2 Get Lists Length

We can define a recursion size() method get the length of list.

public int size(){
    if(rest == null)
        return 1;
    else
        return 1 + rest.size();
}

2.3.3 Get the ith element of the list

public int get(int i){
    if(i == 0)
        return first;
    else
        return rest.get(i - 1);
}

2.4 Review

In this lecture, we learned about:

References Types
Recursion
Lists

References Types are used to store the memory address of an object. They are different from Primitive Types. It’s like a pointer in C++.

Recursion is a technique in which a function calls itself. It’s a powerful tool in programming.

Lists are a data structure that stores a collection of elements. We can use the IntList class to represent a list of integers, in this class, we define two instance variables first and rest to store the first element and the rest of the list.

Lec 3. Lists II: SLLists, Nested Classes, and Sentinel Nodes

3.1 SLLists

SLLists means Singly-Linked-List.

ofc we can use the previous IntList to create a list, but it’s naked, and it’s not convenient to use, so we can create a new class SLList to represent a list of integers.

Comparing to the IntList, our SLList class act as a middle man between the user and raw data structure.

public class SLList
{
    private static class IntNode
    {
        public int item;
        public IntNode next;

        public IntNode(int i, IntNode n)
        {
            item = i;
            next = n;
        }
    }
}

In the SLList class, we define a nested class IntNode to represent the node of the list. It’s a good way to encapsulate the node class in the list class.

Then we can create a list like this:

1	SLList L = new SLList(5);

Did you see, its more convenient than the previous code L = new IntList(5, null);

and also, we can write more methods in the SLList class to operate the list, such as addFirst(), size(), get(), addLast(), etc.

e.g

public void addFirst(int x)
{
    sentinel.next = new IntNode(x, sentinel.next);
    size += 1;
}

But! the method is has safety issues:

node first is naked, it’s not safe.
if the lists are empty, get() method will throw an error.

Fix:

change the public to private to make the IntNode class private.

public class SLList
{
    private static class IntNode
    {
        public int item;
        public IntNode next;

        public IntNode(int i, IntNode n)
        {
            item = i;
            next = n;
        }
    }
}

public and private method just like Car analogy,

public method is pedals and steering wheel, which is used to operate the car.
private method like the engine, our drive doesn’t need to know how the engine works, just need to know how to op the car. (from the outside)

3.2 Nested Classes

Nested classes are classes defined within another class. They are used to logically group classes that are only used in one place.

There are four types of nested classes in Java:

Static Nested Classes: a static class that is defined at the same level as the instance variables of the outer class.
Non-static Nested Classes (Inner Classes): a class that is defined at the same level as the instance variables of the outer class.
Local Classes: a class that is defined within a block of code.
Anonymous Classes: a class that is defined without a name.

In the previous example, we can move the IntNode class into the SLList class as a static nested class.

It’s more convenient, dosent it?

3.3 Sentinel Nodes

Hey, if our list first item is null, then we use the get() , what will happen?

Sure, it will throw an error, we can add if statement to check if the list is empty, but it’s not a good way.

We can make sure that the list first item is always not null by using the sentinel node.

Why call it sentinel node? because it’s like a sentinel, it’s always there, but it’s not a real element of the list.He is your faithful guard, always protecting the list from being empty.

public SLList(int x){
    /* sentinel node can be any value, but it's better to be a special value. */
    sentinel = new IntNode(999, null);
    sentinel.next = new IntNode(x,null);
}

/* Add item x to the front of List*/
public void addFirst(int x){
    sentinel = new IntNode(x, sentinel);
}

/* Get the first item of the list */
public int getFirst(){
    return sentinel.next.item;
}

/* Add item x to the end of the list */
public void addLast(int x){
    IntNode p = sentinel;
    while(p.next != null){
        p = p.next;
    }
    p.next = new IntNode(x, null);
}

Like this (image from the lecture slides)

3.4 Review

In this lecture, we learned about:

SLLists: a data structure that stores a collection of elements. We can use the SLList class to represent a list of integers. In this class, we define a nested class IntNode to represent the node of the list. It’s a good way to encapsulate the node class in the list class.
Nested Classes: classes defined within another class. They are used to logically group classes that are only used in one place.
Sentinel Nodes: a special node that is always present in the list. It’s used to prevent the list from being empty. The sentinel node is like a guard that protects the list from being empty ^_^ (My faithful guard)

Lec 4. Lists III: DLLists and Arrays

4.1 DLLists

Let’s quick review the SLList class we learned in the previous lecture.

SLList is a single linked list, which means that each node only points to the next node, and we also have the sentinel node to prevent the list from being empty. It’s good.

But, hey, if we want to add a new node to the end of the list, we need to traverse the whole list to find the last node, it’s not efficient. the pointer from the sentinel node go go go until he reaches the end of the list. It’s not good enough. btw Time complexity is O(n).

So what can we do to solve this problem?

We can use the Double Linked List, which means that each node points to the next node and the previous node. It’s like a two-way street, you can go forward and backward.

e.g we have a list like this:

$$ \text{sentinel} \rightarrow 3 \rightarrow 9 $$

if we want to ask 9: “hey what is your previous guy?”
9 use his prev pointer to find and say “oh, it’s 3”.

$$ \text{sentinel} \leftrightarrows 3 \leftrightarrows 9$$

But, considering the list, sometimes the list is null or sometimes is not null, there’s two different cases, you need to write two cases to handle, Its annoying and complicated.

One solution: Two sentinel nodes

Structure like this:

We can set two nodes in the list, one is sentFront, and the other is sentBack. They are always there, making sure that the list is not empty. they also not real elements of the list.

Write the code:

public class DLList
{
    private static class IntNode
    {
        public int item;
        public IntNode prev;
        public IntNode next;

        public IntNode(int i, IntNode p, IntNode n)
        {
            item = i;
            prev = p;
            next = n;
        }
    }

    private IntNode sentFront;
    private IntNode sentBack;
    private int size;

    public DLList()
    {
        sentFront = new IntNode(999, null, null);
        sentBack = new IntNode(888, sentFront, null);
        sentFront.next = sentBack;
        size = 0;
    }
}

Another solution: Circular Sentinel Node

Structure like this:

If the list is empty, the sentinel node points to itself, and the Sentinel’s previous item is itself.

It’s kind of like the world is round, you start here and start walking east or west whatever, you will eventually come back to the starting point. Amazing!

We can modify our code like this:

public DLList()
{
    sentinel = new IntNode(999, null, null);
    sentinel.prev = sentinel;
    sentinel.next = sentinel;
}

Then we can write removeLast() method like this:

public void removeLast()
{
    sentinel.prev = sentinel.prev.prev;
    sentinel.prev.next = sentinel;
    size -= 1;
}

4.2 Generic Types

Review our DLList class, we can see that the item is an integer, but what if we want to store other types of data, such as String, Double, etc.

One solution is copy copy the class again and again, and change the int to String, Double, etc. It’s ugly and dizzy!

We can use the Generic Types to solve this problem.

Define a generic type Item in the class declaration

public class DList<Pineapple>
{
    private static class IntNode
    {
        public Pineapple item;
        public IntNode prev;
        public IntNode next;

        public IntNode(Pineapple i, IntNode p, IntNode n)
        {
            item = i;
            prev = p;
            next = n;
        }
    }
}

Pineapple is a placeholder, it can be any type of data, such as String, Double, etc.

Then we can create a DLList object like this:

1 2	DLList<String> MyList = new DLList<String>(); MyList.addFirst("Hello");

4.3 Arrays

I quickly read this section because I am already quite familiar with arrays in C++, It’s such a basic data structure.

4.4 Review

In this lecture, we learned about:

DLLists: a data structure that stores a collection of elements. We can use the DLList class to represent a list of integers. In this class, we define a nested class IntNode to represent the node of the list. We can use two sentinel nodes or a circular sentinel node to prevent the list from being empty.
Generic Types: a way to create classes that can work with different types of data. We can use the placeholder <Item> to define a generic type in the class declaration. It’s a good way to make the class more flexible and reusable.
Arrays

Week 3

Lec 5. Testing

5.1 Google Truth and Testing

Testing is an important part of software development. It helps us to ensure that our code works as expected and to catch bugs early.
In this lecture, we will learn about Google Truth, a testing framework that makes it easy to write tests in Java.

For example, we have a method max() that returns the maximum of two integers.
We specify that the return result of this function is as follows

If Number1 is greater than Number2, then the result should be Number1.
If Number1 and Number2 are equal, then the result should be any of them.
If Number1 and Number2 are both null, then the result should be null.

Write the test code using Google Truth:

import static com.google.common.truth.Truth.assertThat;

public class TestMax{
    @Test
    public static void testNumberMax(){
        assertThat(max(3, 5)).isEqualTo(5);
    }

    @Test
    public static void testNullMax(){
        assertThat(max(null, null)).isNull();
    }

    @Test
    public static void testEqualMax(){
        assertThat(max(3, 3)).isEqualTo(3);
    }
}

5.2 Review

In this lecture, we learned about:

Testing: an important part of software development. It helps us to ensure that our code works as expected and to catch bugs early.
Google Truth: a testing framework that makes it easy to write tests in Java. We can use the assertThat() method to specify the expected result of a function and compare it with the actual result.
Test Code: a code that tests the functionality of a function. We can write test code using Google Truth to verify that our code works as expected.
@Test Annotation: an annotation that marks a method as a test method. We can use the @Test annotation to indicate that a method is a test method.
Assertions: a statement that checks whether a condition is true. We can use assertions to verify that our code works as expected.

Lec 6. Lists IV: Lists and Arrays

6.1 AList

Use Array to implement the List!

Talk is cheap, show me the code!

public class AList{
    private int[] items;
    private int size;

    public AList(){
        items = new int[100];
        size = 0;
    }

    public void addLast(int x){
        if(size == items.length)
            resize(size + 1);
        items[size] = x;
        size += 1;
    }

    public int getLast(){
        return items[size - 1];
    }

    public int get(int i){
        return items[i];
    }

    public int size(){
        return size;
    }

    private void resize(int capacity){
        int[] a = new int[capacity];
        System.arraycopy(items, 0, a, 0, size);
        items = a;
    }
}

If we want, we can also let the AList class support the generic type.

1
2
3

public class Alist<Pineapple>{
    ...
}

6.2 Resizing Arrays

When the array is full, we need to resize the array to add a new element.
That’ may need to learn OS first, I have learned it before, so I skip this part.

Resize the array:

private void resize(int capacity){
    int[] a = new int[capacity];
    System.arraycopy(items, 0, a, 0, size);
    items = a;
}

6.3 Array vs. List

Array: a fixed-size data structure that stores a collection of elements. It has a constant time complexity for accessing elements, but a linear time complexity for adding or removing elements.
List: a dynamic-size data structure that stores a collection of elements. It has a linear time complexity for accessing elements, but a constant time complexity for adding or removing elements.
ArrayList: a resizable array that stores a collection of elements. It has a linear time complexity for accessing elements, but a constant time complexity for adding or removing elements.

My idea:

Using the ArrayList is better than using the Array or List, because it’s more flexible and convenient.

6.4 Review

In this lecture, we learned about:

AList: a data structure that stores a collection of elements using an array. We can use the AList class to represent a list of integers. In this class, we define an instance variable items to store the elements of the list and a method resize() to resize the array when it’s full.
Resizing Arrays: a technique that allows us to resize an array when it’s full. We can use the System.arraycopy() method to copy the elements of the old array to the new array.

And we also compared the Array and List. My preference is to use the ArrayList because it’s more flexible and convenient.

Lec 7. Inheritance I Interface and Implementation Inheritance

Basic of OOP, I already know it LOL, but every lang has its own syntax, so Let’s see how Java implements it.

7.1 Interface and Interface Inheritance

An interface is a reference type in Java. It is similar to a class, but it is a collection of abstract methods. It’s like a contract, it defines what a class can do, but not how it does it.

Define an interface:

public interface Animal{
    void eat();
    void sleep();
}

We don’t care how the eat() and sleep() methods are implemented, we just know that the Animal interface defines these two methods. We can use the implements keyword to implement the interface in a class. Then write specific methods in the interface class.

public class Dog implements Animal{
    public void eat(){
        System.out.println("Dog is eating");
    }

    public void sleep(){
        System.out.println("Dog is sleeping");
    }
}

Then we can create a Dog object and call the eat() and sleep() methods on it.

1
2
3

Dog dog = new Dog();
dog.eat(); // Dog is eating
dog.sleep(); // Dog is sleeping

Don’t you think it’s like the Abstract Class in C++ or C#? Yes, it’s similar ^_^…

Let’s review the AList and DLList class we learned in the previous lecture.
It’s obvious that AList and DList are both some kind of list, they have some common methods, such as addLast(), getLast(), get(), etc.
We can conclude that:

List is a hypernym of AList and DList.
AList and DLList can inherit the methods of List.

So we can define an interface List to represent the list, and then let the AList and DLList class implement the List interface. Don’t forget the generic type!

Define the List interface:

new*
public interface List<Item>{
    public void addFirst(Item x);
    public void addLast(Item x);
    public Item getLast();
    public Item get(int i);
    public int size();
}

7.1.1 Override Annotation

Okay, It’s time to achieve our new AList and DLList class.

Implement the List interface in the AList class:


public class Alist<Item> implements List<Item>{
    private Item[] items;
    private int size;

    public Alist(){
        /*size of 100*/
        items = (Item[]) new Object[100];
        size = 0;
    }

    @Override
    public void addLast(Item x){
        if(size == items.length)
            resize(size + 1);
        items[size] = x;
        size += 1;
    }
    ...
}

Did you notice the @Override annotation? It’s used to indicate that the method is overriding a method in the superclass or interface.
It actually runs good whatever you add it or not, but it’s a good habit to use it.

But, if you add @Override annotation in a method that doesn’t override a method in the superclass or interface, it will throw an error.

7.2 Implementation Inheritance

Quick review:

Interface Inheritance:
- Subclass inherits signatures, but NOT implementations.
- Subclass can implement multiple interfaces.

So what is Implementation Inheritance?

Implementation Inheritance:
- Subclass inherits implementations.
- Subclass can only extend one class.

Use the default method in the interface is a kind of Implementation Inheritance.

Example: the List interface has a default method print() that prints the elements of the list.

Define the List interface with a default method:

public interface List<Item>{
    ...
    default void print(){
        for(int i = 0; i < size(); i++){
            System.out.println(get(i));
        }
    }
}

Then we can call the print() method on the AList object.
Aha… general method, don’t you think it’s like the Virtual Method in C++?

1
2
3

AList<String> list = new AList<String>();
list.addLast("Hello");
list.print(); // Hello

But! the default method could not suit all the classes, so we can override the default method in the subclass. just like what we do in the previous… ehh, like the teacher said but you never listen to him. LOL

7.3 Review

In this lecture, we learned about:

Interface: a reference type in Java that is similar to a class, but it is a collection of abstract methods. We can use the implements keyword to implement an interface in a class.
Interface Inheritance: a way to define a relationship between interfaces. A subclass can inherit
Implementation Inheritance: a way to define a relationship between classes. A subclass can inherit implementations from a superclass. We can use the @Override annotation to indicate that a method is overriding a method in the superclass or interface.
Default Method: a method in an interface that provides a default implementation. We can use the default keyword to define a default method in an interface. A subclass can override the default method if needed.

What’s the difference between Interface Inheritance and Implementation Inheritance?
We can summarize it as follows:

Interface Inheritance: Subclass inherits signatures, but NOT implementations.
Implementation Inheritance: Subclass inherits implementations.

and remember, Implementation Inheritance is no safe enough

Lec 8. Inheritance II: Extends, Casting, and Higher-Order Functions

8.1 Extends

In the previous lecture, we learned about the inheritance relationship between interfaces. Now, let’s talk about the inheritance relationship between classes. Such as we have a Dog, our lovely dog Coco is inherited from the Dog class. He has the same properties and methods as the Dog Class. But he also has his own unique properties and methods. For example, he can rotate his head 360 degrees, but the most of Dog class can’t (maybe). How can we achieve our unique Coco the dog, the answer is using the extends keyword QwQ!

Our Dog class:

public class Dog{
    ...
}

Our lovely Coco:


public class Coco extends Dog{
    public void rotateHead(){
        System.out.println("Coco is rotating his head 360 degrees");
    }
}

8.2 Casting

Casting is a way to convert an object of one type to another type.

e.g:

1
2
3

double x = 3.14;
int y = (int)x;
/* x is converted to an int : 3 */

In Java, there are two types of casting:

Implicit Casting: automatically converts a smaller type to a larger type. It’s safe and doesn’t require an explicit cast.
Explicit Casting: manually converts a larger type to a smaller type. It’s not safe and requires an explicit cast.
Upcasting: casting a subclass to a superclass. It’s safe and doesn’t require an explicit cast.
Downcasting: casting a superclass to a subclass. It’s not safe and requires an explicit cast.

8.3 Higher-Order Functions

What is a higher-order function?
well, it’s a function that takes one or more functions as arguments or returns a function as its result. Did you think of the Callback function? YES! ITS THE SAME!

In Python, we can pass a function as an argument to another function. It’s a powerful feature of Python. like this:

def add(x, y):
    return x + y

def apply(func, x, y):
    return func(x, y)

result = apply(add, 3, 5)
print(result) # Result is 8

In Java, we can achieve the same thing by using the Functional Interface. ehh, like a operator overloading in C++.

Define a Functional Interface:

1
2
3

public interface IntUnaryFunction{
    int apply(int x);
}

Then we can pass the IntUnaryFunction interface as an argument to another function.

public class TenX implements IntUnaryFunction{
    public int apply(int x){
        return 10 * x;
    }
}

Then we can create a TenX object and pass it as an argument to the do_twice() function.

public static int do_twice(IntUnaryFunction f, int x){
    return f.apply(f.apply(x));
}
...
System.out.println(do_twice(new TenX(), 2)); // Result is 200

8.4 Review

In this lecture, we learned about:

Extends: a way to define a relationship between classes. A subclass can inherit properties and methods from a superclass. We can use the extends keyword to extend a class in Java.
Casting: a way to convert an object of one type to another type. There are two types of casting: implicit casting and explicit
Higher-Order Functions: a function that takes one or more functions as arguments or returns a function as its result. We can use the Functional Interface to achieve higher-order functions in Java.

Week 4

Lec 9. Inheritance III: Subtype Polymorphism, Comparators, Comparable

9.1 Polymorphism

What is Polymorphism?
Well, according to the definition, Polymorphism is the ability of an object to take on many forms. It’s a powerful feature of OOP.

For example, we want to compare two dogs by their weight. in HoF, we could do like this:

def print_larger(weight1, weight2, compare_func):
    if compare_func(weight1, weight2):
        return weight1
    else:
        return weight2

def print_larger(weight1, weight2):
    if weight1.larger_than(weight2):
        return weight1
    else:
        return weight2

Preface

Week 1

Lec 1. Defining and Using Classes

1.1 Defining Classes

1.2 Static Methods

1.3 Review

Week 2

Lec 2. Lists I: References, Recursion, and Lists

2.1 References

2.2 Recursion

2.3 Lists

2.3.1 Create a list

2.3.2 Get Lists Length

2.3.3 Get the ith element of the list

2.4 Review

Lec 3. Lists II: SLLists, Nested Classes, and Sentinel Nodes

3.1 SLLists

3.2 Nested Classes

3.3 Sentinel Nodes

3.4 Review

Lec 4. Lists III: DLLists and Arrays

4.1 DLLists

One solution: Two sentinel nodes

Another solution: Circular Sentinel Node

4.2 Generic Types

4.3 Arrays

4.4 Review

Week 3

Lec 5. Testing

5.1 Google Truth and Testing

5.2 Review

Lec 6. Lists IV: Lists and Arrays

6.1 AList

6.2 Resizing Arrays

6.3 Array vs. List

6.4 Review

Lec 7. Inheritance I Interface and Implementation Inheritance

7.1 Interface and Interface Inheritance

7.1.1 Override Annotation

7.2 Implementation Inheritance

7.3 Review

Lec 8. Inheritance II: Extends, Casting, and Higher-Order Functions

8.1 Extends

8.2 Casting

8.3 Higher-Order Functions

8.4 Review

Week 4

Lec 9. Inheritance III: Subtype Polymorphism, Comparators, Comparable

9.1 Polymorphism

Lec 10. Inheritance IV: Iterators, Object Methods

Week 5

Lec 11. Asymptotics I