Deques

Designing and analyzing double-ended queues.

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

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 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, we welcome collaboration and teamwork in this class. Our primary rule is that we ask that you do not claim to be responsible for work that is not yours. If you get a lot of 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 two Canvas submissions: one individual writeup and a link to your src/deques folder on GitLab that addresses all the green callouts in the Design and Implement section, and one video-recorded individual presentation that addresses all the green callouts in the Analyze and Compare section.

The project instructions contain a lot of details to provide context, clarify common confusions, and help students get started. Your Canvas submisisons 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 4 minutes and should include your voiceover. (Your video is appreciated but not necessary.)
Your 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.

Your job in all the projects in this course is to help your team determine the most promising direction for further investment of software engineering resources. Therefore, your program implementation does not need to satisfy all correctness standards to complete this project. The goal of this course is to learn how to design program specifications in the first place; your implementations are prototypes used to evaluate potential approaches, not complete solutions that would actually be used in real applications.

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.

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 two 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 test/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 TAs, 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.

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.

Run all the tests for both ArrayDeque and LinkedDeque in IntelliJ and include a screenshot in your writeup showing a summary of the results. If the implementations pass all the test cases, explain an interesting bug that you addressed or avoided during your programming process. If the implementations do not pass all the test cases, explain what you think could be causing the problem.

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 each of addFirst, addLast, removeFirst, and removeLast in both ArrayDeque and ArrayListDeque. Give a Big-Theta bound for each runtime, and explain the runtime of each implementation in a couple sentences.

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.

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.

Compare your plots for the addLast method between all three implementations: ArrayListDeque, ArrayDeque, and LinkedDeque. Then, identify an operation that should show a significant difference between ArrayListDeque and the ArrayDeque, and modify the RuntimeExperiments class so that it measures this difference. Compare your new plots to confirm that ArrayDeque is more efficient than ArrayListDeque for your operation.

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 292 to the operation you’d like the test. Change deque.removeLast() on line 297 to the opposite of what you’re testing. For example, if you want to test removeFirst on line 292, use addFirst on line 297 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. ↩