Try   HackMD

Homework 3: Doubly-Linked Lists

In lecture, we've been working on ways to implement "Linked Lists". This name comes about because we "link" objects together into a chain of nodes (there are other ways to implement lists, which we will study in upcoming lectures). In particular, we've been looking at how to implement mutable lists (where the list contents as seen through a variable name change by virtue of calling methods to manipulate the list).

In lecture, we've talked about how to implement methods to add items to both mutable and immutable lists. In this assignment, we turn to thinking about deleting items from lists. How should this work at the level of objects in memory? How do we implement it? And how do we do so with efficient time performance?

As we discuss deletion, we'll find that it makes sense for the nodes in the list to store not only a reference to the next/rest node, but also to the previous node. This kind of list is called a "doubly-linked list". Understanding and implementing doubly-linked lists is the essence of this assignment.

Learning Objectives

This assignment practices the following course objectives:

  • Implement doubly-linked lists from soup to nuts!
  • State the key structural and performance characteristics of core data structures (here, lists)
  • Understand what makes a data structure mutable or immutable at the level of implementation
  • Comment code effectively with Javadocs
  • Develop a collection of examples and tests that exercise key behavioral requirements aspects of a problem
  • Write programs that can compile and run against a provided interface
  • Write programs that behave as expected based on a provided description or collection of test cases
  • Correctly determine the run-time complexity of an algorithm

Here is the github classrooms link.

Please make sure to read our gradescope submission guide before handing in your assignment!

Handing In

After completing this assignment, the following solution files should be in your sol directory, all as part of the sol package:

  • IList.java containing public interface IList<T>
  • IListWithNode.java containing public interface IListWithNode<T>
  • Node.java containing public class Node<S>
  • DoublyLinkedList.java containing public class DoublyLinkedList<T>
  • Homework3TestSuite.java containing public class Homework3TestSuite, which thoroughly tests your doubly-linked list implementation.
  • memory.pdf, containg the memory diagram you drew in the first task.
  • README.pdf or README.txt, with your answers to the questions that we ask you to put in a README file.

To hand in your files, submit them to Gradescope. Once you have handed in your homework, you should receive an email, more or less immediately, confirming that fact. If you don’t receive this email, try handing in again, or ask the TAs what went wrong.

You will separately submit a PDF with your responses to a couple of socially-responsible computing questions (described at the end of the handout). Instructions are with the questions. Submit this to the Homework 3: SRC submission on Gradescope.

Note: If your code does not work with the autograder, you will be penalized. If there are any complications, please contact the TA’s via hours or Piazza.

Theming (Optional): The Hunt Continues

While searching for information about Blueno's hidden treasure, a thought pops into your mind: perhaps he left clues in his journal, Dear Blueno. The only problem is that it's a mess! Thousands of entries detail the quality of Ratty chicken, CS professors, and 🚀📈, with no organization whatsoever! Fortunately, you remember a data structure from class that may help you sort through the posts and look for clues: a doubly-linked list! With this in mind, you open Blueno's journal and read the inscription written on the inside of the front cover

As I scribble these words, I'm right on the brink
My treasure you'll find, if these lists you do link!
Here's my preamble,
For you to unscramble
Those questionable posts that make you think!

Note: Overview of Generic/Parameterized Types

When you used Java’s LinkedList class in Lab, you supplied the type of the list elements in angle brackets, as in LinkedList<Integer>. For this assignment, we want you to create lists that can similarly take contents of any type, not just the ints that we have been doing in class. Fortunately, this doesn’t involve a lot of work.

Just as you provide a type in angle brackets to use LinkedLists, you can annotate a class or interface with a type parameter (such as T), as in the following example:

class Node<S> { S item; Node next; Node(S item, Node next) { this.item = item; this.next = next; } }

To create an object of this class, you would just supply the type, as you do when using the built in linked lists. For example, Node<Integer>.

Double the Fun with Doubly-Linked Lists

The starter code from lectures 7 and 8 included a list method to remove an element from a list. That code is recursive: it walks down the list looking for the item, removing it if/when the item is found. The code for the NodeList class looks as follows:

public IList remEltOnce(int remelt) { if (remelt == this.first) { return this.rest; } else { return new NodeList(this.first, this.rest.remEltOnce(remelt)); } }

Task: Assume someone ran the following program against our code from the end of lecture 8 (linked to the lectures page). Draw the memory contents (environment and heap) after this code has finished running. Save this in memory.pdf

LinkList L = new LinkList(); L.addFirst(5).addFirst(7).addFirst(9); L.remEltOnce(9)

Stop and Think (Study Questions):

  • What are the strengths and limitations of this approach to removing elements?
  • How might our code have to be different to prevent creating the new NodeList objects without adding any fields to our objects?

You don't have to turn in your answers, but these would be great study question to discuss with other students or in conceptual hours. They get at the point of this assignment.

In practice, we implement remove-style operations cleanly by adding a new field to our NodeList objects so that they refer both to the next element (what we have called rest until now) and the prev(ious) element. This so-called doubly-linked list is what you will implement. An example is shown in the following figure:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Figure 1: The doubly-linked list (12, 99, 37). Boxes with X in them denote null, and boxes with black circles are the next and prev fields of Nodes.

The doubly-linked list that you implement for this assignment will differ from the lists we've built in class in a couple of ways:

  • the NodeList class will be renamed to Node (following convention)
  • Instead of an EmptyList class, we will use null to denote the end of the list (we'll discuss this in class on Monday 2/8)
  • The Node class will have fields for the content, next Node, and previous Node, instead offirst and rest
  • The type of the list contents can be anything, not just int
  • you will add methods to the IList interface, as outlined below

Implementing Core Methods

The goal of this part of the assignment is to augment the IList interface and provide a DoublyLinkedList class to include get, reverse, removeFirst, removeLast, and remove methods:

  • The get method takes as input an index, say i, and returns the ith item in the list. You should assume 0-indexing where the first item in the list has index 0. If there is an index that is too large, or if the list is empty, you should throw a RuntimeException with the string “Index out of bounds”.

  • The reverse method reverses the order of the items in the list that it is called on.

  • The removeFirst method removes the first item in the list and returns it (the item). If there are no items in the list, it throws a RuntimeException with the string “List is empty”.

  • The removeLast method removes the last item in the list and returns it (the item). If there are no items in the list, it throws a RuntimeException with the string “List is empty”.

  • The remove method will take as input an item, the first instance of which it proceeds to remove from the list. It returns a boolean indicating whether or not the operation was successful: i.e., true if the item was found and removed, or false if not.

Task: Consider how the remove operation for doubly-linked lists is different than from singly linked lists. Write 3-5 sentences in your README explaining the significant differences.

Task: Before beginning to code, compare and contrast the optimal runtimes of each method with one another. Which methods do we expect to take longer with larger inputs? Which methods do we expect to take the same amount of time no matter the input? Write your thoughts in your README.

Task: Augment the given IList interface to include these five methods.

Task: Write a doubly-linked list class, DoublyLinkedList. Your DoublyLinkedList class should implement your augmented IList interface.

Required RuntimeExceptions
The following methods should throw the following exceptions:

  • getFirst(), getLast(), get(), removeFirst(), and removeLast() should throw new RuntimeException("List is empty"); if the list is empty
  • get() should throw new RuntimeException("Index out of bounds"); if the input index is out of bounds

Hint: As you write your methods, keep the following guidelines in mind about doubly-linked lists:

  1. When the linked list is empty,
    • start should be null
    • end should be null
  2. When the linked list is nonempty,
    • start refers to the first node of the list
    • end refers to the last node of the list
    • if the list contains exactly one node, then both start’s and end’s next and prev fields should be null
    • if the list contains more than one node, then only end.next and start.prev are null; no other node’s next or prev fields should be null

Implementing Additional Methods

The goal here is to further enhance the functionality and robustness of your doubly-linked list class, DoublyLinkedList. We would like our doubly-linked list class to also implement the secondary interface IListWithNode provided in the source code.

It's important to remember that a class can implement as many interfaces as you desire but can only extend a single class. We want the DoublyLinkedList class to continue to implement the IList interface, but would also like it to implement our secondary interface.

Implementing the secondary interface will allow the DoublyLinkedList class to include getNode and removeNode methods:

  • The getNode() method takes as input an item and returns the Node in the list containing that item. If getNode() doesn't find that item in the list, it throws an IllegalArgumentException with the string "item not present".
    • You do not need to test getNode() in your testsuite.
  • The removeNode method takes as input a Node, and removes that node from its list. It returns void.

Task: Consider the new removeNode method. Does it have the same runtime as the remove method? Explain why or why not in your README.

Task: Modify DoublyLinkedList to implement the IListWithNode. Your doubly-linked list class should still implement the IList interface.

Required RuntimeExceptions
The following methods should throw the following exceptions:

  • getNode() should throw an IllegalArgumentException with the string "item not present".

Testing

You should submit Homework3TestSuite.java to the Homework 3: Testing assignment on Gradescope. See our gradescope submission guide for an explanation on how we are grading your tests, and how you can use the Testing assignment on Gradescope to get a better understanding of the assignment.

As usual, you must exhaustively test your DoublyLinkedList methods! However, because we are working with mutable data, you should create a setup method in your test class, like you did in Lab 3. A setup method takes in nothing and returns an object that you will perform tests on; in this case, a DoublyLinkedList. You know the contents of this list, because the method makes a list, exactly as you want, and returns it. This allows you to safely perform tests. We use setup methods because we want our tests to pass regardless of what order the test methods are run in.

If we were running tests on a DoublyLinkedList that was a global variable in our test class, switching the order of our testAdd and testRemove methods would be disastrous. But if we create a new DoublyLinkedList in each test method, we won’t run into any issues!

You do not need to test your getNode() method in your testsuite.

Task: Think about how this plays into our understanding of mutability and make sure you understand why a setup method is an effective solution.

Here’s an example of what a setup method could look like:

/** * A setup method for a basic list * @return a basic linked list */ public IList<Integer> setupBasicList() { IList<Integer> dll = new DoublyLinkedList<Integer>(); dll.addFirst(1); dll.addFirst(5); dll.addFirst(10); return dll; // A doubly linked list with elements 10, 5, 1, in that order } // A method to test get public void testGet(Tester t) { IList<Integer> testList = setupBasicList(); t.checkExpect(testList.get(0), 10); ... }

The contents of this list are up to you, but you should make several setup methods so that you can test methods such as remove and reverse. Remember to check edge cases!

As a reminder, here is how to test exceptions.

// say you have a runtime exception somewhere in your code: public class ErrorObject { public void alwaysFail(int i, String s, boolean t) { throw new RuntimeException("informative error message"); } } // and then somewhere in your testing class, you should have this checkException(): t.checkException(new RuntimeException("informative error message"), new ErrorObject(), "alwaysFail", 1, "hello", false);

In general, the syntax for checkException is this:

t.checkException(<new object of exception type>, <new object of class that calls the method you want to test>, <method name, as a String>, <method parameters, in order>);

If you need to test an exception thrown in a constructor, the syntax is this:

t.checkConstructorException(<new object of exception type>, <class name, as a String>, <constructor parameters, in order>);

You should test all exceptions thoroughly for this homework.

Task: Write a class to exhaustively test your DoublyLinkedList methods (except the methods given to you in the src folder). Be sure to setup methods to create DoublyLinkedLists for testing, instead of global variables.

SRC Assignment: Thinking about Data Integrity

Task: Read What is Data Integrity? Definition, Best Practices & More (skip over the section on “Data Integrity for Databases”) [5 minute read], then, in a few sentences each, answer all questions listed below.

  • Question 1: Provide some examples of systems/industries that rely on accurate and consistent data.
  • Question 2: Propose a concrete example scenario of how data integrity could get violated, which could then lead to an adverse impact on a person or organization.
  • Question 3: In class, we’ve been talking about mutable vs immutable lists. Does the need for data integrity suggest that we should always use mutable lists? Why or why not?

Task: Read Ownership Or Rights: What’s the path to achieving true agency over data? [12 minute read], then answer all the questions listed below each item, using one short paragraph per question (approx. 3-5 sentences).

  • Question 4: Pavel surveys experts’ opinions on data ownership and what it means to have agency over one’s data. Identify two specific claims or statements in the article that changed how you think about your agency over data (either now or when you first encountered those ideas). What specifically changed for you? (i.e., what preconceptions did you hold, and what had you never thought about?)
  • Question 5: If you could have asked one followup question to the panelists, what would it have been, and why?

Grading:

Homework 0 gave you some practice with the rubric that we use for grading your SRC responses during the course. Like Homework 0, you will get feedback about how well you are meeting the rubric points and about the content of your response more generally for this assignment’s SRC component.

How to Hand In: Submit your work as a single PDF file on Gradescope to the “Homework 3: SRC” submission portal. Do not include your name or other identifying fields anywhere in your response. This, like all assignments, is subject to the course collaboration policy.


Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CS 18 document by filling out our anonymous feedback form