In the first few parts of this lab, we will be creating our own implementation of the doubly linked list data structure to better understand how its implementation and behavior differ from the array list that we created in Lab 3, even though both provide the same fundamental functionality as Lists. This will build on the singly linked list that you started in Part 1 of the Warmup – recall from class that a doubly linked list can transverse the list both forwards and backwards, whereas a singly linked list only traverses the list in one direction (usually forward).
As we used in Lab 3, Java already provides an interface called List that defines all the methods that a linked list should have, as well as an AbstractList abstract class that implements some of the basic functionality of the List interface (that could be shared by other types of lists, such as Lab 3’s MyArrayList). We’ll again be using generics for the implementation so that the doubly linked list can store any type of data as elements.
Full documentation of what a doubly linked list might include can be found in Java’s LinkedList documentation.
Inside your GitHub repository, you will find a file called MyLinkedList.java. Open this file in Visual Studio Code by either using the “File” > “Open” dialog box, or double click on the MyLinkedList.java file on the left side of your IDE in the “Explorer” area. Within this file, you should create a new class called MyLinkedList<T> that inherits from Java’s AbstractList<T>. Throughout the semester, we will include the prefix My in your class name so we can separate it from Java’s own LinkedList implementation.
Before we can start creating our linked list, we need a class to represent the nodes that are chained together to comprise the doubly linked list. Inside our MyLinkedList<T> class, create an inner class called DoublyLinkedNode.
ReadMe
Here, we make DoublyLinkedNode an inner class to MyLinkedList<T> because DoublyLinkedNode is only used internally to our MyLinkedList; we will never refer to a DoublyLinkedNode object outside the methods of MyLinkedList. All of the methods of MyLinkedList<T> will either take an item of type T as an argument or return an item of type T, but they will never expose the underlying DoublyLinkedNode that stores an item. This is an example of encapsulation from object-oriented programming in action!
Also, note that DoublyLinkedNode is not DoublyLinkedNode<T>. Since it is a private class of MyLinkedList<T>, it is already parameterized by the generic T.
To make DoublyLinkedNode an inner class of MyLinkedList, we nest its definition inside of the MyLinkedList class like:
public class MyLinkedList<T> extends AbstractList<T> {
/* Your MyLinkedList instance variables and methods go here. */
private class DoublyLinkedNode {
/* Your DoublyLinkedNode instance variables and constructor
go here.*/
}
}
Your DoublyLinkedNode inner class should have three private instance variables:
/** The item stored in this Node. */
private T item;
/** The Node that preceeds this Node in the doubly linked list. Note: previous is null if this Node is the beginning of the doubly linked list. */
private DoublyLinkedNode previous;
/** The Node that follows this Node in the doubly linked list. Note: next is null if this Node is the end of the doubly linked list. */
private DoublyLinkedNode next;
Even though we declared these instance variables to be private, they can still be accessed by our MyLinkedList class since DoublyLinkedNode is an inner class of MyLinkedList.
The DoublyLinkedNode class only needs one method: a constructor that takes three arguments – one for each of the three instance variables – and assigns the arguments to the instance variables.
You have probably noticed that our DoublyLinkedNode class is very similar to the LinkedNode class that you created in the Part 1 of the Warmup. The only difference is the addition of the previous instance variable, which will allow us to also traverse the linked list in backwards order. Otherwise, everything is exactly the same as in the warmup.
The MyLinkedList<T> class should have three private instance variables:
/** The Node that is currently the beginning of the linked list. */
private DoublyLinkedNode firstNode;
/** The Node that is currently the end of the linked list. */
private DoublyLinkedNode lastNode;
/** The current size of the list. */
private int size;
We also want to include one constructor public MyLinkedList() that takes no arguments and creates an initially empty list. This simply involves assigning null to both the firstNode and lastNode to null and assigning 0 to size.
The last thing we are going to do in this first part of the lab is fill in the public int size() method required of all List classes. This method should simply return the current size of your MyLinkedList.
As we saw in Lab 3, it is good practice to frequently test what you have implemented so far, instead of trying to implement an entire class before doing any debugging. Although we haven’t implemented a lot of our MyLinkedList class yet, we can still do some testing before moving on.
ReadMe
However, there is one more thing we need to do before we can compile our MyLinkedList.java file. Recall that we had our MyLinkedList<T> class extend AbstractList<T>. There is one more abstract method in AbstractList that needs to be implemented in order to compile our class. For the purposes of testing our progress so far, we do need to actually fill in this method; instead, we can simply include a stub that we will fill in later. To do so, add this to your code for now:
public T get(int index) {
// TODO: we will fill this in soon
return null;
}
which satisfies the requirements of the get method signature but doesn’t actually do anything for now.
Now, we can create our first unit test that verifies the functionality of our MyLinkedList class. As in Lab 3, we can create a Java file that will contain our unit tests by right clicking anywhere in the MyLinkedList.java file and selecting “Source Action” from the right click menu. Then, select “Generate Tests”. Use the default name proposed by the IDE of MyLinkedListTest. Next, it will prompt you with what methods you want to create tests for. Select the size method for now.
Inside the newly created MyLinkedListTest.java file, fill in the testSize method to:
Later in the lab, after you’ve implemented the add method, we’ll want to update this test to make sure that size is properly returned for MyLinkedList objects with different numbers of items.
Don’t forget to frequently save your progress periodically to GitHub using the add, commit, and push commands with git.