Before You Begin

Pull the skeleton code from GitHub as usual. Open IntelliJ and remember to Import Project and add javalib to the Project Structure.

If something isn’t working, usually re-importing the project (choosing to overwrite any existing configurations) and re-adding javalib to the Project Structure will fix things.

Linked Lists

In today’s lab, we’re going to continue our discussion of linked lists by introducing a new way of organizing programs through encapsulation.

We will first define a few terms.

Module
A set of methods that work together as a whole to perform some task or set of related tasks.
Encapsulated
A module is said to be encapsulated if its implementation is completely hidden, and it can be accessed only through a documented interface.

Encapsulation

The previous iteration of IntList that we learned is impractical to use at scale.

In our current IntList, the notion of a node in the list and the list itself are not separate. This means that someone who wants to use the IntList class would need to spend a lot of time adding null checks and handling errors that might come as a result of accidentally or intentionally modifying the first or rest of a list. By giving users direct control to the IntList data structure’s internals, in some ways, we’ve actually made it harder to reason about the correctness of a program.

We want to separate the idea of the list as an entity from an entry in the list, much like the abstraction barrier you might remember from CS 61A. We’ll see that this design philosophy of encapsulation will come up over and over again for each of the data structures we study in the coming weeks.

Read the entirety of SLLists, Chapter 2.2.

Then, discuss how the idea of invariants at the end of the chapter relates to how someone might reason about the correctness of code that uses IntList vs. SLList.

Discussion: addFirst

Exercise 2.2.1
The curious reader might object and say that the IntList would be just as easy to use if we simply wrote an addFirst method. Try to write an addFirst method to the IntList class. You’ll find that the resulting method is tricky as well as inefficient.

In the textbook, we implemented SLList.addFirst.

public class SLList {
    public IntNode first;

    public SLList(int x) {
        first = new IntNode(x, null);
    }

    /** Adds an item to the front of the list. */
    public void addFirst(int x) {
        first = new IntNode(x, first);
    }
}

Discuss with your partner how you might implement IntList.addFirst.

Consider the case below, and how you might make it so that the IntList L in main can see the changes. It’s not as straightforward as you might think!

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

    public void addFirst(int x) {
        // Describe in your own words what you might put here.
    }

    public static void main(String[] args) {
        IntList L = IntList.of(2, 3, 4, 5);
        L.addFirst(1);
        System.out.println(L.first);
    }
}

Printing out L.first should display the number 1 even without reassigning L in the main method.

Hint: If we know that the reference, L, cannot be changed, what are our options for making the changes in addFirst visible to main? We know that, due to Golden Rule of Equals, there’s no way to change what L points to from the addFirst method. Given these constraints, try drawing a box-and-pointer diagram that shows what it should look like before and after calling addFirst.

Exercise: toString and equals

Normally, we would ask you to manually write out these methods to convert a list into its String representation and to write an equality checker. However, since we’re using IntelliJ, let’s utilize one of its features: automatic code generation.

Move your blinking cursor to somewhere inside the IntNode class and press the Code tab at the top. Then, click the Generate button and this should bring up a Generate menu at your cursor. Go ahead and select toString(), take a look at the dialog, and press OK.

You’ll notice a toString() method is generated for the IntNode class, using the fields you specified. (Both fields should have been highlighted.) Now pull up the menu again, and this time select equals() and hashCode(). Look at the dialog boxes, press OK & next as needed, and you’ll see the equals() and hashCode() methods appear automatically. You can feel free to delete the hashCode() method as we won’t need it and will be learning about it later in the course.

Repeat the process with your cursor inside the SLList class, and now you’ll have equals() and toString() methods automatically generated and working. This doesn’t work 100% of the time, but it’s a great way to get a framework going quickly. You can even generate constructors and several other kinds of useful methods!

Make sure to generate toString and equals for both IntNode and SLList or it won’t pass the tests later.

If the IntelliJ-generated equals method includes an if case mentioning the keyword super, delete that test case.

Note that you’ll still need to clean-up the code a bit to pass the style checker.

Exercise: add

As a bit of practice working with such lists, implement the add method in SLList.java, which adds the int x to the list at the specified int index.

public void add(int index, int x) {
    // TODO
}

Check your solution with the tests provided in SLListTest.java.

Exercise: reverse

Over the next few steps, we’re going to be working on a method to reverse an SLList using our current SLList implementation.

We will assume the restriction that the reversal is to be done in place, destructively, without creating any new nodes.

public void reverse() {
    // TODO
}

However, don’t implement the method just yet!

Testing reverse

Make sure that you’re familiar with how to test with JUnit from the section on Testing in last lab.

We’re going to write a test before we write reverse, as part of a methodology called test-driven development (TDD).

Thinking about test cases before writing code can help us write better code more quickly compared to rushing ahead and trying to solve the problem without first having considered all the different scenarios.

We’ve included a very basic test, testReverse, in SLListTest.java. Add a couple more test cases in the same style as the first few to test larger lists of length 2, 3, 4, 5, and more until you’re satisfied that the tests cover all the bases.

In the end, your tests should test at least the following three situations:

  • That the function returns a reversed list.
  • That the function is destructive, i.e. when it is done running, the list pointed to by A has been tampered with. You can use assertNotEquals. This is sort of a silly test.
  • That the method handles a null input properly.

Once you’ve written your test, discuss with your partner to make sure you’ve both written tests for at least all three situations above.

Implementing reverse

public void reverse() {
    // TODO
}

Try running the test we just wrote; it should fail. This is a good thing because it means our tests are working as expected.

Implement reverse, and rerun the tests until all of them pass. A static helper method will be helpful.

Why? Discuss with your partner why a static helper method might be useful here, and what its method signature would be.

The method signature consists of the method name and parameter types.

Hint: This is a challenging problem. If you’re stuck, try drawing things out on a whiteboard, talking it through with your partner, and solving each test one-by-one, even if the solution doesn’t look elegant. For example, it is possible to implement reverse using a huge if statement that performs different operations for different-length lists.

public void reverse() {
    if (size() == 0) {
        // Do nothing: reverse of an empty list requires no change.
    } else if (size() == 1) {
        // Do nothing: reverse of a single item list requires no change.
    } else if (size() == 2) {
        IntNode first = sentinel.next;
        IntNode second = sentinel.next.next;
        second.next = first;
        first.next = null;
        sentinel.next = second;
    } else if (size() == 3) {
        ...
    }
}

Even though this might feel icky, we can use this approach to help find patterns in the recursive logic and help us get a sense for what operations are needed to solve the problem.

Some people find the rush of TDD addictive. You basically set up a little game for yourself to solve. Some people hate it. Your mileage may vary. Whether you personally enjoy the TDD flow or not, writing tests will be one of the most important skills you learn here at Berkeley, and getting test-infected will save you and your future colleagues an enormous amount of time and misery.

If you find the concept of test-driven development interesting, or just want to learn more about testing philosophy and the conversation around TDD, here are a couple recommended optional readings:

Doubly-Linked

There are some major issues, both efficiency-wise and code-simplicity-wise with the linked list implementations we’ve been working with so far:

  • It’s easy to insert into the front of the list, but requires a lot more work to insert into the back of the list.
  • If we want to remove a node in our linked list, even if we have a reference to the node we want to remove, we have to traverse until we find the node before it in order to remove it.

The solution to these problems is to use a doubly-linked list.

Read the entirety of DLLists, Chapter 2.3. It’s not too long.

Exercise: DLList Methods

Implement add and remove in DLList.java.

Read through the existing code—some of it can be used as a reference and example for how you can structure your methods. You should never need to type the word null or do any edge case checking, thanks to the sentinel design.

Recap

Naked Data Structures
IntLists are hard to use. In order to use an IntList correctly, the programmer must understand and utilize recursion even for simple list-related tasks.
Adding Clothes
First, we will turn the IntList class into an IntNode class. Then, we will delete any methods in the IntNode class. Next, we will create a new class called SLList, which contains the instance variable first, and this variable should be of type IntNode. In essence, we have “wrapped” our IntNode with an SLList.
Using SLList
As a user, to create a list, I call the constructor for SLList, and pass in the number I wish to fill my list with. The SLList constructor will then call the IntList constructor with that number, and set first to point to the IntList it just created.
Improvement
Notice that when creating a list with one value, we wrote SLList list = new SLList(1). We did not have to worry about passing in a null value like we did with our IntList. Essentially, the SLList class acts as a middleman between the list user and the naked IntList.
Public vs. Private
We want users to modify our list via SLList methods only, and not by directly modifying first. We can prevent other users from doing so by setting our variable access to private. Writing private IntNode first; prevents code in other classes from accessing and modifying first (while the code inside the class can still do so).
Nested Classes
We can also move classes into classes to make nested classes! You can also declare the nested classes to be private as well; this way, other classes can never use this nested class.
Static Nested Classes
If the IntNode class never uses any variable or method of the SLList class, we can turn this class static by adding the “static” keyword.
Recursive Helper Methods
If we want to write a recursive method in SLList, how would we go about doing that? After all, the SLList is not a naturally recursive data structure like the IntNode. A common idea is to write an outer method that users can call. This method calls a private helper method that takes IntNode as a parameter. This helper method will then perform the recursion, and return the answer back to the outer method.
Caching
Previously, we calculated the size of our IntList recursively by returning 1 + the size of the rest of our list. This becomes really slow if our list becomes really big, and we repeatedly call our size method. Now that we have an SLList, lets simply cache the size of our list as an instance variable! Note that we could not do this before with out IntList.
Empty Lists
With anSLList, we can now represent an empty list. We simply set first to null and size to 0. However, we have introduced some bugs; namely, because first is now null, any method that tries to access a property of first (like first.item) will return a NullPointerException. Of course, we can fix this bug by writing code that handles this special case. But there may be many special cases. Is there a better solution?
Sentinel Nodes
Lets make all SLList objects, even empty lists, the same. To do this, lets give each SLList a sentinel node, a node that is always there. Actual elements go after the sentinel node, and all of our methods should respect the idea that sentinel is always the first element in our list.
Invariants
An invariant is a fact about a data structure that is guaranteed to be true (assuming there are no bugs in your code). This gives us a convenient checklist every time we add a feature to our data structure. Users are also guaranteed certain properties that they trust will be maintained. For example, an SLList with a sentinel node has at least the following invariants:
  • The sentinel reference always points to a sentinel node.
  • The front item (if it exists), is always at sentinel.next.item.
  • The size variable is always the total number of items that have been added.
SLList Drawbacks
addLast() is slow! We can’t add to the middle of our list. In addition, if our list is really large, we have to start at the front, and loop all the way to the back of our list before adding our element.
A Naive Solution
Recall that we cached the size of our list as an instance variable of SLList. What if we cached the last element in our list as well? All of a sudden, addLast() is fast again; we access the last element immediately, then add our element in. But removeLast() is still slow. In removeLast(), we have to know what our second-to-last element is, so we can point our cached last variable to it. We could then cache a second-to-last variable, but now if I ever want to remove the second-to-last element, I need to know where our third-to-last element is. How to solve this problem?
DLList
The solution is to give each IntNode a prev pointer, pointing to the previous item. This creates a doubly-linked list, or DLList. With this modification, adding and removing from the front and back of our list becomes fast (although adding/removing from the middle remains slow).
Incorporating the Sentinel
Recall that we added a sentinel node to our SLList. For DLList, we can either have two sentinels (one for the front, and one for the back), or we can use a circular sentinel. A DLList using a circular sentinel has one sentinel. The sentinel points to the first element of the list with next and the last element of the list with prev. In addition, the last element of the list’s next points to the sentinel and the first element of the list’s prev points to the sentinel. For an empty list, the sentinel points to itself in both directions.
Generic DLList
How can we modify our DLList so that it can be a list of whatever objects we choose? Recall that our class definition looks like this: 
public class DLList { ... }

We will change this to:

public class DLList<T> { ... }

where T is a placeholder object type. Notice the angle bracket syntax. Also note that we don’t have to use T; any variable name is fine. In our DLList, our item is now of type T, and our methods now take T instances as parameters. We can also rename our IntNode class to TNode for accuracy.

Using Generic DLList
Recall that to create a DLList, we typed: 
DLList list = new DLList(10);

If we now want to create a DLList holding String objects, then we must say:

DLList<String> list = new DLList<>("bone");

On list creation, the compiler replaces all instances of T with String! We will cover generic typing in more detail in later lectures.

Deliverables

Here’s a short summary on what you need to do to complete this lab.

  • Identify the differences between today’s implementation of IntList and yesterday’s implementation.
  • Use the Intellij code generation tool to auto-generate a toString and equals method for the IntNode and SLList classes.
  • Implement add for today’s implementation of SLList.
  • Implement reverse with a recursive helper method.
  • Understand the benefits and trade-offs between using a singly-linked and double-linked list.
  • Implement add and remove methods in DLList.java.

There is no assessment for this lab, so you can either work ahead, spend time on the project, or ask questions about the upcoming exam.