Project 1a: Data Structures, version 1.1

This project is in two parts. Part 1A will be due 2/3, and Part 1B will be due 2/10.

Rather than simulating the glorious gravitational physics of our universe, we'll instead be building data structures. Not the most glamorous thing, but this will provide you with plenty of opportunities to practice everything we've been doing in lecture before our midterm rolls around.

Introduction

In project 1A, we will build implementations of a "Double Ended Queue" using both lists and arrays. In project 1B (next week), we will learn how to write our own tests for those data structures, and will use the Double Ended Queue to solve some small real world probelms.

In this part of the project you will create exactly two Java files: LinkedListDeque.java and ArrayDeque.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 must work alone! Please carefully read the Policy on Collaboration and Cheating to see what this means exactly.

Getting the Skeleton Files

As with project 0, you should start by downloading the skeleton files. The directions are repeated below.

To do this, head to the folder containing your copy of your repository. For example, if your login is 'agz', then head to the 'agz' folder (or any subdirectory).

Now we'll make sure you have the latest copy of the skeleton files with by using git pull skeleton master. If you're using a newer version of git, you might need to do git pull skeleton master -allow-unrelated-histories.

If you find yourself faced with a strange text editor or a merge conflict, see the project 0 directions for how to proceed.

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

If you get some sort of error, STOP and either figure it out by carefully reading the git guide or seek help at OH or 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 file in the skeleton is LinkedListDequeTest.java. This file provides 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 your own.

You'll probably find writing tests pretty annoying in part A. However, in part B of this project, we will use a library called JUnit that will make writing tests much easier.

To use the sample 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 visualizer from inside IntelliJ!

The Deque API

The double ended queue is very similar to the SLList and AList classes that we've discussed in class. Specifically, any Deque implementation must have exactly the following operations:

For both implementations (LinkedListDeque.java and ArrayDeque.java), your code must include all of these public methods. In addition, LinkedListDeque must include a getRecursive method described below, and both should also include zero argument constructors that create an empty Deque.

Your class should accept any generic type (not just integers). For information on creating and using generic data structures, see lecture 5. Make sure to pay close attention to the rules of thumb on the last slide about generics.

Linked List Deque

Note: We covered everything needed in lecture to do this part in Lectures 4 and 5 (1/25 and 1/27).

As your first of two Deque implementations, you'll build the LinkedListDeque class, which will be linked list based. Your operations are subject to the following rules:

In addition to the methods listed above, you should also include:

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 lecture on doubly linked lists, particularly the slides on sentinel nodes: two sentinel topology, and circular sentinel topology. I prefer the circular approach. You are not allowed to use Java's LinkedList data structure (or any data structure from java.util) in your implementation.

Array Deque

Note: We'll have covered everything needed in lecture to do this part by Jan 30th (lecture 6).

As your second of two Deque implementations, you'll build the ArrayDeque class. This Deque must use arrays as the core data structure. In addition to the methods listed in "The Deque API", your ArrayDeque class must include a zero argument constructor that creates an empty Deque.

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

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 project 1 demo slides for more details.

The signature of the constructor should be public ArrayDeque(). That is, you need only worry about initializing empty ArrayDeques.

Tips

Frequently Asked Questions

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

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

I can't get Java to create an array of generic objects!

Use the strange syntax we saw in January 30th's lecture, i.e. Item[] a = (Item[]) new Object[1000];

I tried that but I'm getting a compiler warning.

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.

How do I make my arrows point to particular fields of a data structure. In your diagram from lecture it looked like the arrows were able to point to the middle of an array or at specific fields of a node.

Any time I drew an arrow in class that pointed at an object, the pointer was to 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.