Lab 2: List Improvement¹

• Assigned: Monday, January 18
• Check-in Post: Before 9pm Thursday, January 21 (check-in forum)
• Due: 9pm Monday, January 25
• Collaboration: Individual assignment
• Handout: starter project
• Submit: Upload DoublyLinkedList.java to Lab 2
• Reference:
  • Linked List I
  • Linked List II

Overview

The central purpose of this week’s lab is to give you some hands-on experience writing code that manipulates a linked structure. You will start with already working code (a class called DoublyLinkedList that implements a doubly-linked list as was covered in the topics linked above). The goal is to simplify the code by adding two dummy nodes to your DoublyLinkedList in order to simplify the implementations of many of the class methods. The lab writeup below walks you through this process—you will have the best experience if you follow the instructions in this description carefully!

Preparatory Exercises

1. If you haven’t already, work through the practice problems from the Linked List II topic.
2. Watch the introductory video. Follow along to make sure you have the Checkstyle for Java extension installed and know how to run the tests for the lab.

Introductory Video

Panopto viewer link

Suggested Timeline

• Preparatory Exercises and steps 1 and 2 of Procedure by Wednesday
• Steps 3 to 7 of Procedure by Friday
• Steps 8 to 11 of Procedure by 9pm Monday

Discussion

Anyone attempting to understand the workings of a doubly-linked list understands that it is potentially difficult to keep track of the references. One of the problems with writing code associated with linked structures is that there are frequently boundary cases. These are special cases that must be handled carefully because the typical path through the code makes an assumption that does not hold in the special case. Take, for example, the addFirst method in DoublyLinkedList.java:

    /**
     * Add a value to the head of the list.
     *
     * @pre value is not null
     * @post adds element to head of list
     * 
     * @param value The value to be added.
     */
    public void addFirst(E value) {
        // construct a new element, making it the head
        head = new ListNode(value, null, head);
        // fix tail, if necessary
        if (tail == null) tail = head;
        count++;
    }

The presence of the if statement suggests that sometimes the code must reassign the value of the tail reference. Indeed, if the list is empty, the first element must give an initial non-null value to tail. Keeping track of the various special cases associated with a structure can be very time consuming and error-prone. One way that the complexity of the code can be reduced is to introduce dummy nodes. Usually, there is one dummy node associated with each external reference associated with the structure. In the DoublyLinkedList, for example, we have two references (head and tail); both will refer to a dedicated dummy node:

These nodes appear to the code to be normal elements of the list. In fact, they do not hold any useful data. They are completely hidden by the abstraction of the data structure. They are transparent. This means that from the perspective of someone calling the list’s public methods, the dummy nodes don’t exist—they aren’t counted for size or isEmpty, their values aren’t returned by getFirst or getLast, etc. They serve an entirely internal purpose to simplify the implementation of the data structure.

Because most of the boundary cases are associated with maintaining the correct values of external references and because these external references are now hidden behind their respective dummy nodes, most of the method code is simplified. This comes at some cost: the dummy nodes take a small amount of space, and they must be explicitly stepped over if we work at either end of the list. On the other hand, the total amount of code to be written is likely to be reduced, and the running time of many methods decreases if the special condition testing would have been expensive.

Procedure

In this lab we will modify the DoublyLinkedList class to make use of two dummy nodes: one at the head of the list, and one at the end.

1. Download the starter project (lab2-handout.zip). Unzip it and make sure the files are in their own folder. Open the folder in VS Code.
2. First, note that the constructor for the inner ListNode class takes a value and two references—the nodes that are to be next and previous to the new node. That constructor will also update the next and previous nodes to refer to the newly constructed node.
3. Replace the constructor for the DoublyLinkedList. Instead of initializing head and tail references that are null, you should construct two dummy nodes; one node is referred to by head and the other by tail. Remember that dummy nodes are normal instances of ListNode, just without values. You can use null for the values of these nodes. These dummy nodes should point to each other in the natural way. Because these dummy nodes replace the null references of the DoublyLinkedList class, we will not see any need for null values in the rest of the code. Amen.
4. Check and make any necessary modifications to size, isEmpty, and clear.
5. Now, implement the two important private methods. The method insertAfter takes a value and a reference to a node, previous. It inserts a new node with the value value that directly follows previous. It should be declared private because we are not interested in making it a formal feature of the class. The remove method takes a reference to a node. It should unlink the node from the linked list and return the value stored in the node. You should, of course, assume that the node removed is not one of the dummy nodes. These two methods should be simple with no if statements.
6. The third and final private method, find, takes an index and returns the node located at that index in the list.
7. Using insertAfter and remove, replace the code for addFirst, addLast, getFirst, getLast, removeFirst, and removeLast. These methods should be very simple (perhaps one line each), not counting the check of whether the list is empty for the later four.
8. Next, replace the code for the indexed versions of methods add, remove, get, and set. Each of these should make use of methods you have already written, including find. They should work without any special if statements.
9. Replace the versions of methods indexOf, lastIndexOf, and contains and the remove method that takes a value. Each of these searches for a value in the list and then returns something based on what it finds. You will find that these methods no longer need to compare to null—instead you can check whether you’re at the beginning or end of the list by comparing to head or tail.
10. Update the toString method to appropriately use the dummy nodes.
11. Re-run the tests (see the Introductory Video for how to do this) and make sure they all still pass. The names of the test cases give a good indication of what’s being tested.
12. For an optional challenge, uncomment testInsertAtEndIsEfficient and testInsertNearEndIsEfficient and get them to pass (these two tests will not be part of your grade).

Style

For this lab we will be fairly lenient on style grading, and become more strict later on in the course. You are expected to submit a DoublyLinkedList.java that contains no checkstyle errors. In particular, you must fill out the header comment at the top of DoublyLinkedList.java with your name, email, and a (brief) description of your code. You must also make sure to declare all fields of DoublyLinkedList private.

It is ok to have checkstyle warnings in your submitted code, though I encourage you to fix them if you have time. Avoiding these warnings will be part of your grade on future labs.

Grading

This lab will be graded out of 30 points as follows: