Skip to content

Linked Deque HW

The Java Collections Framework provides a Deque interface (pronounced like "deck", short for double-ended queue). Deques allow for insertion and removal at either end of the collection, and so can be used in place of either stacks or queues.

The Java Collections Framework provides a number of concrete classes that implement the Deque interface, including ArrayDeque and LinkedList. Your goal for this homework will be to provide an alternate implementation based on a doubly-linked list.

Illustration of a doubly-linked list with four nodes.

In this implementation, each node in the linked list will have a reference to the next node and the previous node. The deque itself will have references to the head (first) and tail (last) nodes. This will allow us to add and remove elements from both ends of the deque in constant time.

You will also be asked to write tests that both verify the correctness of your implementation and demonstrate your understanding of the deque's behavior.

Starter Code

Download the following files:

  • AbstractDeque.java – (FINISHED) Abstract base class that simplifies Deque implementation.
  • LinkedDeque.java – (UNFINISHED) This is the file you will be implementing.
  • TestLinkedDeque.java – (UNFINISHED) This is the file you will be using to test your implementation.

Instructions

Implement each of the remaining methods in LinkedDeque.java. As you complete each method, write and run tests in TestLinkedDeque.java to verify that your implementation is correct. Make sure to also submit early and often to Gradescope to check your progress.

Read through the following sections to understand how the deque should behave and how the linked list should be implemented.

Visualizing the LinkedDeque

It's almost always helpful to draw a picture and visualize how the linked list works and how the references are updated.

Offering

Think about what happens when we offerLast. There are two cases to consider.

  1. When the deque is empty:

    Illustration of adding a single node to an empty deque.

    Note that both head and tail should reference the new node.

  2. When there is at least one element in the deque:

    Illustration of adding a node at the end of a doubly linked list that already has one node.

    In the second case, what references need to be updated?

Polling

Consider this LinkedDeque:

Doubly-linked list with four nodes S P O T.

If we call pollFirst(), this should return 'S' and then the deque would look like this:

Illustration showing the same list with the S Node removed.

Take note of the differences between the two images. Specifically, what references need to be updated?

If we then call pollLast(), this should return 'T' and the deque would look like this:

Illustration showing the same list with the T Node removed.

One Element Left

Don't forget about the special case when the deque has only one element:

Illustration showing the process of removing the P node when it is the only node remaining

Here, you'll need to update both head and tail.

Hints

For poll methods, don't leave any references to the Node you remove!

  • For example, if I had [A, B, C] and called pollLast(), tail should be pointing to node B, and node B's .next should be null.
  • Otherwise, the stale reference will prevent the garbage collector from recovering node C.

For the iterator's remove method, here are a few tips:

  • Don't worry about current. The last reference already points to the item you need to remove. Work with last.
  • There are a few special cases to consider:
    1. What if last points to the first item in the list (aka head)? Do you have a method you can call that removes the first item? Call it.
    2. What if last points to the last item in the list (aka tail)? Do you have a method you can call that removes the last item? Call it.
    3. Otherwise, you are removing from the middle. You are guaranteed that last is surrounded by two other nodes. Think about the references you need to change here.
  • After removing last, don't hold a reference to it anymore! Set last to null.

Submission and Grading

Submit LinkedDeque.java and TestLinkedDeque.java to Gradescope. Your code must pass your own tests to receive credit.

Full credit for your unit tests will require 100% statement coverage of LinkedDeque.java.

Gradescope will run additional tests on your code that are not included in TestLinkedDeque.java. Style checks will be run on LinkedDeque.java, but not on TestLinkedDeque.java.

The assignment will be graded as follows:

Statement Coverage for Student-Developed Unit Tests 40%
Instructor Gradescope Functionality Tests 50%
Gradescope Style Checks10%