---
tags: Homeworks-Summer21
---
# 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 (lists whose contents can be changed by calling methods that 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

## Assignment Link
Here is the [Github classroom link](https://classroom.github.com/a/VWwqSfQr).

If you're having trouble with IntelliJ, check out our [IntelliJ Common Problems](https://hackmd.io/webHvA8yTCqGOAKXYgrI_A) handout.

Please make sure to read [our gradescope submission guide](https://hackmd.io/jC-SEMn_RpiGqMH_EhsDMw) 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`, containing 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 the **Homework 3: Implementation** assignment 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 a name of your choice) with your responses to a couple of [socially-responsible computing questions](https://hackmd.io/n1D51OB8SBWv0tBDlapadA?view#SRC-Assignment-Thinking-about-Data-Integrity) (described at the end of the handout). Instructions are with the questions. Submit this to the **Homework 3: SRC** assignment on Gradescope.

**Note:** If your code does not work with the autograder, you will lose points towards one of the course learning objectives (on writing code against details someone else provided). If you are having trouble with the autograder, please contact the TA’s via hours or Ed.

## The Hunt Continues...
:::spoiler Optional theme material
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!*](https://www.facebook.com/dearblueno/posts/1149706548806219)
:::

## 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<T> {
  T item;
  Node next;
    
  Node(T 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>`.

## Understanding Mutable Lists

When we implemented immutable lists (lecture 5), we implemented a `delete` method. That code is recursive: it walks down the list looking for the item, removing it if/when the item is found. The method code in the `NodeList` class looks as follows:

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

**Task:** Assume someone ran the following program against the code in the notes for lecture 5 (immutable lists). Draw the memory contents (environment and heap) after this code has finished running. Save this in `memory.pdf`

IList L = new EmptyList();
L = L.addFirst(5).addFirst(7).addFirst(9);
L2 = L.delete(5);

## Double the Fun with Doubly-Linked Lists

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 and the `prev`(ious) element. This so-called *doubly-linked list* is what you will implement. An example is shown in the following figure:


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 linked list wrapper class (called `DoublyLinkedList`) will contain both a `start` and `end` field, which are of type `Node`
- The `Node` class will have fields for the content, next `Node`, and previous `Node`.
- The type of the list contents can be anything, not just integers
- Your LinkedList class will implement two interfaces, an `IList` interface similar to the one for immutable lists and an `IListWithNode` interface specific to separate `List` and `Node` classes.

---

### Implementing Core Methods

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

* The `get` method takes as input an `int` representing an index, say `i`, and returns the `i`th 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 negative, 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.

:::warning
**Clarification (June 2, 12:00 pm EDT)**
`reverse` method should be `void` and mutate the list
:::

* 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, and the first instance of said item is then removed 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 `README.txt`.

**Task:** Augment the given `IList` interface to include the above five methods.

**Task:** Write a doubly-linked list class, `DoublyLinkedList`. Your `DoublyLinkedList` class should contain the fields described in the previous section and implement your augmented `IList` interface.

**Required RuntimeExceptions**
The following methods should throw the following exceptions:
- `getFirst()`, `getLast()`, `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

::: warning
**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` object that is in the list, and removes that node from the list. Its return type is `void`.
* You may assume that the inputted `Node` is in the list.

**Task:** Consider the new `removeNode` method. How is `removeNode` different from `remove`? Does it have the same runtime as the `remove` method? Write and explain your answers 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](https://hackmd.io/jC-SEMn_RpiGqMH_EhsDMw) 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>, <package.className, as a String>, <constructor 
    parameters, in order>);

You should test all exceptions thoroughly for this homework.

**Task:** Exhaustively test your `DoublyLinkedList` methods in `Homework3TestSuite.java`. Be sure to setup methods to create `DoublyLinkedLists` for testing, instead of global variables.

## Getting Started
It can help to draw out a doubly-linked list by hand first. Try drawing out the doubly-linked list operations like add, remove, and reverse before trying to write their implementations.

A good place to start would be the methods you are familiar with from singly-linked lists. So once you start undertanding how doubly-linked lists work, try implementing `get`, `removeFirst`, and `removeLast` first.

## FAQ
<!-- **I'm getting an error says "start has private access" or "end has private access". What's happening?**
This might be happening because the start and end fields are private and can't be accessed from outside the class. Do you have methods implemented already that can get the start and end of a list? -->

**For functions that depend on your list not being empty (removeFirst, removeLast, and your getFirst and getLast methods), what should we do for empty list cases?"**
Please throw a Runtime Exception with the message "List is empty". This is also in the Required Runtime Exceptions section of this document.

**What should be in our README.txt file?**
Please include answers to the written questions (seperate from the SRC questions below). Please do not include answers to the study questions (but please still think about the study questions!) In addition, you may include the "usual" components of a README, like any information you'd like your TA to know. Like always, please do not include any identifying information.

**What do I need to test?**
Please test all of the methods in the IList interface to catch the chaffs. See the [Testing](https://hackmd.io/n1D51OB8SBWv0tBDlapadA?both#Testing) section of this file for more information.

## SRC Assignment: Thinking about Data Integrity

**Note: [Here's](https://docs.google.com/document/d/1_qeWEKhVqW22KweCPCY0W5bIuXYHDsHAN-9zQ3BKfdo/edit?usp=sharing) a Google Doc with these questions. You can make a copy of it to use as a template if you'd like.**

**Task:** Read [What is Data Integrity and Why Is It Important?](https://www.talend.com/resources/what-is-data-integrity/) and answer the following questions:

- **Question 1:**
* Provide an example of a system or industry that relies on accurate and consistent data.
* Using the situation you described above, answer these questions:
* Who are the stakeholders of that system/industry?
* Describe at least two ways in which *specific types* of data integrity could be violated in this situation.
* How could/would the stakeholders be adversely affected by those violations? (2-3 sentences)

- **Question 2:** Describe:
* One way that using mutable lists could put data integrity at risk (1-2 sentences)
* One way that using immutable lists could help preserve data integrity (1-2 sentences)
* Bonus question (optional): Can you think of a way that mutable lists could help preserve data integrity, or that immutable lists could put data integrity at risk? If so, describe your thoughts!

- **Question 3:** Look at the [products page](https://www.talend.com/products/data-integrity-governance/) for Talend’s website. How does the knowledge that Talend sells data integrity software affect your understanding of the article, if at all? (~2 sentences)

**Task:** Read [Ownership Or Rights: What’s the path to achieving true agency over data?](https://www.adalovelaceinstitute.org/blog/ownership-or-rights-whats-the-path-to-achieving-true-agency-over-data/), 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:
We grade your responses according to [this rubric](https://docs.google.com/spreadsheets/d/1kyjing8hVDCSVyHuiy0MB_9LjyCA9HWjKu_s85E6Iig/edit?usp=sharing).

For guidance on SRC responses, take a look at our [annotated Homework 0 sample response](https://docs.google.com/document/u/1/d/1wu_hKL2jwnYAfC8vMFmqMJ6Q-gp3zNBYNDiHmUCXY9s/edit?usp=drive_web&ouid=103120773613617146887). You'll be getting your HW0s back shortly, so be sure to take a look at your feedback and incorporate it for this homework.

Please leave any feedback about this assignment (or any SRC-related feedback in general) through our [anonymous feedback form](https://forms.gle/GjAZdBk8uvt6H2i46).

**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 CS18 document by filling out the (mostly) [anonymous feedback form](https://cs.brown.edu/courses/cs018/feedback)!*