Lab 4: Linked Lists

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 (Bailey), entitled Lists with Dummy Nodes (pp. 215—217). You will start with already working code (a class called LinkedList that extends the structure5 class DoublyLinkedList). The goal is to change 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

Due Monday, 3/2 by 5pm.

  • We will assign you a partner for this lab. If you would like to opt out of certain pairings (up to 3), fill out the following Google Form. If you are happy to be partnered with any classmate, you need not fill out the form.

PRE-LAB: Step 1

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.

Lab Assignment

  1. Complete Laboratory Assignment 9.10, which begins on p. 215 of Bailey. The starter file LinkedList.java will be included in your team’s private GitHub repository in addition to a file, LinkedListTests.java, that includes tests. The tests are not exhaustive, so please add additional tests as you consider the various edge cases.
  2. In the comment block for each method in your LinkedList class, provide the running time (in Big-O notation) for each method, along with a brief justification.
  3. 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.

Style

checkstyle requirements:

This week, we are expanding checkstyle to encourage you to write modular and reusable code. Let’s first motivate that decision, and then describe the new checkstyle rule.

As a programmer, you should never type the same code over and over again. That would be a waste of your time. The ability to copy/paste useful code makes this tempting, but it is still very bad practice! When you copy code, you copy errors. If you ever fix those errors, you have to remember to fix them in every location. This “fixing” rarely happens. Trust us. We’ve been there.

So what should you do instead? You should write a helper method! Whenever you find yourself writing the same code more than once (it could be a common loop, searching a data structure, computing an equation) you should refactor that code into a method. Then you can call that method many times, but only ever have to fix bugs in one place.

Similarly, if you find yourselves writing a function that is very long, that is problematic. The long function can probably be broken into smaller parts that can then be composed to solve a larger problem. Bonus: you can now reuse those parts to solve other problems.

Breaking long functions into byte-size chunks also has the benefit of making your code easier to read and debug: by isolating functionality inside independent units, you can convince yourself that each of those units is correct in isolation, and then you can more easily convince yourself that the larger problem is correct.

Since we cannot easily check for copy/pasted code, we will use checkstyle to encourage concise methods.

The checkstyle tool will report an [ERROR] if your program has a method that is longer than 40 lines (excluding whitespace and single-line comments). This new rule is in addition to previous style requirements.

In total, checkstyle will enforce the following guidelines:

  • All class variables that are not final must be declared private or protected (i.e., no public member variables unless they are constants).
  • All public methods must include a “Javadoc” comment (starts with /** and ends with */; it should include descriptions of the function, the arguments, and any pre/post conditions).
  • No methods should be longer than 40 lines (exluding whitespace and single-line comments).

To run checkstyle, you would type the following command at the terminal:

$ ./checkstyle

The ./ is peculiar to Unix: it tells the terminal to look for the checkstyle program in the current directory. This command will run checkstyle on every Java program in your directory. To run checkstyle on a specific Java file, type:

$ ./checkstyle SomeFile.java

javac requirements:

In addition to checkstyle, we will continue to enforce proper use of Java generics.

  • Compiling your code with javac must not produce the following message: 
    Note: YourProgram.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

This message tells you how to get more information. Recompile your program as follows (replace with the appropriate file name):

$ javac -Xlint:unchecked YourProgram.java

The output will give you details about the issue.

To fix this problem, make sure that you specify type parameters for every generic class, both when declaring the variable’s type and when instantiating an object. For example, to create a Vector that stores Integer objects, one would type:

    Vector<Integer> intVec = new Vector<Integer>();

Lab Deliverables

By the start of lab, you should see a new private repository called cs136lab04_dummylists-{USERNAMES} in your GitHub account (where USERNAMES is replaced by your usernames).

For this lab, please submit the following:

cs136lab04_dummylists-{USERNAMES}/
    README.md
    PROBLEMS.md
    MISTAKES.md
    LinkedList.java
    TestLinkedList.java

The LinkedList.java file contains starter code, and you should write all of your functions inside that file. The TestLinkedList.java file contains a convenient main method pre-populated with a variety of helpful tests that should help you get started.

As with 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/cs136lab04_dummylists-USERNAMES 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 "We are the sole authors of the work in this repository." in the comments at the top of your Java files.

The squeaky wheel gets the grease

We are always looking to make our labs better. Please submit answers to the following questions using the anonymous feedback form for this class:

  1. How difficult was this assignment on a scale from 1 to 5 (1 = super easy, …, 5 = super hard).
  2. Did you take advantage of any TA help hours or professor office hours?
  3. If you did go, was the assistance helpful? If you did not go, why not?
  4. What part of this assignment did you like best? Why?
  5. Is there one question about computers / computer science that you wish you had the answer to? What is that question?

Bonus: Functional Linked List

An alternative way to implement a linked list is in the functional style associated with the LISP programming language. For the bonus, implement this functional list. You may earn up to 10 bonus points for this problem, however your total score will not exceed 100%.

A functional list has an elegant, recursive definition. A list is either:

  • null, or
  • a ListNode<E>, where E is a generic type.

The head of a functional list is the first element (which has type E).

The rest of a functional list is the entire list after the element that contains the head (which has type ListNode<E>).

Your ListNode<E> class should have two instance variables:

  1. An instance variable of type E called data.
  2. An instance variable of type ListNode<E> called next.

Both of these variables should be declared final. Note that the fact that both variables are final will influence your constructor design.

A functional list is a singly linked list where the next variable of each ListNode<E> points to the next ListNode<E> in the list. The last ListNode<E> should point to null.

A ListNode<E> also has the following methods:

  1. public static <E> ListNode<E> prepend(E e, ListNode<E> ls)

    which prepends a new ListNode<E> to the list ls and returns the new node. Note that prepend should not make new copies of any of the ListNode<E> elements. Furthermore, it should be possible for the user to create a new list by calling prepend with ls set to null.

  2. public static <E> E head(ListNode<E> ls)

    which returns the first element (of type E) in the list.

  3. public static <E> ListNode<E> rest(ListNode<E> ls)

    which returns the entire list after the element that contains the head (of type ListNode<E>).

  4. public String toString()

    which returns a String representation of the list. This representation should be of the form [ e1, e2, ..., en ] In other words, the returned String should begin and end with square bracket characters, and each element should be separated by a comma and a space. You should call toString() on each data element (of type E) in the list to get its own String representation.

  5. public static <E> int length(ListNode<E> ls)

    which returns an int representing the number of ListNode<E>s in the list.

  6. public static <E> ListNode<E> reverse(ListNode<E> ls)

    which returns a new list with all of the elements of the list in reverse order. This method will need to make copies of the ListNode<E> elements.

  7. Finally, provide a main method that

    • Reads in a text file specified by the user,
    • adds each word to a list, one at a time,
    • reverses the list,
    • and then prints the list back out.

    After compiling, you should be able to run this program with a text file like so:

    ListNode < file.txt

Be sure to commit your implementation to your repository in a file called ListNode.java.

Bonus: Mistakes

Did you find any mistakes in this writeup? If so, add a file called MISTAKES.md to your GitHub repository and describe the mistakes using bullets. For example, you might write

* Where it says "bypass the auxiliary sensor" you should have written "bypass the primary sensor".
* You spelled "college" wrong ("collej").
* A quadrilateral has four edges, not "too many to count" as you state.

You will receive 1 bonus point on this assignment for each mistake we are able to validate.

  • CSCI 136, Spring 2020

Powered by Bootstrap 4 Github Pages