Homework 3: Linked Lists

Due Monday, October 7 @ 8:00pm on Gradescope

1. Introduction

In this assignment, you’ll be constructing two different kinds of linked lists: A singly linked list and a doubly linked list. The singly linked list is very similar to the one we developed in class. When you’re done, you’ll have a pretty good start on two different fully-fledged generic linked list classes!

Download a pre-prepared Eclipse Project hw3.zip and import it into Eclipse using these instructions. You will make all of your changes inside the Java files in this project.

For this assignment you have 5 submissions. That is not a lot for an assignment of this size, so you will need to test thoroughly before submission. After you have used your submissions, you may continue to submit, but your submission will be penalized 4 points for every extra submission. (So, your 6th submission receives a -4, your 7th submission a -8, etc.)

Please note that you will likely need to use one of those submissions to properly determine the exact exceptions that you will need to raise in error situations. You may also need some if your efficiency is borderline and you need to submit a few times. Make sure to save submissions for these purposes.

2. The Singly Linked List

The first part of this assignment is to build a singly linked list, as described in class. You are free to use any of the demo code we wrote in class to help you here. (We wrote some of these methods in class...) The methods you need to write are as follows:

public SinglyLinkedList()

A basic constructor.


public String toString()

A basic toString().


public void addHead(ListType value)

Add an item to the head of the list.


public void add(ListType value)

Add an item to the end of the list.


public int size()

Determine how many items are in the list


public boolean isEmpty()

Determine whether or not the list is empty.


public boolean contains(ListType value)

Determine if a specified value is in the list.


private SingleListNode<ListType> nodeAtIndex(int index)

Optional Helper Function: Get the node at the position in the list specified by index.

Throws an IndexOutOfBoundsException with an appropriate message if index is out of range.


public ListType get(int index)

Get an item at a specified index from the list.

Throws an IndexOutOfBoundsException with an appropriate message if index is out of range.


public void add(int index, ListType value)

Adds a node containing value at the specified position in the list, if such a position can be added to the list.

Throws an IndexOutOfBoundsException with an appropriate message if index is out of range.


public ListType remove(SingleListNode<ListType> node)

Remove the specified node from the list.

Throws a NoSuchElementException (with no extra message) if the node is not in the list.


public void remove(ListType value)

Remove the first instance of an item with a given value from the list.

Throws a NoSuchElementException (with no extra message) if the node is not in the list.


public ListType remove(int index)

Remove the node at the position in the list specified by index, if such a position is in the list, and returns the data value that was at that location.

Throws an IndexOutOfBoundsException with an appropriate message if index is out of range.


public void removeLast(ListType target)

Removes the node containing the last occurrence of a value in the list.

Throws a NoSuchElementException if the node is not in the list.


public void removeAll(ListType value)

This method removes every node in the list that contains a particular value. Realize that the target can occur multiple times and anywhere in the list! This method does nothing if the target is not in the list.

This method must run in linear time, O(N), or you will lose points!


3. Doubly Linked List

The second part of this assignment is to build a doubly linked list, a list where each node has both a next and and a previous pointer:

This allows for a few optimizations:

The new methods you need to write are as follows:

public DoublyLinkedList()

A basic constructor.


public String toString()

A basic toString(), both forward and reverse.

It should return a string with two lines: The list both forward and backward. For example:
List Content Forwards: A –> B –> C
List Content Backwards: C –> B –> A


private void addAfter(DoubleListNode<ListType> prevNode, ListType value)

Adds a node containing value after the specified position in the list. (The new node should be after prevNode in the list)

This method must run in constant time, O(1), or you will lose points!


private void addBefore(DoubleListNode<ListType> postNode, ListType value)

Adds a node containing value before the specified position in the list. (The new node should be before postNode in the list)

This method must run in constant time, O(1), or you will lose points!


public void addHead(ListType value)

Add an item to the head of the list.

This method must run in constant time, O(1), or you will lose points!


public void add(ListType value)

Add an item to the end of the list.

This method must run in constant time, O(1), or you will lose points!


public int size()

Determine how many items are in the list


public boolean isEmpty()

Determine whether or not the list is empty.


private DoubleListNode<ListType> nodeContaining(ListType value)

Helper Function: Get the node of the first instance of a particular value in the list.

Throws a NoSuchElementException (with no extra message) if the node is not in the list.


public boolean contains(ListType value)

Determine if a specified value is in the list.


private DoubleListNode<ListType> nodeAtIndex(int index)

Helper Function: Get the node at the position in the list specified by index.

Throws an IndexOutOfBoundsException with an appropriate message if index is out of range.


public ListType get(int index)

Get an item at a specified index from the list.

Throws an IndexOutOfBoundsException with an appropriate message if index is out of range.


public void add(int index, ListType value)

Adds a node containing value at the specified position in the list, if such a position can be added to the list.

Throws an IndexOutOfBoundsException with an appropriate message if index is out of range.


public ListType remove(DoubleListNode<ListType> node)

Remove the specified node from the list. You may assume the node is in the list.

This method must run in constant time, O(1), or you will lose points!


public void remove(ListType value)

Remove the first instance of an item with a given value from the list.

Throws a NoSuchElementException (with no extra message) if the node is not in the list.


public ListType remove(int index)

Remove the node at the position in the list specified by index, if such a position is in the list, and returns the data value that was at that location.

Throws an IndexOutOfBoundsException with an appropriate message if index is out of range.


public void removeLast(ListType target)

Removes the node containing the last occurrence of a value in the list.

Throws a NoSuchElementException (with no extra message) if the node is not in the list.

Note: You need to be intelligent here while searching. If you don’t search correctly, then you might not pass the autograder, even if your method works.


public SinglyLinkedList<ListType> asSinglyLinkedList()

Return a copy of this list transformed into a singly-linked list.

This method must run in linear time, O(N), or you will lose points.


4. Note on Efficiency

Some of the methods listed above have efficiency requirements. The Autograder will test the efficiency of those methods to ensure your implementation meets the requirements.

To test your complexity, we time how long the method takes to run on a list with 50,000 elements. Next, we time and run it again with a list twice that size. We then divide the two times to get your speed ratio.

If your method is \(O(N)\) then your speed ratio should be \(\approx 2\). (Because if we double the input, the time to run should double as well.)

If your method is \(O(1)\) then your speed ratio should be \(\approx 1\). (Because if we double the input, the time to run should not change.)

This method of determining your speed ratio is not an exact science, and your speed ratio will vary a little bit between two runs, even if your code hasn’t changed. It should not change drastically, however.

If your code is much slower than it should be, such as \(O(N^2)\), then the time to complete an operation on a 50,000-item list will be very high. As such, the testcase will simply timeout after 4 seconds and you’ll see a message indicating that a timeout occurred. This means your solution is not efficient enough.

5. Grading and Submission

There are multiple parts of the grading of this assignment:

  1. For the first 90 points, your submission will be auto-graded on Gradescope.

  2. For the next 5 points, your submission will be manually graded to check for good implementation methodologies. (Did you use a good approach to solving the problems?)

  3. For the next 5 points, your submission will be manually graded to check for good testcases that you include in the main method. (Do you have 2-3 of your own testcases for each method, and do they all execute automatically?)

  4. Your code will also be checked for style. The parts of style that can be checked automatically (things like spacing, indentation, the use of CamelCase, etc.) are automatically checked by the autograder. Other parts of style, such as choosing good variable names, will be checked manually. Autograded style guide violations can result in, at most, -10 points. Manually checked style guide violations can result in, at most, -5 points.

You will submit your program to Gradescope. Log in to the system and you will see the homework. Once there, you need to submit a zip file containing your code. Lucky for you, however, Eclipse can create this zip file for you. Check out these instructions for exporting. On Gradescope, you’ll submit that exported zip file. On the page that follows your submission, you will see your live score (out of 90). If you receive a lower score than you expect, you can click on the score to see the feedback from the autograder.

5.1. Testcases

You need to write at least two testcases for each of the methods listed above. (This is a lot of test cases for you to write.) One of those testcases should test basic functionality, and the other should test an error condition of some sort. All of your testcases should be in the LinkedListTester class included with the skeleton code. You must follow the model of our testcases from previous assignments (meaning you print when you start, print the results (pass/fail) when you finish, etc.) Additionally, you must comment each testcase with a note describing what it tests.

6. Restrictions

You may only use the following Java libraries in this assignment:

java.util.NoSuchElementException

7. Important Notes