CSCI 136 - Fall 2019

Data Structures & Advanced Programming

Home | Bill's Lectures | Sam's Lectures | Labs | Handouts & Problem Sets | Links | CS@Williams

Lab 5: The Genius of Dummies

The central purpose of this week's lab is to give you some hands-on experience writing code that manipulates a linked structure. Your task is to complete the Laboratory Assignment from Section 9.10 of your text, entitled Lists with Dummy Nodes (pages 215-217). You will start with already working code (a class called LinkedList that extends the structure5 class DoublyLinkedList). The goal is to simplify the code by adding two "dummy" nodes to your LinkedList in order to simplify the implementations of several of the class methods. The Laboratory Assignment in Section 9.10 walks you through this process—you will have the best experience if you follow the instructions in that description carefully!

Pre-lab: Step 0

Before lab, please do the following:

• Read Chapter 9 up to and including 9.5 Implementation: Doubly Linked Lists, and bring your questions to class.
• Study the code in the LinkedList.java file before coming to lab, and think carefully about how you might modify the various methods as described in the assignment. A copy of the file will also be provided in your starter repository.
• Whether or not you decide to work with a partner, please fill out the following Google form by Monday at 4:00 pm. Please submit exactly once per pair! Please remember to fill out the form on time, even if you are working alone.

Lab Assignment

Complete Laboratory Assignment 9.10, which begins on page 215 of Bailey. The starter file LinkedList.java will be included in your team's private GitHub repository in addition to a starter file with sample tests. The tests are not exhaustive, so please add additional tests as you consider the various edge cases.

In addition, answer the five Thought Questions on page 217 of your text in a file called PROBLEMS.md, and submit it with the rest of your code this week.

Lab Deliverables

For this lab, please submit the following:

• Your well-documented source code in LinkedList.java
• The sample testing file, TestLinkedList.java supplemented with additional tests as you feel appropriate. The sample file has some tests to get you started, but it does not test all edge cases.
• A PROBLEMS.md file that contains answers to the five warm-up/thought questions.

If you worked with a partner, submit one folder with your collaborative solution.

As in all labs, you will be graded on design, documentation, style, and correctness. Be sure to document your program appropriately: include pre/post conditions and assertions where appropriate. We will also be looking at how well you organize your code. Whenever you see yourself duplicating functionality, consider moving that code to a helper method. There are several opportunities in this lab to simplify your code by using helper methods. Think carefully!

Submitting Your Lab

As you complete portions of this lab, you should commit your changes and push them. Commit early and often. When the deadline arrives, we will retrieve the latest version of your code. If you are confident that you are done, please use the phrase "Lab Submission" as the commit message for your final commit. If you later decide that you have more edits to make, it is OK. We will look at the latest commit before the deadline.

• Be sure to push your changes to GitHub.
• Verify your changes on Github. Navigate in your web browser to your private repository on GitHub. It should be available at https://github.com/williams-cs/cs136-dummylists-USERNAME. You should see all changes reflected in the files that you push. If not, go back and make sure you have both committed and pushed.

We will know that the files are yours because they are in your git repository. Do not include identifying information in the code that you submit. We grade your lab programs anonymously to avoid bias. In your README.md file, please cite any sources of inspiration or collaboration (e.g., conversations with classmates). We take the honor code very seriously, and so should you. Please include the statement "I am the sole author of the work in this repository." in the comments at the top your Java files.