Skip to content

Lab: Linked Deque

This lab will have you implement a double-ended queue (deque) using a doubly-linked list, which is able to function as both a stack and a queue.

In this implementation, each node in the linked list will have a reference to the next node AND the previous node. The deque will also 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:

These files are in the labs.linkeddeque package. Make sure to put them in appropriate directories, e.g.:

src/
└── labs/
    └── linkeddeque/
        ├── AbstractDeque.java
        ├── LinkedDeque.java
        └── TestLinkedDeque.java

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 offer an element to the end of the deque. There are two cases to consider.

  1. When the deque is empty:

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

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

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

Polling

Consider this LinkedDeque:

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

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:

One Element Left

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

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, Java will not actually delete node C and your linked deque will still think it exists!

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

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

Gradescope will run additional tests on your code that are NOT included in TestLinkedDeque.java.

Style is not graded for this lab.