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.
This assignment practices the following course objectives:
Here is the github classrooms link.
Please make sure to read our gradescope submission guide before handing in your assignment!
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.
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!
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:
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>
.
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:
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
Stop and Think (Study Questions):
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:
NodeList
class will be renamed to Node
(following convention)EmptyList
class, we will use null
to denote the end of the list (we'll discuss this in class on Monday 2/8)Node
class will have fields for the content, next Node
, and previous Node
, instead offirst
and rest
int
IList
interface, as outlined belowThe 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 emptyget()
should throw new RuntimeException("Index out of bounds");
if the input index is out of boundsHint: As you write your methods, keep the following guidelines in mind about doubly-linked lists:
start
should be null
end
should be null
start
refers to the first node of the listend
refers to the last node of the liststart
’s and end
’s next
and prev
fields should be null
end.next
and start.prev
are null
; no other node’s next
or prev
fields should be null
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:
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"
.
getNode()
in your testsuite.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"
.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:
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.
In general, the syntax for checkException is this:
If you need to test an exception thrown in a constructor, the syntax is this:
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.
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.
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).
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