Before You Begin

As usual, pull the skeleton code.

Learning Goals

In this lab, we’ll wrap up the Java-focused portion of the class. First, we will take a look at two fundamental parts of comparing objects, the .equals() method for equality, and the Comparator and .compareTo() method for ordering (you should already be familiar with .equals() but Comparator and .compareTo() will be new). Both techniques will be widely used in the remainder of the class. We will then discuss inheritance and its rules.

We will then finish up the last of our Java concepts by exploring the concept of delegation and different methods for how we can delegate work to other classes and methods. For our purposes, to delegate work means to pass it off to someone or something else.

In this section, we’ll first consider what happens when an error occurs, like an ArrayIndexOutOfBoundsException. Instead of crashing immediately and printing out a long stack trace, we’ll learn how we can hand over control of the program to the method which called us, allowing the programmer to handle the crash and take alternate action. The mechanism that enables this ability is called an exception.

An exception can be thrown—passed to another part of the program to handle—or caught—handled on its own. We’ll consider examples of each kind of use in the upcoming lab exercises.

Finally, we’ll see how to build iterators, objects that control iteration through the items in a collection via three methods: a constructor, hasNext (“Are there any more items left?”), and next (“Return the next item.”). Iterators and iterables are a core component of the Java standard library, and we’ll see how iterators, as a form of delegation, can be used to write better and more performant code.

Comparison

Read Chapter 4.3 from Max Function through Comparables to help motivate the problem we’re solving and the tools we’ll use along the way.

Remember casting is a bit of special syntax where you can tell the compiler that a specific expression has a specific compile-time type. If the maxDog method below returns an object of static type Dog, the code normally wouldn’t compile as Poodle is a subtype of Dog. Casting tells Java to treat the Dog as if it were a Poodle for the purposes of compilation because it’s possible that the Dog returned from maxDog could be a Poodle.

Poodle largerPoodle = (Poodle) maxDog(frank, frankJr);

While we haven’t explicitly learned about sorting yet, the idea of sorting should be intuitive enough. You have a list of things, and you want to put it in sorted order. While this makes sense immediately for things like ints, which we can compare with primitive operations like < and ==, this becomes less clear for general objects.

Take a look at the Java API for the Comparable<T> interface. A lot of things implement Comparable in the Java standard library, as comparing two of the same type of object is a very common idea.

The only method required by Comparable is compareTo(T o) which takes another object of the (same) type T and returns an int whose value represents whether this or o should come first. In order to sort a list in Java, most sorting algorithms will call compareTo and make pairwise comparisons to determine which object should come first, repeatedly, and swap elements until the entire list is sorted. (The hard part of sorting, then, is to determine which compareTo ‘questions’ are necessary to ask!)

Here are a few key details from compareTo, slightly adapted:

Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer if this object is less than, equal to, or greater than the specified object, respectively.

There are other requirements that usually just happen naturally with a reasonable implementation, but are still important to specify:

The implementor must also ensure that the relation is transitive: (x.compareTo(y) > 0 && y.compareTo(z) > 0) implies x.compareTo(z) > 0.

It is strongly recommended, but not strictly required that x.compareTo(y) == 0 is equivalent to x.equals(y). Generally speaking, any class that implements the Comparable interface and violates this condition should clearly indicate this fact. The recommended language is “Note: this class has a natural ordering that is inconsistent with equals.”

Typically, a class will compare to objects of the same type as itself (although it does not strictly have to). Doing so means data structures that require ordering (like sorted lists, and in the future, search trees) can contain the class.

Exercise: User

In User.java, we’ve provided an example of how a website might model a user.

Make User implement Comparable. Use the generic parameter to Comparable to ensure that User can only be used to compare against other Users.

The natural ordering for User is to compare by ID number. If their ID numbers are the same, then compare them on their username.

After implementing this, you should be able to sort Users:

public static void main(String[] args) {
    User[] users = {
        new User(2, "Nandini", ""),
        new User(4, "Zoe", ""),
        new User(5, "Allyson", ""),
        new User(1, "Sohum", ""),
        new User(1, "Jedi", "")
    };
    Arrays.sort(users);
    for (User user : users) {
        System.out.println(user);
    }
}
User{id=1, name=Jedi, email=}
User{id=1, name=Sohum, email=}
User{id=2, name=Nandini, email=}
User{id=4, name=Zoe, email=}
User{id=5, name=Allyson, email=}

Note that here we use Arrays.sort because users is an array; if it was a Java Collection like ArrayList, we would use Collections.sort.

Discussion: Inheritance and Overriding

Read from the beginning of Chapter 4.2 through (and including) Casting.

There are lots of tricky concepts in this chapter; the best way to learn them is by applying them through practice and remember that Java follows a very strict and precise set of rules.

Note much of this will be a review from material that we covered in lecture 2. If you feel confident on the material you should be able to skip this reading, but we recommend at least skimming again as a refresher.

Between you and your partner, come up with a definition and procedure in your own words for each of the following terms.

  • Compile-time type (also known as static type)
  • Runtime type (also known as dynamic type)
  • Superclass
  • Subclass
  • Extends
  • Overriding and dynamic method selection

Discussion: Cats and Dogs

Discuss the first problems from the Spring 2019 Exam Prep 4 worksheet and check your answers against the solution.

Make sure that both partners understand why each answer is what it is. A good question to really check your understanding is to ask, “What if we removed this method?” or, “What if we added another overloaded method?”

Refer to the Inheritance Rules below if you’re not sure how to handle a particular problem. These formal procedures are helpful to reference when working through some of the trickier situations that can happen when designing with inheritance.

Recap: Inheritance Rules

All fields (class and instance variables) and static methods (class methods) are looked up against the static type of the variable or expression.

Overloading
Overloading occurs when there are multiple methods within a class with the same name, but different parameters. Note that, “In a subclass, you can overload the methods inherited from the superclass. Such overloaded methods neither hide nor override the superclass instance methods—they are new methods, unique to the subclass.”
Dynamic Method Selection
“An instance method in a subclass with the same signature (name, plus the number and the type of its parameters) and return type as an instance method in the superclass overrides the superclass’s method.”

Note that selecting methods by the dynamic type of the object only applies to non-static, instance methods! All other members, including static methods, and both static and non-static variables, are looked up against the static type of the object only: no overriding occurs for these members!

At compile-time, the compiler, using the static type, creates a link to the exact matching method signature, which includes the name, number and type of parameters (as they appear exactly), and return type of the method. This information is saved in the .class file generated by javac.

Then, at runtime, if the method is an instance method, then override it with the method with a matching signature that is closest to the dynamic type of the object. An overriding method can also return a subtype of the type returned by the overridden method.

Casting
A type cast temporarily changes the static type of a variable, and tells the compiler to trust us, the programmer, that it will work.

So upcasting is always okay.

Dog d = new Dog();
Animal a1 = (Animal) d; // this is okay
Animal a2 = d; // same thing

A cast fails at compile-time if the compiler knows, based on the static type of the variable being casted, that it cannot possibly succeed at runtime:

Tree tree = new Tree();
Animal a3 = (Animal) tree; // compile-time error

Since no Tree is ever an Animal, the compiler knows this cast cannot possibly succeed. So we get a compile-time error: incompatible types: Tree cannot be converted to Animal.

Here’s a downcast:

Animal a4 = new Dog();
Dog dd = (Dog) a4; // no error

a4 has dynamic type Dog, and dd is a reference to a Dog, so it’s okay for dd to refer to a4.

But now consider:

Animal a5 = new Animal();
Dog ddd = (Dog) a5; // runtime error

At compile-time, the reasoning is, “a5 has static type Animal. So a5 could have dynamic type Dog, in which case, the cast will succeed at runtime. Since it’s possible that the cast will succeed, we will allow this to compile.” (Notice that the compiler does not know that a5 has dynamic type Animal.)

But then here’s what happens at runtime: a5 has dynamic type Animal, and ddd is a reference to a Dog. It’s not okay for a reference to a Dog to refer to an Animal. (Why not?) So we get a runtime error: ClassCastException: Animal cannot be cast to Dog.

This example is thanks to Allen Guo.

Nicole Rasquinha, a TA from spring 2018, created a video playlist reviewing and applying this material if you prefer a video presentation of the material. Since these videos are on the long side, it’s best to watch them at home. You might find them helpful when studying later.

The summary video provides a good overview of the compiler’s role in dynamic method selection.

Summary
  • The compiler is a cautious proofreader
  • Compiler only knows static type
Method Procedure
  1. During compile-time, look in static type for method
  2. Write down exact method signature including name and parameters
  3. During runtime, only override if method signature is the same including parameters

Some of the excerpts above were quoted from the Java Tutorials on Overriding and Hiding Methods. Note that this tutorial covers material such as static method hiding which you don’t need to know about.

Comparable Interface
Java has an in-built Comparable interface that uses generics to avoid any weird casting issues. Plus, Comparable already works for things like Integer, Character, and String; moreover, these objects have already implemented a max, min, etc. method for you. Thus you do not need to re-do work that’s already been done!
Overloading
In Java, methods in a class can have the same name, but different parameters. For example, a Math class can have an add(int a, int b) method and an add(float a, float b) method as well. The Java compiler is smart enough to choose the correct method depending on the parameters that you pass in. Methods with the same name but different parameters are said to be overloaded.
Overriding
For each method in AList that we also defined in List, we will add an @Override right above the method signature. As an example:
@Override
public Item get(int i) { ... }

This is not necessary, but is good style and thus we will require it. Also, it allows us to check against typos. If we mistype our method name, the compiler will prevent our compilation if we have the @Override tag.

Static vs. Dynamic Type
Every variable in Java has a static type. This is the type specified when the variable is declared, and is checked at compile-time. Every variable also has a dynamic type; this type is specified when the variable is instantiated, and is checked at runtime. As an example:
Thing a;
a = new Fox();

Here, Thing is the static type, and Fox is the dynamic type. This is fine because all foxes are things. We can also do:

Fox b = a;

This is fine, because now the static and dynamic types match. Because all foxes are animals too, we can do:

Animal c = b;

This is fine, because b points to a Fox and all foxes are animals. Finally, we can do:

a = new Squid()

This is fine, because the static type of a is a Thing, and Squid is a thing.

Dynamic Method Selection
The rule is, if we have a static type X, and a dynamic type Y, then if Y overrides the method from X, then on runtime, we use the method in Y instead. Student often confuse overloading and overriding.
Overloading and Dynamic Method Selection
Dynamic method selection plays no role when it comes to overloaded methods. Consider the following piece of code, where Fox extends Animal.
Fox f = new Fox();
Animal a = f;
define(f);
define(a);

Let’s assume we have the following overloaded methods in the same class:

public static void define(Fox f) { ... }
public static void define(Animal a) { ... }

Line 3 will execute define(Fox f), while line 4 will execute define(Animal a). Dynamic method selection only applies when we have overridden methods. There is no overriding here, and therefore dynamic method selection does not apply.

Comparator Interface
The term “Natural Order” is used to refer to the ordering implied by a Comparable’s compareTo method. However, what if we want to order our Dog objects by something other than size? We will instead pass in a Comparator<T> interface, which demands a compare() method. We can then implement the compare() method anyway we want to achieve our ordering.

Error-Handling

So far in this course, we have not dealt much with error-handling. You were allowed to assume that the arguments given to methods were formatted or structured appropriately. However, this is not always the case due to program bugs and incorrect user input. Here are a few examples of this:

  1. Bugs in your programs might create inconsistent structures or erroneous method calls (e.g. division by zero, indexing out of bounds, dereferencing a null pointer).
  2. Users cannot be trusted to give valid input (e.g. non-numeric input where a number is required or search failures where a command or keyword was misspelled).

We assume in the following discussion that we can detect the occurrence of an error and at least print an error message about it.

A big challenge in dealing with the error is to provide information about it at the right level of detail. For instance, consider the error of running off the end of an array or list. If the contents of a list are inconsistent with the number of elements supposedly contained in the list, a “reference through a null pointer” or “index out of bounds” error may result. The programmer may wish to pass information about the error back to the calling method with the hope that the caller can provide more appropriate and useful information about the root cause of the error and perhaps be able to deal with the error.

Discussion: Error Handling

Here are three approaches to error handling:

  • Don’t try to pass back any information to the caller at all. Just print an error message and halt the program.
  • Detect the error and set some global error indicator (like a public static variable in Java) to indicate its cause.
  • Require the method where the error occurred (and every method that directly or indirectly calls it) to pass back its value or to take an extra argument object that can be set to indicate the error.

Different languages geared towards solving different types of problems take different approaches to error handling. The increasingly popular Go programming language, for example, chooses a design similar to the third option.

Which seems most reasonable? Discuss with your partner, and defend your answer. If none, justify why all the options are bad.

Exceptions

There is a fourth option for handling errors, called an exception. Provided by Java and other modern programming languages, an exception signals that an error of some sort has occurred. Java allows both the signaling of an error and selective handling of the error. Methods called between the signaling method and the handling method need not be aware of the possibility of the error.

An exception is thrown by the code that detects the exceptional situation, and it is caught by the code that handles the problem. These two definitions are helpful in discussing exceptions.

Read Chapter 6.1 and 6.2 of the online textbook to learn more about exceptions.

An extension to the try catch block construct that often comes in handy is the finally block. A finally block comes after the last catch block and is used to do any cleanup that might be necessary, such as releasing resources the try block was using. This is very common when working with input-output like opening files on your computer.

Scanner scanner = new Scanner(System.in);
int k;
try {
    k = scanner.nextInt();
} catch (NoSuchElementException e) {
    // Ran out of input
} catch (InputMismatchException e) {
    // Token isn't an integer
} finally {
    // finally will be executed as long as JVM does not exit early
    scanner.close();
}

This use of the finally block so common that the Java language developers introduced the try-with-resources block. It allows you to declare resources being used as part of the try block, and automatically release those resources after the block finishes executing. The code below is equivalent to the snippet above, but it doesn’t use the finally block.

int k;
try (Scanner scanner = new Scanner(System.in)) {
    k = scanner.nextInt();
} catch (NoSuchElementException e) {
    // ran out of input
} catch (InputMismatchException e) {
    // token isn't an integer
}

Iteration

In CS 61BL, we’re going to encounter a variety of different data structures, or ways to organize data. We’ve implemented linked lists like DLList and resizing array-based lists like AList. Starting Thursday, we’ll see more complicated data structures such as trees, hash tables, heaps, and graphs.

A common operation on a data structure is to process every item. But often, the code we need to write to setup and iterate through a data structure differs depending on the data structure’s implementation.

for (int i = 0; i < array.length; i += 1) {
    // Do something with array[i]
}

For SLList, the pattern significantly differs from above.

SLList list = ...
for (IntNode p = list.sentinel.next; p != null; p = p.next) {
    int item = p.item;
}

Evidently, we need to write two very different codes in order to do the exactly same thing. It would be nice if we can write one piece of code that we can reuse for different data structures. In other words, we wish to abstract away the internal implementation of data structures from the operations on them.

Furthermore, if we use a different data structure, a for loop like the one above may not make sense. For example, what would it mean to access the kth item of a set, where order of items is not defined? We need a more abstract notion of processing every item in a data structure, something that allows us to check every item regardless of how they’re organized. To do that, we’re going to use something called an iterator.

Enhanced for Loop

It turns out that we’ve been using iterators all semester long! When Java executes an enhanced for loop, it does a bit of work to convert it into iterators and iterables. The following code represents the enhanced for loop you have most likely already seen and then a translated version which reveals what is happening behind the hood using an iterator.

List<Integer> friends = new ArrayList<>();
friends.add(5);
friends.add(23);
friends.add(42);
for (int x : friends) {
    System.out.println(x);
}
List<Integer> friends = new ArrayList<>();
friends.add(5);
friends.add(23);
friends.add(42);

Iterator<Integer> seer = friends.iterator();
while (seer.hasNext()) {
    int x = seer.next();
    System.out.println(x);
}

Iterable

How does this work? List is an interface which extends the Iterable interface. An iterable is something which can be iterated over, so all Collections implement Iterable.

public interface Iterable<T> {
    Iterator<T> iterator();
}

The iterator() method initializes an iterator by returning an object of type Iterator, which can then be used to iterate.

Your next questions is probably what is an Iterator? It turns out this is another interface!

Iterator

package java.util;

public interface Iterator<T> {
    boolean hasNext();
    T next();
    default void remove() { // implementation not shown }
    default void forEachRemaining(Consumer<? super E> action) { // implementation not shown}

}
hasNext
hasNext is a boolean method that says whether there are any more remaining items in the data structure to return. In other words, returns true if next() would return an element rather than throwing an exception.
next
next successively returns items in the data structure one by one. The first call to next returns the first value, the second call to next returns the second value, and so on. If you’re iterating over a set—a data structure that is not supposed to have an order—we might not necessarily guarantee that next returns items in any specific order. However, what we do need to guarantee is that it returns each item exactly once. If we were iterating over a data structure that does have an ordering, like a list, then we would also like to guarantee that next returns items in the right order.

It’s worth noting that every call to next() is typically preceded by a call to hasNext(), thus ensuring that the Iterator does indeed have a next value to return. If there are no more elements to remaining, it is common practice to throw a NoSuchElementException.

remove
Because this is declared as a default method in the interface, it need not be overridden and as such it is rarely implemented in this class and elsewhere. The default implementation throws an UnsupportedOperationException and performs no other action, thus this is an optional operation. If implemented the method removes from the underlying collection the last element returned by this iterator. This method can be called only once per call to next(). The behavior of an Iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.
forEachRemaining
Also declared as default and thus does not need to be implemented. This will never be overridden for Iterators you will be asked to make for this class. Performs the given action for each remaining element until all elements have been processed or the action throws an exception. Actions are performed in the order of iteration, if that order is specified. Exceptions thrown by the action are relayed to the caller.

Why design two separate interfaces, one for iterator and one for iterable? Why not just have the iterable do both?

The idea is similar to Comparable and Comparator. By separating the design, we can provide a ‘default’ iterator, but also allow for programmers to implement different iterators with different behaviors. While the AList class might, by default, provide an efficient AListIterator implementation, this design opens up the possibility of defining an AListReverseIterator that can iterate over an AList in reverse, all without modifying any of the code in AList!

AListIterator

Here’s an example of inserting the iterator methods into the AList class from the online textbook. Don’t worry if you don’t get it all right away or the generics.

import java.util.Iterator;

public class AList<Item> implements Iterable<Item> {

    private Item[] values;
    private int size;

    // AList constructors and methods would normally appear here.

    public Iterator<Item> iterator() {
        return new AListIterator();
    }

    private class AListIterator implements Iterator<Item> {

        private int bookmark = 0;

        public Item next() {
            Item toReturn = values[bookmark];
            bookmark += 1;
            return toReturn;
        }

        public boolean hasNext() {
            return bookmark < size;
        }
    }
}

The code maintains an important invariant: prior to any call to next, bookmark contains the index of the next value in the list to return.

Notice also that we don’t need a generic type in the AListIterator class declaration. Since it’s a non-static nested class (called an inner class), the AList generic type still applies. The implication of AListIterator being non-static means that an AListIterator cannot be created without an existing AList instance: the AListIterator needs to know its outer AList’s generic type Item in order to function correctly.

We can then use our AList class exactly like in the earlier examples, and even in an enhanced for loop.

AList<Integer> friends = new AList<>();
friends.add(5);
friends.add(23);
friends.add(42);

Iterator<Integer> seer = friends.iterator();
while (seer.hasNext()) {
    int x = seer.next();
    System.out.println(x);
}
AList<Integer> friends = new AList<>();
friends.add(5);
friends.add(23);
friends.add(42);
for (int x : friends) {
    System.out.println(x);
}

Defining Iterators

Often, when writing our own iterators, we’ll follow a similar pattern of doing most of the work in next.

  1. We save the next item with Item toReturn = values[bookmark].
  2. Move the bookmark to the next item with bookmark += 1.
  3. Return the item we saved earlier.

An important feature of the code is that hasNext doesn’t change any state. It only examines existing state by comparing the progress of the iteration to the number of list elements. hasNext can then be called twice in a row and nothing should change, or it could be called not at all and the iteration should still work as long as there are elements left to be returned.

Discussion: Iterator Invariants

Consider the following AListIterator, slightly different from those we just encountered.

private class AListIterator implements Iterator<Item> {

    private int bookmark = -1;

    public Item next() {
        bookmark += 1;
        return values[bookmark];
    }

    public boolean hasNext() {
        return (bookmark + 1) < size;
    }
}

Now, discuss the following questions with your partner:

  1. What’s the invariant relation that’s true between calls to next?
  2. In general, most experienced programmers prefer the organization introduced first over this organization. What might explain this preference?

Finally discuss these next two questions and answers with your partner. These questions deal with the order in which methods are called and it is important to understand this before using an Iterator.

What if someone calls next when hasNext returns false?
This violates the iterator contract so the behavior for next is undefined. Crashing the program is acceptable. However, a common convention is to throw a NoSuchElementException.
Will hasNext always be called before next?
Not necessarily. This is sometimes the case when someone using the iterator knows exactly how many elements are in the sequence. For this reason, we can’t depend on the user calling hasNext when implementing next.

Exercise: DLListIterator

As mentioned before, it is standard practice to use a separate iterator object (and therefore a separate, typically nested class) as the actual Iterator. This separates the Iterator from the underlying data structure or iterable.

Modify the provided DLList class so that it implements Iterable<Item>. Then, add a nested DLListIterator class which implements Iterator<Item>. Note that if you submit to the autograder before you implement this, your code likely will say that there are compilation errors coming from the autograder tests (you will see errors like “error: cannot find symbol” for calls to a.iterator or similar). Once you have properly completed this, the errors should go away.

Note that DLList itself does not implement Iterator. This is why we need a separate, nested, private class to be the iterator. Typically, this class is nested inside the data structure class itself so that it can access the internals of the object that instantiated the instance of the nested class.

Make sure that you’ve completed the following checklist.

  1. Does your DLList object know anything about its DLListIterator’s state? Information about iteration (index of the next item to return) should be confined to Iterator alone.
  2. Are multiple Iterators for the same DLList object independent of each other? There can be multiple Iterators for a single DLList object, and one iterator’s operation should not affect the state of another.
  3. Does hasNext alter the state of your Iterator? It should not change state.

After you have modified your DLList class, write some test code to see if Java’s enhanced for loop works as expected on your DLList.

Discussion: Concurrent Modification

For our lab, we regarded our data structure to be “frozen,” while the Iterator was at work. In other words, we assumed that while we were operating on the iterators, the data structure would remain as is. However, this is not generally true in the real world.

Iterator<BankAccount> it = accounts.iterator();
while (it.hasNext()) {
    // Remove the next account!
    checkValidity(it.next()); // This code breaks since the account was removed.
}

If all clients of the data structure were to only read, there would be no problem. However, if any were to modify the data structure while others are reading, this could break the fundamental invariant that next returns the next item if hasNext returns true!

To handle such situations, many Java iterators throw ConcurrentModificationException if they detect that the data structure has been externally modified during the iterator’s lifetime. This is called a “fail-fast” behavior.

List<String> friends = new ArrayList<>();
friends.add("Nyan");
friends.add("Meow");
friends.add("Nyaahh");
for (String friend : friends) {
    friends.remove(1);
    System.out.println("friend=" + friend);
}

Discuss with your partner about how to implement this “fail-fast” property for a data structure. How can we propagate the modification to all existing iterators?

If you want to see the Java standard library solution, run the above code, see the error message and click on the link in the stack trace ArrayList.java:1042 (note the line number might be slightly different depending on your Java version) to see where the fail-fast happened. You can even see how Java implements their nested Iterator.

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1042)

Delegation

The key advantage of using iterators over, say, the old fashioned way of getting items from a list lies in programming cost and execution cost.

Programming cost
How long it takes to develop, modify, and maintain code.
Execution cost
How long or how much space it takes to execute code on a computer.

Iterators are a powerful abstraction that allow us to reduce both programming cost and execution cost.

Let’s compare and contrast all the different ways to iterate over all the elements in an SLList.

Direct pointer manipulation
While this has a good execution cost as it runs in \(\Theta(N)\) time, it increases programming cost as the developer needs to know exactly how linked lists work, not to mention it’s a violation of abstraction barriers! Forgetting to include p = p.next is a very easy way to get stuck in an infinite loop. Moreover, the programmer need to know the exact details of the implementation like the fact that SLList uses a single sentinel node and is null-terminated, while DLList uses a single, circular sentinel node structure. As our data structures and our problems get increasingly complex, it will get harder and harder to maintain programs written in this way.
SLList list = SLList.of(1, 2, 3, 4, 5);
IntNode p = list.sentinel.next;
while (p != null) {
    int item = p.item;
    System.out.println(item);
    p = p.next;
}
Abstract data type methods
Using our provided ADT methods reduces programming costs significantly since we no longer need to worry about how the linked list works (and the code now works more generally as well), but our execution cost increases as the get operation isn’t optimized for sequential access! The following code runs in \(\Theta(N^2)\) time where \(N\) is the size of the list.
SLList list = SLList.of(1, 2, 3, 4, 5);
int i = 0;
while (i < list.size()) {
  int item = list.get(i);
  System.out.println(item);
  i += 1;
}
Iterators
Iterators provide the best of both worlds by creating an abstraction for sequential access. The programming cost is incurred once by the SLList programmer, not the client using SLList! The client only has to understand how the iterator interface works to use the class.
SLList list = SLList.of(1, 2, 3, 4, 5);
Iterator<Integer> seer = list.iterator();
while (seer.hasNext()) {
  int item = seer.next();
  System.out.println(item);
}

Java provides the enhanced for loop to make this even easier to use.

SLList list = SLList.of(1, 2, 3, 4, 5);
for (int item : list) {
  System.out.println(item);
}

By delegating work to the implementation, we can reduce both programming cost by writing code that adheres to a universally-accepted standard interface while gaining all the execution cost benefits of specialization thanks to dynamic method selection.

In this way, delegation is a form of abstraction. Just like we saw with the idea of encapsulation earlier in the course, delegation makes it much easier to compose efficient programs.

Deliverables

Here’s a quick recap of what you need to do to complete this lab!

  • Understand how compareTo relates to higher order functions.
  • Understand how method overloading and overriding work with inheritance relationships.
  • Make the User class implement Comparable.
  • Finish DLList

You will need to complete the two exercises:

  • In User.java you should have modified the file to implement the Comparable interface.
  • Make DLList.java iterable.

If you have any time remaining in your lab, we recommend that you stick around and work on midterm prep problems with your partner! If your TA is available this is a great time to ask questions.

Be sure to submit to gradescope and select your partner!