Mini-Project 1B: LinkedListDeque61B

Lectures needed for this project:

• Lecture 4 (IntLists).
• Lecture 5 (Testing).
• Lecture 6 (Singly Linked Lists).
• Lecture 7 (Doubly Linked Lists).

Partner policy: No partners. Discussing ideas with other students is allowed, but code sharing is not allowed, and the solutions you submit should be your own work! More details on the policies page.

In this assignment, we’ll use what we’ve learned in the first seven lectures to build your own linked list implementation of a List. To keep the workload lighter, we won’t build a full list, but rather a Double Ended Queue (deque, pronounced “deck”).

By the end of this assignment, you will…

• Gain an understanding of the usage of a backing linked list in data structures.
• Have experience with using testing and test-driven development to evaluate the correctness of your own data structures.

For Mini-Project 1, we will provide a significant amount of scaffolding by giving explicit instructions. In Mini-Project 2, you’ll be completing a similar task, but with less scaffolding.

Assignment Philosophy

A common beginner mistake is to write a large amount of code and hope that it all works once you’re finished. This makes life very difficult for a programmer. Imagine implementing all the methods above, submitting to the autograder, and getting back a message that says something like “call to get returned 9, expected 7”. You have no idea if the problem is the get method itself, or if some other necessary methods are broken.

To help encourage better programming habits, in Mini-Project 1, we’re going to hold your hands through the development process. You are not strictly required to follow the recommended steps, i.e. if you pass the autograder, then you get all the points, but we strongly encourage you to follow the steps outlined in this spec.

For the intended experience, follow these steps in order. If you do something else and ask us for help, we will refer you back to these steps.

Task 1: Creating the File

Start by creating a file called LinkedListDeque61B.

This file should be created in the proj1/src directory. To do this, right-click on the src directory, navigate to “New -> Java Class”, and give it the name LinkedListDeque61B.

We want our LinkedListDeque61B to be able to hold several different types. For example, a LinkedListDeque61B<String> holds String’s and a LinkedListDeque61B<Integer> holds Integer’s. To enable this, you should edit the declaration of your class so that it reads:

public class LinkedListDeque61B<T>

Recall from lecture that it doesn’t actually matter if we use T or some other string like LinkedListDeque61B<Glerp>. However, we recommend using <T> for consistency with other Java code.

We also want to tell Java that every LinkedListDeque61B is a Deque61B, so that users can write code like Deque61B<String> lld1 = new LinkedListDeque61B<>();. To enable this, change the declaration of your class so that it reads:

public class LinkedListDeque61B<T> implements Deque61B<T>

At this point, your class declaration should look like the line above.

However, this creates an error. In order for a LinkedListDeque61B to be a Deque61B, it needs to implement all the Deque61B methods.

Hover your mouse over the red squiggle, and click the “implement methods” button when the error message box pops up. This will autogenerate the method headers for you.

Next, you should create an empty constructor.

To do this, add the following code to your file, leaving the constructor blank for now.

public LinkedListDeque61B() {
}

Lastly, you should create a main method.

Your main method should look exactly like this:

public static void main(String[] args) {
  Deque61B<Integer> lld = new LinkedListDeque61B<>();
  lld.addLast(0);   // [0]
  lld.addLast(1);   // [0, 1]
  lld.addFirst(-1); // [-1, 0, 1]
}

Now you’re ready to start writing methods!

As you start writing code, keep in mind that you may not use any of the built-in java.util data structures in your implementation! The whole point is to build your own versions!

There are a few places where you may use specific data structures outside of tests, and we will clearly say where.

Task 2: Constructor

In this section, you’ll implement the functionality needed so that the first line of the main method Deque61B<Integer> lld = new LinkedListDeque61B<>(); generates a new LinkedListDeque with the appropriate topology.

Recall that the “topology” is the shape of your linked list. Though there are numerous choices as discussed in lecture, for this project, you are required to implement a circular, doubly-linked topology with a sentinel node.

The empty list is represented by a single sentinel node that points at itself. There is a single instance variable called sentinel that points at this sentinel. See this slide.

As mentioned in lecture, this circular toplogy is the hardest to understand, but yields the simplest implementation for this project.

Implement the constructor for LinkedListDeque61B.

In your constructor, you’ll need to:

• Add one or more instance variables to the LinkedListDeque61B class.
• Instantiate a sentinel node.
• Add one or more instance variables the to Node class.
• Initialize the instance variables in the constructor.

To verify that your solution is correct, set a breakpoint in your main method and verify using the visualizer that your code matches the expected topology (shown below for your convenience).

Do not add additional constructors to LinkedListDeque61B. We require that you have only the no-argument constructor.

Task 3: addFirst and addLast

Now, we’ll implement the other methods called in your main method.

Implement addFirst and addLast,

addFirst and addLast may not use looping or recursion. A single add operation must take "constant time," that is, adding an element should take approximately the same amount of time no matter how large the deque is. This means that you cannot use loops that iterate through all / most elements of the deque.

After implementing these two methods, set a breakpoint at the end of your main method and verify that the created LinkedListDeque61B matches the expected topology below.

Note that the arrows will likely look very messy in the Java visualizer, but with some effort you should be able to see that the topology is correct.

Note that in the visualizer diagrams, it might look like the arrows are able to point to the middle of an array or at specific fields of a node. Any time the visualizer draws an arrow that pointed at an object, the pointer is 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.

Task 4: toList

You may have found it somewhat tedious and unpleasant to use the debugger and visualizer to verify the correctness of your addFirst and addLast methods. There is also the problem that such manual verification becomes stale as soon as you change your code. Imagine that you made some minor but uncertain change to addLast. To verify that you didn’t break anything you’d have to go back and do that whole process again. Yuck.

What we really want are some automated tests. But unfortunately there’s no easy way to verify correctness of addFirst and addLast if those are the only two methods we’ve implemented. That is, there’s currently no way to iterate over our list and get back its values and see that they are correct.

That’s where the toList method comes in. When called, this method returns a List representation of the Deque61B. For example, if the Deque61B has had addLast(5), addLast(9), addLast(10), then addFirst(3) called on it, then the result of toList() should be a List with 3 at the front, then 5, then 9, then 10. If printed in Java, it’d show up as [3, 5, 9, 10].

If the Deque is empty, then toList should return an empty list with zero items, e.g. return new ArrayList<>(). The toList method should never return null.

Write the toList method.

The first line of the method should be something like List<T> returnList = new ArrayList<>(). This is one location where you are allowed to use a Java data structure. You can import ArrayList by using IntelliJ’s auto import or copying this statement at the top of your LinkedListDeque61B.java file:

import java.util.ArrayList; // import the ArrayList class

To verify that your toList method is working correctly, you can run the tests in LinkedListDeque61BTest.

You might realize that you can just dodge the rest of the project by calling toList and calling the appropriate method. That would defeat the point of the project! You may not call toList inside any method of LinkedListDeque61B; there is an autograder test that checks for this.

Note: Later in the class, we’ll learn techniques that will allow us to test our data structures without converting them into a Java list first. This is purely for convenience on this first project.

Task 5: isEmpty and size

Now you should test and implement all the remaining methods. For the rest of this project, we’ll describe our suggested steps at a high level. We strongly encourage you to follow the remaining steps in the order given.

Implement isEmpty and size.

These methods must take constant time. That is, the time it takes to for either method to finish execution should not depend on how many elements are in the deque.

Task 6: getFirst and getLast

Implement getFirst and getLast methods. Make sure to address the cases where Deque61B has no items or is empty. In these cases getFirst and getLast should return null.

Implement getFirst and getLast.

These methods must take constant time. That is, the time it takes to for either method to finish execution should not depend on how many elements are in the deque.

Task 7: get and getRecursive

Now, implement the get method. Make sure to address the cases where get receives an invalid argument, e.g. calling get(28723) when the Deque61B only has 1 item, or a calling get on a negative index. In these cases get should return null.

get must use iteration.

Implement get.

Since we’re working with a linked list, it is interesting to write a recursive get method, getRecursive.

Implement getRecursive.

Task 8: removeFirst and removeLast

Lastly, implememt methods removeFirst and removeLast

Do not maintain references to items that are no longer in the deque. 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 memory usage should amount to a deque with 1 item, and not 10,000. Remember that the Java garbage collector will “delete” things for us if and only if there are no pointers to that object.

If Deque61B is empty, removing should return null.

removeFirst and removeLast may not use looping or recursion. Like addFirst and addLast, these operations must take "constant time." Refer to the section on writing addFirst and addLast for more information on what this means.

Implement removeFirst and removeLast.

Submission

Once you’ve written local tests for every method, follow the Assignment Workflow Guide to submit to the autograder.

Scoring

Project 1B is worth 120 points