A. Intro

Learning Goals

Today we're going to continue our discussion of linked lists. In particular, you will be introduced to the concept of encapsulation, doubly-linked lists, and sentinels.

To get started, download the code for Lab 6 using git.

Testing Your Code

We have provided a suite of JUnit tests for you in TestLab06.java. To run the tests, you can right click on TestLab06.java in IntelliJ and select Run 'TestLab06.java. Afterward, you can select TestLab06 in the upper right corner of IntelliJ and press the green button to run the tests again.

Tip: It is a good practice to read the test code to be familiar with JUnit4, since you will soon be writing your own tests for future labs!

B. Encapsulation

The previous iteration of IntList that we learned is impractical to use at scale. The notion of a node in the node and the list itself are not separate. This means that null checks would be scattered throughout code that uses the IntList, becoming increasingly difficult to maintain and understand. Instead, we want to separate out the idea of the list as an entity, and an entry in the list. This is called encapsulation, and we will see this used for every data structure we learn in the future.

Let's see what this looks like for our basic IntList.

In code, it looks like this:

public class IntList {
    /** The head of the list is the first node in the list. If the list is empty, head is null **/
    private IntListNode head;
    private int size;

    /** IntListNode is a nested class. It can be instantiated when associated with an instance of
     *  IntList.
     *  **/
    public class IntListNode {
        int item;
        IntListNode next;

        public IntListNode(int item, IntListNode next) {
            this.item = item;
            this.next = next;
        }
    }

    ... more methods to operate on ...
}

All operations on the list are handled through an instance of an IntList object, which in turn operates on the IntListNodes it contains that make up the list itself. Note that IntListNode does not need any methods (other than some utility toString(), equals(), and so on methods which you will add later). The main effect of this is that code that wants to interact with the IntList needs to know nothing about the internal representation of the list, but instead simply tells the list what it needs and the IntList representation itself will take care of any null checks or size checks and further operations.

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 and 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 IntListNode class and press Alt+Insert (or on Mac, Command+N). This should bring up a "Generate" menu where your cursor is - go ahead and select "toString()", take a look at the dialog, and press OK. You'll notice a toString() method is generated for the IntListNode class, using the fields you specified (both should have been checked). 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 IntList class, and now you'll have equals() and toString() methods automatically generated and working. This doesn't work 100% of the time (as we'll see in the next part), but it's a great way to get a framework going quickly. You can even generate constructors, getters and setters, and so on!

Exercise: Implement insert()

As a bit of practice working with such lists, fill in the insert(int x, int position) method in IntList.java. Note that this is not the same IntList as used in the previous lab. While it seems obvious to read, it may be helpful to think that, for example, inserting into position 1 is equivalent to finding the node at position 0 and inserting after it.

Exercise: Implement merge()

Suppose two high schools in a school district both have running teams. Each maintains a sorted IntList storing their athletes' 800 meter times to the nearest second. Now suppose the two high schools want to make a combined school district team. How would they choose the fastest runners from both schools?

This is just one real-world use for the merge function, an interesting utility that you may have touched upon in CS 61A.

Implement the non-destructive static method merge in your IntList class. This method will take as input two sorted IntLists and return the IntList that contains all elements from both input IntLists in sorted order.

(Optional) Exercise: Implement remove()

Fill in the remove(int position) method in IntList.java. Make sure to take care of edge cases, like removing the last element in the list.

C. Reverse

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

• We will assume the restriction that the reversal is to be done in place, that is, without creating any new IntListNodes (Does this mean destructive or non-destructive?).
• A static method will be helpful.
• We must pay close attention to the next references when we reverse all of the links.

Reversing a List in Place

To reverse the list in place, we recommend using a static helper method.

Here's the framework code for reverse. Don't fill it in yet.

public IntList reverse() {
    // ...
}

public static IntListNode reverseHelper(IntListNode l, IntListNode soFar) {
    // ...
}

An Invariant for Reversing a List

This framework suggests we maintain a recursion invariant that relates the values of l and soFar at each call.

Here is a trace of a call to reverse with the list that represents {A, B, C, D}

Exercise: Completing the reverse Method

Whenever helper is called, L is the list of elements not yet reversed, and soFar is the reversed list of the elements already processed. To design the procedure from this relation, we position ourselves in the middle of the recursion, say, with L equal to (C D) and soFar equal to (B A). What do we do with C, the next element in L, so that soFar is the reverse of (A B C)? The answer is to add it to the current soFar.

We apply the same reasoning for the reverseHelper method. Here's its header:

private static IntListNode reverseHelper(IntListNode l, IntListNode soFar) {
    if (l == null) {
        return soFar;
    } else {
        ...
    }
}

Again, we position ourselves in the middle of the recursion. For design in Java, it helps to draw box-and-arrow diagrams; here's the situation with L pointing to the list (C D) and soFar pointing to the list (A B), along with the structure that should be passed to the recursive call. The boxes outlined in bold are the boxes whose contents should change.

There are three changes to be made. All are interdependent, though, so we need a temporary variable:

IntListNode temp = l.next;
l.next = soFar;
return reverseHelper ( ____ , ____ );

The copying of the arguments in the recursive call will provide the other two changes to box values.

Fill in the arguments of the recursive call to complete the helper method.

Finally, fill in the reverse() method in IntList.java and create the helper method so that it is correct.

D. The Standard Doubly-linked List

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

1. 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.
2. If we want to remove a node in our linked list, we have to traverse until we find that node, then remove it, even if we have a reference to the node we want to remove.
3. Due to an empty list being represented by the head field being null, and the end of a list being represented by the next field being null, there are null checks and special cases everywhere in the code.

The solution to the first two problems is to use a doubly-linked list. Each node keeps track of the node after and before itself. Instead of just a head pointer, the list object maintains both a head and tail pointer, to the front and back of the list respectively. It looks like this:

This adds a bit of complexity to the operations, but allows for constant time insertion to the front and back, and allows the user to traverse the list either forwards or backwards. Additionally, this allows the list to delete any nodes, even in the middle of the list, in constant time without traversing to the middle as long as it has a reference to the node that needs to be deleted.

This doesn't fix the issue of many null checks, however, in conjunction with the doubly linked list, we can eliminate null checks and simplify the code greatly with usage of a sentinel node, instead of a head and tail. The sentinel node always exists, and does not represent an actual node in the list. It's next field represents the front of the list and it's prev field represents the back of the list. The sentinel's item is null, and an empty list is represented by just a sentinel node pointing to itself. In a box and pointer diagram, it looks like this:

This has many benefits. When iterating through the list, we do not need to worry about reaching a null pointer at any point; when our moving pointer reaches the sentinel, it's the end of the list. When inserting and removing nodes, we don't need to manually handle being near the end or beginning or being the first or last element inserted or removed of the list; the code can be written with disregard for edge cases and it will still work properly because of the sentinel. Because of this, in practice the doubly linked list with a sentinel node is typically used in practice as the linked list representation, like in Java's own standard library class, java.util.LinkedList.

Finally, note one last thing - in the diagrams above, it's clear that sentinel, next and prev point to DLNode object. However, item is ambiguous and doesn't point to anything. This is because in our new list, item will be an Object, which can hold any type. Instead of using only ints like before, we allow our list to be more robust, like python lists, holding mixtures of any kind of object. We'll talk more about how this works in a later lab, but for now you can add items to your DLList and print out their values without fear of type problems, like so:

public static void main(String[] args) {
    DLList l = new DLList();
    l.insertBack("CS"); //String
    l.insertBack(61); //Integer
    l.insertBack("BL!");
    System.out.println("l = " + l);
}

$ java DLList
l = DLList(CS, 61, BL!)

Note that if we want to actually manipulate anything out of our list, we'd have to cast it, like so:

Integer sixtyone = (Integer) l.get(1);

Although you won't be needing to do any of that.

Exercise: Implement insert(), insertFront(), and both remove() methods

Fill in insert(), insertFront(), and both remove() methods 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 not need to ever type the word null or do any edge case checking. Your only if statement should be in remove(Object o).

E. Double In Place and Reverse, revisited

Exercise: Implement doubleInPlace()

Implement the method doubleInPlace. Each node in the list should be copied in place, resulting in a list that's twice as long. For example, if the list initially contains (a, b, c), it should contain (a, a, b, b, c, c) after the call to doubleInPlace. Is this a destructive or non-destructive method?

Don't call any methods other than the DLNode constructor, and don't call it more than once per node in the original list. Draw a box-and-pointer diagram if you're stuck!

Exercise: Implement reverse()

Implement reverse() iteratively in DLList.java. As before, we do not need any null checks or special cases. You should be able to do this only iterating through the list once and flipping all the pointers around as you go - try drawing a box and pointer diagram before you start.

F. Conclusion

Summary

You should have some more practice with working with linked lists and their various representations - singly vs doubly linked with sentinel. We also saw some different ways to implement things - recursively and iteratively, both with their tradeoffs.

Submission

Submit as lab06:

• IntList.java
• DLList.java