Programming

Deque ADT¶

Deques can do everything that both stacks and queues can do. Specifically, any deque implementation must have the following operations:

Unlike lists, we do not allow clients to add items to the middle of a deque. We do, however, allow clients to access elements in the deque—this method primarily exists to make it easier for us to test the implementations.

To get started, open deques/src/deques in IntelliJ. Take a look at the Deque.java file to explore the interface in more detail. There are a few important things to note here:

• The interface methods defined there include comments with extra notes on edge cases and preconditions.
• The Deque interface extends Java’s Queue interface—the Deque interface inherits all the methods defined by Java’s Queue interface, and any implementations of Deque must define those methods.
• In AbstractDeque.java, we define the relationships between our Deque interface and Java’s Queue; this means that subclasses of AbstractDeque can implement the functionality of a deque using our Deque interface, but also provide the functionality of a queue through Java’s Queue interface for free.

Debugging ArrayDeque¶

Explore the Circular ArrayDeque Demo¹ below to see how the ArrayDeque works: it works similarly to the ArrayQueue class presented in lecture.

We’ve provided a nearly-working ArrayDeque implementation that is intentionally buggy, along with a failing test in BaseDequeTests.confusingTest that causes the bug to emerge. Your task is to fix the flaw in the implementation.

Follow the debugging cycle:

1. Develop a hypothesis about what the root cause is based on what you know about the problem.
   • Skim through the code in ArrayDeque.java to learn the layout of its methods and fields.
   • Run the provided tests.
   • Read through ArrayDeque again, focusing on methods relevant to the failing tests.
2. Reproduce the issue in a minimal working example.
   • Write and run simple unit tests to help determine what exactly is going wrong. The failing test that we provide makes it hard to debug since it calls many methods. You’ll want to write some simpler tests to figure out what exactly is going wrong.
     • As an aside, it may be useful to write these new tests in BaseDequeTests so that you can later reuse them for LinkedDeque.
3. Make productive changes based on the root cause discovered.
   • Make sure that the unit tests you’ve written pass after you’ve fixed the issue.
4. If there are more issues, return to step 1.

Tips¶

• This should only involve changing at most 5 lines of code. If you find yourself having to rewrite large swaths of code, you are likely just redoing it without catching the original bug.
• Do not spend more than an hour debugging! It’s easy to lose track of time and get stuck in a deep hole when debugging. Please come to office hours, and remember to take breaks!
• Use the jGRASP visualizer in addition to IntelliJ’s debugger! It’s very useful for showing the current state of small programs.

• Java’s own stack trace is usually pretty informative about what errors occur. For example, the following stack trace shows that an addLast call is responsible for a NullPointerException:

  java.lang.NullPointerException
      at deques.LinkedDeque.addLast(LinkedDeque.java:44)
      at deques.BaseDequeTests.size_afterAddToOppositeEnds_is2(BaseDequeTests.java:126)
  

Implementing LinkedDeque¶

• add, remove, and size must run in constant time (operations must not involve any looping or recursion). Note: size is provided for you.
• get must use iteration, not recursion.
• The amount of memory that your program uses at any given time must be proportional to the number of items. For example, if you add 10,000 items to the deque, and then remove 9,999 items, the resulting data structure should use memory similar to a deque with 1 item. Do not maintain references to items that are no longer in the deque.
• Your implementation must use sentinel nodes and adhere to the associated invariants.

Consider working out what your LinkedDeque will look like on paper before you try implementing it in code. If you can find a willing partner, have them give commands while you draw out the process. It may also help to review LinkedIntList from P0.

Sentinel Nodes¶

Sentinel nodes are a type of node that never has any null references and doesn’t contain any meaningful data. This allows us to simplify how we handle linked nodes as we no longer need to check if a node is null before accessing it. When used in linked data structure, we can avoid null pointer exceptions by pointing our front and back fields to them, even with an empty data structure.

Invariants¶

A data structure’s invariants are a set of internal requirements maintained by the data structure: they must be true before and after any of the data structure’s operations. A doubly-linked deque with sentinel nodes should include the following invariants:

• The front field always references the front sentinel node, and the back field always references the back sentinel node which allows us to skip null checks when accessing front or back.
• The sentinel nodesfront.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, respectively.
• The nodes in your deque have consistent next and prev fields. For example, if a node curr has a curr.next, we expect to see curr.next.prev == curr.

Since invariants are always meant to be true in a data structure, we can also explicitly check a data structure’s invariants to determine whether it’s behaving correctly. Our unit tests will extensively check the invariants to ensure that your deques always remain in a valid state.

Tips¶

• Make sure you think carefully about what happens if the data structure goes from empty, to some non-zero size (e.g., 4 items) back down to zero again, and then back to some non-zero size. This is a common oversight.
• If you find your code failing the grader-only tests on Gradescope, you should try to recreate the test locally so that you can run and debug it.
• If your first try goes badly, don’t be afraid to scrap your code and start over. The amount of code for this part isn’t actually that much. (Our solution adds about 40 lines of code to the skeleton.)
• Take things a little at a time. Writing tons of code all at once is going to lead to misery and only misery. Likewise, if you’ve been stuck debugging for more than an hour, take a break and work on something else.

Submission¶

If you’re working in a group, the partner who submits must add the other partner as a group member on Gradescope. Here’s a video demonstrating that process. You’ll also need to re-add group members whenever you resubmit to the same assignment, even if you already did so on a previous submission.