Deques

Designing and analyzing double-ended queues.

Project Setup
Deques
Deque interface
1. Reference implementation
Design and implement
1. ArrayDeque
2. LinkedDeque
Analyze and compare
1. Asymptotic analysis
2. Experimental analysis

Project Setup

If you are running into errors with running BrowserHistory make sure you are using JDK 17.

If you are running into errors with running MapServer make sure you move your resources folder. Husky Maps is a web app for mapping the world, searching for places, and navigating around Seattle. The next three projects, after Deques, will help implement it (MapServer)!

Deques

In Java, every variable has a data type like int, boolean, String, List, or the name of any interface or class defined by a programmer. Data types combine representation and functionality.

Representation: The specific way that data is stored or represented within the computer.
Functionality: The actions or operations that determine how we can use the data type.

For example, we can have an int x = 373 and a String s = "373". Although they both hold similar content, their representation and functionality are very different. In Java, an int can only represent integer numbers within a certain range, whereas a String represents data as a sequence of characters. The functionality of the plus operator differs for x + x versus s + s.

Abstract data types (ADT) are data types that do not specify a single representation of data and only include a specification for the functionality of the data type. In Java, abstract data types are often represented using interfaces like List, Set, or Map. Java provides implementations or specific representations of each interface through classes like ArrayList, TreeSet, or HashMap.

A deque (pronounced “deck”) is an abstract data type representing a double-ended queue. Deques are linear collections (like lists, stacks, and queues) optimized for accessing, adding, and removing elements from both the front and the back. Deques differ from lists in that they do not allow elements to be added or removed from anywhere except for the front or the back. This restriction might make it seem like deques are much less useful than lists. Indeed, any problem you can solve using a deque you can also solve using a list!

But usefulness is not the only metric for determining the quality of a program. Imagine you’re on a team engineering a web browser, and you’re working on addressing a performance problem that has been reported in the browser history feature. When a user visits a web page, the page visit is recorded in the browser history by adding the link and the date of visit to the end of an ArrayList. But users are reporting that the option to clear-out the history of pages that were visited over 3 months ago is unusually slow.

In this project, we’ll study this performance problem by designing and analyzing different approaches to implement a deque. By the end of this project, students will be able to:

Design and implement node-based and array-based data structures.
Analyze and compare runtimes using asymptotic and experimental analysis.

Can I work with someone else on this project?

Although this project requires an individual submission, you may find it useful to discuss overarching ideas with your classmates. Our primary rule is that we ask that you do not claim to be responsible for work that is not yours. If you get some help from someone else or from an online resource, cite it. I believe that there is a lot of value in learning from others so long as you do not deprive yourself (or others) of the opportunity to learn.

We are comfortable doing this because each submission in this class comes in the form of a video that you record. Your video is a demonstration of everything that you learned throughout the process of working on an assignment. Our goal is for students to support each other and find community through this course. The real advantage of taking a course on-campus at a university is to be able to connect with others who share common interests in learning.

What am I submitting at the end of this project?

Satisfactory completion of the project requires one Canvas submission including: a video-recorded individual presentation, some kind of visually-organizing structure, such as slides or a document and a link to your src/main/java/deques folder on GitLab that addresses all the green callouts.

The project instructions contain a lot of details to provide context, clarify common confusions, and help students get started. Your Canvas submissions only need to address tasks that are described in green callouts like this one.

Your video presentation should meet the following requirements:

Your presentation should not be much longer than 8 minutes (9 minutes maximum) and should include your voiceover. (Your video is appreciated but not necessary.)
Your video presentation should include some kind of visually-organizing structure, such as slides or a document.
After submitting to Canvas, add a submission comment linking to your slides or document and a link to your src/main/java/deques folder on GitLab. Remember to commit and push to Gitlab and check that the associated status for your latest Pipeline is a green checkmark!

Students are expected to follow Washington state law on the Student Conduct Code for the University of Washington. In this course, students must:

Indicate on assignment submissions any assistance received, including materials distributed in this course.
Not receive, generate, or otherwise acquire any substantial portion or walkthrough for an assignment.
Not aid, assist, attempt, or tolerate prohibited academic conduct in others.

In your visually-organizing structure shown during the video presentation, you must cite any sources you used, including lecture materials, section materials, and collaboration with peers. If you used any kind of computer technology to help prepare your project deliverable, include the queries and/or prompts.

Submitted work that is not consistent with sources may be subject to the student conduct process.

Deque interface

Interfaces are a useful way to indicate common methods that will be provided by different implementations (Java classes). For example, List is an interface with implementations such as ArrayList and LinkedList. Deques are like lists but without the capability to add, remove, or get elements from anywhere except for the front or the back. For testing purposes, we included a method to get any element by its index in the deque.

Implementations of Deque must provide the following methods:

void addFirst(E element): Adds an element of type E to the front of the deque.
void addLast(E element): Adds an element of type E to the back of the deque.
E get(int index): Gets the element at the given index, where 0 is the front, 1 is the next element, etc.
boolean isEmpty(): Returns true if deque is empty, false otherwise.
E removeFirst(): Removes and returns the element at the front of the deque.
E removeLast(): Removes and returns the element at the back of the deque.
int size(): Returns the number of elements in the deque.

The interface defines a default method isEmpty that returns size() == 0.

Reference implementation

We’ve provided a reference implementation that will help us evaluate the performance problem with ArrayList. The ArrayListDeque class implements Deque using an ArrayList. The class maintains a single field called list that stores all the elements in the deque, where the i-th element in the deque is always stored at list[i].

How does ArrayListDeque relate to ArrayList, List, ArrayDeque, and Deque?

ArrayListDeque is a class (implementation) for the interface (abstract data type) Deque. In other words, Deque just defines some functionality; ArrayListDeque specifies how that functionality is actually achieved.

ArrayListDeque uses an ArrayList, which is an implementation of the List interface.

ArrayListDeque is not particularly related to ArrayDeque in concept. They just happen share a similar-sounding name. It would be more appropriate to read ArrayListDeque as the following sentence: a class that uses an ArrayList to implement Deque functionality.

Design and implement

Unlike your prior programming courses, the focus of this course is not only to build programs that work according to specifications but also to compare different approaches and evaluate the consequences of our designs. In this project, we’ll compare the ArrayListDeque reference implementation to two other ways to implement the Deque interface: ArrayDeque and LinkedDeque.

Make sure to pass all the tests for ArrayDeque and LinkedDeque, push your code to Gitlab, and check that the associated status for your latest Pipeline. If the implementations do not pass all the test cases, explain in your video what you think could be causing the problem.

ArrayDeque

An array deque is like an ArrayList, but different in that elements aren’t necessarily stored starting at index 0. Instead, their start and end positions are determined by two fields called front and back.¹

To step back in the slides, click on the slides and press the left arrow key or the backspace key. On touchscreens, swipe left to advance and swipe right to step back.

We’ve provided an ArrayDeque class that includes a bug, and four failing test cases that cause the bug to emerge. Identify and fix the bug in the ArrayDeque class by changing at least 2 lines of code. Follow the debugging cycle to address the bug.

Review ArrayDeque to see how its methods and fields work together to implement Deque.
Run the ArrayDequeTests class inside the src/test/java/deques folder.
Read the test result and review the stack trace (the chain of calls that caused the exception).
Review ArrayDeque again, this time focusing on methods most relevant to the failing test. You can open the DequeTests file and drag the tab for a side-by-side view.
Based on what you know about the bug, develop a hypothesis for the cause of the problem.

For example, we might hypothesize that the problem is caused by the newIndex variable inside the resize method going outside the bounds of the newData array. Gathering information that can confirm or deny this hypothesis can help us zero-in on the problem, leading us to generate another hypothesis or a potential fix to the bug. Debugging is the process of exploring hypotheses, generating potential fixes, trying them out, and learning more information about the problem until we finally identify the root cause of the bug.

It’s easy to lose track of time and get stuck in a deep hole when debugging. Come to office hours, chat with other students, or return after taking a break! We also strongly recommend students to read the confusingTest case carefully and write a more minimal test case that reproduces the problem using a simpler sequence of instructions.

To develop a hypothesis, we can use the debugger to pause the program at any point in time. Watch this video by one of our past instructors, Iris Zhou, to learn more about how to debug your deques in IntelliJ. At each step, compare your thinking to the state of the debugger. If it’s a bit hard to understand the state of the debugger, try switching over to the jGRASP tab while debugging the program.

Explain your hypothesis for the bug in the ArrayDeque class and the lines of code that you changed to address the hypothesis that help to maintain the integrity of the codebase.

LinkedDeque

Implement the LinkedDeque class with the following additional requirements:

The methods addFirst, addLast, removeFirst, and removeLast must run in constant time with respect to the size of the deque. To achieve this, don’t use any iteration or recursion.
The amount of memory used by the deque must always be proportional to its size. If a client adds 10,000 elements and then removes 9,999 elements, the resulting deque should use about the same amount of memory as a deque where we only ever added 1 element. To achieve this, remove references to elements that are no longer in the deque.
The class is implemented with the help of sentinel nodes according to the following invariants. Use the doubly-linked Node class defined at the bottom of the LinkedDeque.java file.

Invariant: A property of an implementation that must be true before and after any methods. For example, in an ArrayList, the i-th element in the list is always stored at elementData[i].
Sentinel node: A sentinel node is a special node in a linked data structure that doesn’t contain any meaningful data and is always present in the data structure, even when it’s empty. Because we no longer need to check if the current node is null before accessing it, we can simplify the number of conditions that are needed to implement LinkedDeque methods. We recommend using two sentinel nodes to simplify your code, providing access to both the front and the back of the deque.²

A LinkedDeque should always maintain the following invariants before and after each method call:

The front field always references the front sentinel node, and the back field always references the back sentinel node.
The sentinel nodes front.prev and back.next always reference null. If size is at least 1, front.next and back.prev reference the first and last regular nodes.
The nodes in your deque have consistent next and prev fields. If a node curr has a curr.next, we expect curr.next.prev == curr.

Write down what your LinkedDeque will look like on paper before writing code! Drawing more pictures often leads to more successful implementations. Better yet, if you can find a willing partner, have them give some instructions while you attempt to draw everything out. Plan-out and double-check what you want to change before writing any code. The staff solution adds between 4 to 6 lines of code per method and doesn’t introduce any additional if statements.

To assist in debugging, we’ve provided a checkInvariants method that returns a string describing any problems with invariants (at the time the method is called), or null if there are no problems. You can use this by adding debugging print statements to help you verify a hypothesis. But it can be tedious editing code, moving the line around, and then running it again just to call checkInvariants at a different point in time. A better way is by Using Evaluate Expression and Watches with IntelliJ. This allows you to pause the program at any point in time and call checkInvariants().

Lastly, if your first try goes badly, don’t be afraid to scrap your code and start over.

Trace through the code for the test confusingTest, starting after the comment on line 199 that says “Test that removing and adding back is okay”, with a focus on justifying how your LinkedDeque implementation for addLast and removeFirst produce the correct behavior.

Remember to use the deque that has been initialized to [-1, 0, 1, 2, 3, 4]. You can justify addLast and removeFirst by tracing the code for those methods once you reach those methods in your trace of confusingTest.

Analyze and compare

Asymptotic analysis

In computer science, simpler solutions are typically preferred over more complicated solutions because they’re less likely to contain subtle bugs. ArrayListDeque provided a simple solution to implementing a deque, but exhibited significantly degraded performance on some methods. How does ArrayDeque compare to ArrayListDeque?

Give a best case and worst case asymptotic runtime analysis for addLast and removeFirst in both ArrayDeque and ArrayListDeque, by giving a Big-Theta bound for each case’s runtime, and reasoning the runtime of each implementation in a couple sentences.

Remember that this means you will want to give a best case Θ bound & reasoning and worst case Θ bound & reasoning for each of the two methods. It may be helpful to look over the corresponding Java documentation for any data structures/methods you utilized as a client.

Experimental analysis

At the bottom of the DequeTests class, you’ll find a nested class called RuntimeExperiments. This nested class defines the code that will be used to evaluate the program’s runtime by measuring how long it takes to run on your computer.

To let RuntimeExperiments run, make sure to comment out the @Disabled line before it. Make sure to keep @Nested. Once you are done running RuntimeExperiments, please uncomment the @Disabled line to ensure that our pipeline to check your tests will work!

Run the deque tests and open the test results. For each implementation’s RuntimeExperiments, open it to see the average time it takes to make a single call to addLast on a deque that already contains size number of elements.

Copy and paste each result into its own Desmos graphing calculator to plot all the points. You can grab the entire result outputted and copy it straight into desmos!

Compare your plots for the addLast method between all three implementations. Then, modify the RuntimeExperiments class to compare new plots from ArrayDeque and ArrayListDeque for the removeFirst method, and explain that ArrayDeque is more efficient than ArrayListDeque for this operation. Please draw from your asymptotic analysis to inform all of your explanations, as well as how the experimental analysis being a more average case may affect this.

To modify the RuntimeExperiments class to measure the runtime of a new operation (addFirst, removeFirst, removeLast), go to the RuntimeExperiments class, located at the bottom of the DequeTests file. Then, change deque.addLast(size) on line 340 to the operation you’d like the test. Change deque.removeLast() on line 345 to the opposite of what you’re testing. For example, if you want to test removeFirst on line 340, use addFirst on line 345 to revert the Deque to its previous state.

Josh Hug. 2019. cs61b sp19 proj1 slides. ↩
Josh Hug. 2019. cs61b lec5 2019 lists3, dllists and arrays. ↩