Homework 6, Part A: Doubly Linked Lists

Here, you will create your own implementation of a doubly linked list. A doubly linked list is a linked list in which every node maintains a reference to the item next in the list, as well as the item previous in the list:

Task 0: Getting Settled

Copy over the LinearList<T> interface from the in-class exercise. Your linked list should implement this interface.

Task 1: Doubly Linear Node

Create a class, DoublyLinearNode<T>, to represent a node in your linked list. You can follow the LinearNode from the in-class exercise for inspiration.

Task 2: Implementing the Doubly Linked list

Create a class, DoublyLinkedList<T> that uses your DoublyLinearNode<T> to implement the LinearList<T> interface. Before implementing each method, draw a memory diagram to make sure you know what pointer manipulations you plan to use. You may find it helpful to draw multiple versions of these memory diagrams corresponding to lists of various sizes.

Additionally, in your implementation, please:

• Store both a reference to the front of the list and the rear.
• Update these references appropriately when inserting/removing.
• Use the reference to rear for fast get/insertion/removal from the very end of the list (i.e. if someone wants to operate on the last element of the list, they shouldn’t have to iterate over the whole list to find it).

Hints: For both insert and remove, you may want to break your code into several cases:

• When the list is empty
• When removing from a list of size 1
• When inserting/removing at the front
• When inserting/removing at the rear

Task 3: Testing

Please test your DoublyLinkedList<T> in a main method belonging to the same class. You can save your tests in DoublyLinkedListTests.txt. There’s no need to test your DoublyLinearNode<T>.

Homework 6, Part B: Implement a Queue

Here, you will implement a queue using your implementation of the doubly linked list above.

Task 0: Getting Settled

Your queue should implement the Queue<T> interface:

public interface Queue<T> {
    // Adds element to rear of the queue
    public void enqueue(T element);

    // Removes and returns element at front of queue
    public T dequeue();

    // Return reference to first element without removing
    public T first();

    // Returns true if queue contains no elements
    public boolean isEmpty();

    // Returns number of elements
    public int size();

    // Returns string representation
    public String toString();
}

Create a file for it in your BlueJ project.

Task 1: Implement the queue

Create a class, LinkedQueue<T> that implements the Queue<T> interface. You should use your DoublyLinkedList<T> in your implementation. Before starting to code, determine whether LinkedQueue<T> should have an is-a or has-a relationship with DoublyLinkedList<T>.

Task 2: Test your queue implementation

Write your tests in a main method in the same file as LinkedQueue<T>. Please save your tests in LinkedQueueTests.txt.

Submission Checklist

• You submitted all .java files and all .txt files.
• Your files are named exactly as in the homework specification, including file extensions.
• You tested every possible pathway in your code.
• You signed every class (or file) with @author and @version, accompanied by a description of what the class does.
• You wrote javadoc for every function, which includes @param and @return.
• You wrote inline comments explaining the logic of your code.