Introduction

In this project, we will build implementations of a “Double Ended Queue” using both linked lists and arrays. You will create exactly three Java files: LinkedListDeque.java, ArrayDeque.java, and Deque.java, with public methods listed below.

Unlike project 0, we will provide relatively little scaffolding. In other words, we’ll say what you should do, but not how.

For this project, you will be working with a partner! Please carefully read the Policy on Collaboration and Cheating to see what this means exactly.

We strongly encourage you to switch to IntelliJ for this project. While it’s not absolutely required, you will have a better time. The ability to visually debug your code can be incredibly useful, it’s also nice to have a development environment that catches syntax errors as you are typing, and it avoids the need to type javac and java (or pressing arrow keys) a bajillion times. If you need a refresher on how to import a project, you can follow the Intellij setup guide

Additionally, we will be enforcing style. You must follow the style guide or you will lose points on the autograder.

Getting the Skeleton Files

Partnerships are required for this project, please see the Collaboration Guide for more information.

For this project, you should choose a partner to work with, and you should be working collaboratively in your shared repository, which should have a name of the form su19-proj1-s***-s***. If you haven’t set this up yet, please see the instructions in Lab 5 to do so.

If you find yourself faced with a strange text editor or a merge conflict, see the Git Weird Technical Failures guide for how to proceed.

Once you’ve successfully merged, you should see a proj1 directory appear with files that match the skeleton repository.

If you get some sort of error, STOP and either figure it out by carefully reading the git guide or seek help in lab or on Piazza. You’ll potentially save yourself a lot of trouble vs. guess-and-check with git commands. If you find yourself trying to use commands recommended by Google like force push, don’t. Don’t use force push, even if a post you found on Stack Overflow says to do it!

The only provided files in the skeleton are LinkedListDequeTest.java and ArrayDequeTest.java. These files provide examples of how you might write tests to verify the correctness of your code. We strongly encourage you try out the given tests, as well as to write some of your own.

The Deque API

Deque (usually pronounced like “deck”) is an irregular acronym of double-ended queue. Double-ended queues are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either its front or its back). Here is a definition from cplusplus.com.

Specifically, any deque implementation must have exactly the following operations:

  • public void addFirst(T item): Adds an item of type T to the front of the deque.
  • public void addLast(T item): Adds an item of type T to the back of the deque.
  • public boolean isEmpty(): Returns true if deque is empty, false otherwise. (This method should be deleted and migrated to Deque.java during Part 3. (The API Checker will fail on this until you get to that point.))
  • public int size(): Returns the number of items in the deque.
  • public void printDeque(): Prints the items in the deque from first to last, separated by a space. Once all the items have been printed, print out a new line.
  • public T removeFirst(): Removes and returns the item at the front of the deque. If no such item exists, returns null.
  • public T removeLast(): Removes and returns the item at the back of the deque. If no such item exists, returns null.
  • public T get(int index): Gets the item at the given index, where 0 is the front, 1 is the next item, and so forth. If no such item exists, returns null. Must not alter the deque!

Your class should accept any generic type (not just integers). Check out these slides from lecture 2 for a quick crash-course on generics.

Project Tasks

1. Linked List Deque

Create a file called LinkedListDeque.java in your project directory.

As your first deque implementation, you’ll build the LinkedListDeque class, which will be linked list based.

Your operations are subject to the following rules:

  • add and remove operations must not involve any looping or recursion. A single such operation must take “constant time”, i.e. execution time should not depend on the size of the deque.
  • get must use iteration, not recursion.
  • size must take constant time.
  • 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 size should be more like a deque with 1 item than 10,000. Do not maintain references to items that are no longer in the deque.

Implement all the methods listed above in “The Deque API” section.

In addition, you also need to implement:

  • public LinkedListDeque(): Creates an empty linked list deque.
  • public T getRecursive(int index): Same as get, but uses recursion.

You may add any private helper classes or methods in LinkedListDeque.java if you deem it necessary.

While this may sound simple, there are many design issues to consider, and you may find the implementation more challenging than you’d expect. Make sure to consult the lab on doubly linked lists, particularly the section on sentinel nodes. You are not allowed to use Java’s built in LinkedList data structure (or any data structure from java.util.*) in your implementation.

2. Array Deque

Create a file called ArrayDeque.java in your project directory.

As your second deque implementation, you’ll build the ArrayDeque class. This deque must use arrays as the core data structure.

For this implementation, your operations are subject to the following rules:

  • add and remove must take constant time, except during resizing operations.
  • get and size must take constant time.
  • The starting size of your array should be 8.
  • 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, you shouldn’t still be using an array of length 10,000ish. For arrays of length 16 or more, your usage factor should always be at least 25%. For smaller arrays, your usage factor can be arbitrarily low.

Implement all the methods listed above in “The Deque API” section.

In addition, you also need to implement:

  • public ArrayDeque(): Creates an empty array deque.

You may add any private helper classes or methods in ArrayDeque.java if you deem it necessary.

We strongly recommend that you treat your array as circular for this exercise. In other words, if your front pointer is at position zero, and you addFirst, the front pointer should loop back around to the end of the array (so the new front item in the deque will be the last item in the underlying array). This will result in far fewer headaches than non-circular approaches. See the slides from Lecture 2 for more details.

Correctly resizing your array is very tricky, and will require some deep thought. Try drawing out various approaches by hand. It may take you quite some time to come up with the right approach, and we encourage you to debate the big ideas with your fellow students or TAs. Make sure that your actual implementation is by you alone.

3. Deque Interface

Before beginning this part, read about Interfaces in the section below.

This last task is going to be a little tedious, but it won’t take long.

Create an interface in a new file named Deque.java that contains all of the methods that appear in both ArrayDeque and LinkedListDeque. In IntelliJ, use “New->Java Class”. IntelliJ will assume you want a class, so make sure to replace the class keyword with interface.

Create this interface and add all the methods. For the isEmpty() method, give it a default implementation, which returns true if the size() is 0. Notice that since both your LinkedListDeque and ArrayDeque probably use an implementation like this, now that we have this default implementation, you should delete the duplicate implementations inside of the two aforementioned concrete classes.

Modify your LinkedListDeque and ArrayDeque so that they implement the Deque interface by adding implements Deque<T> to the line declaring the existence of the class. Please be sure to use T instead of another generic type parameter name, for the sake of the autograder. Add @Override tags to each method that overrides a Deque method.

About Interfaces

Motivation for Interfaces

You’ve probably been told before that for a certain class in college you need to have a computer. You probably weren’t told what kind of computer you had to have, what company it was from, how much RAM it had, even whether it was a Mac or a PC, you were just told you needed “a computer”. This is because the specifics of the machine you owned didn’t matter, all that mattered is what it could do. For the purposes of that class, it might have been important that this computer could:

  • Go on the internet
  • Use a word processor
  • Print things If it could do those three things, it was good enough. Actually what type of computer it was or what else it could do didn’t matter.

This is the fundamental idea of interfaces (and polymorphism in a broader sense) in Java. Sometimes requiring what an object can do is more important that requiring it be a certain type of object. What follows now is a more technical example of why interfaces are useful.

Say we have the following two classes:

public class Computer {
    ...
    public String lookUpDefinition(String wordToLookUp) {
        // Do some stuff and returns a definition found on Google
    }
    ...
}

public class Dictionary {
    ...
    public String lookUpDefinition(String wordToLookUp) {
        // Flip through some pages and return a definition
    }
    ...
}

You want to make a class ConfusedStudent, which represents a student who doesn’t know what the word ‘syzygy’ means, and who wants to look it up:

public class ConfusedStudent {
    ...
    static String whatDoesSyzygyMean (? wordKnower){
        return wordKnower.lookUpDefinition("syzygy");
    }
    ...
}

Notice that there is a question mark above. What type should we specify wordKnower as belonging to? We could make the ? a Computer, but then we couldn’t look the word up in a Dictionary (which isn’t true). We could make the ? a Dictionary, but the same problem would occur. We could replace ? with Object and be able to pass either in, but then the compiler would complain because, generally speaking, an Object doesn’t have a lookUpDefinition method since not all Objects are able to look up definitions.

Before we might have fixed this problem by making one a subclass of the other, but that doesn’t make sense here, there really isn’t any is-a relationship between Computers and Dictionarys.

Interfaces to the rescue! Let’s define an interface:

public interface ThingThatKnowsWords {
    public String lookUpDefinition(String wordToLookUp);
}

And let us rewrite the three classes above so they look like this:

public class Computer implements ThingThatKnowsWords {
    ...
    public String lookUpDefinition(String wordToLookUp) {
        // Do some stuff and returns a defintion found on Google
    }
    ...
}

public class Dictionary implements ThingThatKnowsWords {
    ...
    public String lookUpDefinition(String wordToLookUp) {
        // Flip through some pages and return a definition
    }
    ...
}

public class ConfusedStudent {
    ...
    static String whatDoesSyzygyMean (ThingThatKnowsWords wordKnower){
        return wordKnower.lookUpDefinition("syzygy");
    }
    ...
}

Our problem is solved! We’re allowed to do this, because Java lets us choose an interface as the static type of a method parameter, and this way we can use either a Dictionary or a Computer (since they both implement ThingThatKnowsWords)!

Interfaces are a programmer’s life

When a class implements an interface, it is giving a guarantee that it can perform a certain functionality, as defined by the interface it implements. You’ll find that the idea of an interface is actually very central to software engineering in general. When you’re asked to implement a set of methods to perform some specific task, that’s implementing an interface. Often when working on a group project, a good approach is to split the work into parts that will be integrated together at the end. In order to allow work to be done in parallel, it is important to establish what each part will accomplish and how it will interact with other parts so that they can be merged together without issue. Establishing what each of these parts will do and how they interact with other parts is essentially treating each part as an interface. Using interfaces is all about not knowing the actual implementation, but instead utilizing the input-to-output, defined behavior given by the interface; implementing an interface to specification like you are asked for assignments and projects is about making sure the program you write under some interface gives the correct output for all inputs.

Testing

Testing is an important part of code writing in industry and academia. It is an essential skill that can prevent monetary loss and hazardous bugs in industry, or in your case, losing points. Learning how to write good, comprehensive unit tests, and developing a good habit of always testing code before shipping are some core objectives of CS 61B.

We have been learning about testing in lab. Here, we have provided you a very simple sanity check, LinkedListDequeTest.java, as well as a template for more tests in ArrayDequeTest.java. To use the sample LinkedListDequeTest.java testing file, you must uncomment the lines in the sample tests. Only uncomment a test once you have implemented all of the methods used by that test (otherwise it won’t compile). When testing your project, remember you can use the debugger and visualizer from inside IntelliJ!

It is for your benefit to write more comprehensive tests for both LinkedListDeque and ArrayDeque before submitting. Having local tests that you have written and understand are far more useful because they provide you with more instantaneous feedback, and also they can be debugged more easily using your IntelliJ tools. Note, passing the given tests in LinkedListDequeTest.java does not necessarily mean that you will pass all of the autograder tests or receive full credit. You will submit both of your tester files, but besides the standard style check, we will not be performing autograder tests on your tests.

Here are some suggested tests that you might want to write for yourself:

  • LinkedListDeque
    • Do some insertions/deletions that get you in and out of several empty list situations, in order to ensure that these edge cases behave well with your sentinel implementation.
  • ArrayDeque
    • Test filling up just before resizing to ensure proper operation.
    • Test resizing: fill to N + 1, ensure still correct.
    • Test resizing up and down by adding a large amount and then removing a large amount.
    • Advanced: Fuzz test, which means performing a large number of random insertions/deletions to your deque and ensuring correct behavior. After you have a working LinkedListDeque, you can write a test that ensures that the same operations on your LinkedListDeque and your ArrayDeque have the same results. You can use Math.random() and be sure to provide a random seed so that your results are reproducible. Also make sure not to add/remove each with 50% probability since the deque would likely stay small; bias the probability to favor insertions so that your deque will change size over time.

Deliverables

  • LinkedListDeque.java
  • LinkedListDequeTest.java
  • ArrayDeque.java
  • ArrayDequeTest.java
  • Deque.java

Tips

  • If you’re stuck and don’t even know where to start: Lab 6 contains great hints for the LinkedListDeque and Lecture 2 has slides to help you with ArrayDeque.

  • Take things a little at a time. Writing tons of code all at once is going to lead to misery and only misery. If you wrote too much stuff and feel overwhelmed, comment out whatever is unnecessary.

  • If your first try goes badly, don’t be afraid to scrap your code and start over. The amount of code for each class isn’t actually that much (my solution is about 130 lines for each .java file, including all comments and whitespace).

  • For ArrayDeque, consider not doing resizing at all until you know your code works without it. Resizing is a performance optimization (and is required for full credit).

  • Work out what your data structures will look like on paper before you try implementing them in code! If you can find a willing friend, have them give commands, while you attempt to draw everything out. Try to come up with operations that might reveal problems with your implementation.

  • 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.

  • Sentinel nodes make life much easier, once you understand them.

  • Circular data structures make life easier for both implementations (but especially the ArrayDeque).

  • Consider a helper function to do little tasks like compute array indices. For example, in my implementation of ArrayDeque, I wrote a function called int minusOne(int index) that computed the index immediately “before” a given index.

  • Consider using the Java Visualizer (which you installed in Lab 3) to visualize your Deque as you step through with the debugger. The visualizer is an icon of a blue coffee cup with an eye, and is the tab next to the “Console” tab in the debugger panel). See the CS 61B plugin guide if you can’t figure out how to get the visualizer to show. The visualizer will look something like this: java_visualizer

Frequently Asked Questions

Q: How should I print the items in my deque when I don’t know their type?

A: It’s fine to use the default String that will be printed (this string comes from an Object’s implementation of toString(), which we’ll talk more about later this semester). For example, if you called the generic type in your class Jumanji, to print Jumanji j, you can call System.out.print(j).

Q: I can’t get Java to create an array of generic objects!

A: Use this:

T[] a = (T[]) new Object[1000];

Here, T is a generic type, it’s a placeholder for other Object types like “String” or “Integer”.

Q: I tried that but I’m getting a compiler warning?

A: Sorry, this is something the designers of Java messed up when they introduced generics into Java. There’s no nice way around it. Enjoy your compiler warning. We’ll talk more about this in a few weeks.

Q: How do I make my arrows point to particular fields of a data structure?

In box and pointer diagrams, it sometimes looks like the arrows are able to point to the middle of an array or at specific fields of a node.

A: Those pointer/arrows are always meant to point at the ENTIRE object, not a particular field of an object. In fact it is impossible for a reference to point to the fields of an object in Java.

Q: My implementation of LinkedListDeque or ArrayDeque won’t compile.

Make sure your class definition ends with implements Deque<T>.