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, 2/25 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.

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.

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 tail 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> tail(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

If you would like more information about functional lists, see the handout What is a linked list?. Note that this handout provides method signatures using the C programming language, but you should be able to understand it by substituting in the appropriate Java function definitions.

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: Data Structures and Advanced Programming, Spring 2019

Powered by Bootstrap 4 Github Pages