---
tags: Homeworks
---
# 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

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

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`, 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!*](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<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)

:::info
**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:


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 of`first` 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 `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 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

::: 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`, 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](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>, <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](https://digitalguardian.com/blog/what-data-integrity-data-protection-101) (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?](https://www.adalovelaceinstitute.org/blog/ownership-or-rights-whats-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](https://docs.google.com/spreadsheets/d/1URfKsX1Q0zSQg4pwW_VDOCjthgQiTvGuJ65W-972A90/edit?usp=sharing) 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](https://forms.gle/ym89rAZyBk8Hg3LNA)