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.

If you're having trouble with IntelliJ, check out our IntelliJ Common Problems handout.

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, 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 (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…

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!

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:

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 →

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 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 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.

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

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

When the linked list is empty,
- start should be null
- end should be null
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 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

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 section of this file for more information.

SRC Assignment: Thinking about Data Integrity

Note: Here's 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? 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 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?, 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.

For guidance on SRC responses, take a look at our annotated Homework 0 sample response. 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.

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!