Deques

Designing and analyzing double-ended queues.

Deque interface
1. Reference implementation
Design and implement
1. ArrayDeque
2. LinkedDeque
Commit and push code to GitLab
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.

In this project, we’ll spend most of our time working in two following folders: src/main/java/deques, which contains the application logic for this project, and src/test/java/deques, which contains the testing code for this project.

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 include 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 whether 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.

Commit and push code to GitLab

Once you’re satisfied with your implementations, the last step is to commit and push your code to your private Git repository so that others (such as your TAs) can review your work. Unlike collaboration tools like Google Docs that automatically save your changes as you make them, Git requires you to manually stage, commit, and then push your changes. This is helpful for programming because we often want to try a change to help debug or explore a possible feature, but we might not be immediately ready to share it with others.

Whenever you want to share your work with the TAs:

From the menu bar, select Git | Commit.
In the new tool window that appears on the left, select the files you would like to stage.
Write a descriptive commit message and then click Commit. A descriptive commit message helps your collaborators quickly understand the contents of your changes without having to dive into the details.
From the menu bar, select Git | Push.
Finally, refresh your private repository page in CSE GitLab to ensure that the commits have been shared.

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. We recommend making a table to display your results concisely.

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.

By default, the RuntimeExperiments class is annotated with the tag @Disabled right above the class header. Comment-out the @Disabled line of code and run the deque tests. 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 specific operation, find the RuntimeExperiments class nested at the bottom of the DequeTests class. Then, change the call to deque.addLast(size) in the inner-most loop to the operation you’d like the test. Finally, change the following deque.removeLast() call to perform the opposite operation. For example, if you would like to measure the runtime of removeLast, then the opposite operation would be addLast.

Enabling RuntimeExperiments class will significantly increase the overall time it takes to run tests. GitLab is a shared resource for the entire class. If you mistakenly commit a change enabling RuntimeExperiments, cancel the job in GitLab and correct things by making a new commit that disables the RuntimeExperiments class.

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