Assignment 03: Linked List Deque Implementation

implementing a double ended queue (deque) with a doubly linked list

Due: Friday, February 25th by 5:00pm

Overview

Last week, you implemented a deque (double ended queue) using a circular array to store the deque’s contents. In this assignment, you will provide another deque implementation using a doubly linked list and compare its performance to last week’s implementation.

Doubly Linked Lists

The file LinkedSimpleList.java (linked to below) gives an implementation of a SimpleList using a linked list data structure. While accessing and modifying elements at the head of a linked list is efficient, accessing the “tail” of the list is not, as all preceding elements must be traversed to reach the final node in the list. A doubly linked list is modification of a linked list in which:

  • references to both the head and tail nodes are stored, and
  • each node stores references to both its next and previous nodes.

For example, the following figure depicts a doubly linked list storing the elements 1, 4, 1, 5.

With a doubly linked list, both the head and tail elements can be accessed directly, so adding/removing elements at both ends of the data structure can be performed efficiently.

In order to implement a doubly linked list, your class should store references to both the “head” and “tail” nodes in the list, and each Node should store references to both its “next” Node and its “previous” Node. In this way, the list can be traversed in either direction.

Code

Download this archive containing the following files:

  • Interfaces
    • SimpleDeque.java
    • SimpleList.java
  • Utilities
    • DequeTester.java
    • CSVWriter.java
    • RunTimer.java
  • Implementations
    • ArraySimpleList.java
    • LinkedSimpleList.java
    • ASLDeque.java
    • LSLDeque.java

Your Task

For this assignment, you will write and test an implementation of the Deque ADT: DLLDeque.java, which implements SimpleDeque using a doubly linked list.

Be sure to test the correctness of your implementation using the provided DequeTester.java. The provided version of DequeTester currently tests the (provided) DLLDeque implementation, so you’ll need to add your implementation to the test. For example, you can test DLLDeque by setting

1

	SimpleDeque<Integer> deque = new DLLDeque<Integer>();

at the beginning of the main method in DequeTester.java.

You should also write a program that tests the performance of your SimpleDeque implementation. Specifically, it should be able to measure the (average) running times of the SimpleDeque operations for a range of instance sizes (i.e., for various numbers of elements stored in the deque). You should use its output to answer the questions below. For example, you should test the amount of time required for addFirst and addLast for various sizes of deques—say around 50 different values—to get a sense of the trend of how these running times depend on deque size.

Testing

The provided tester DequeTester performs some “randomly” chosen operations to check the correctness of your implementation. The parameters of the tester are chosen in the following lines:

1
2

    static Random rand = new Random(10);
    static final int TEST_SIZE = 1_000;

In this case ther “random seed” is set to 10, and the instance size is set to 1000. The random seed determines which operations are performed, so that if you run the tester with the same parameters multiple time, it will perform exactly the same tests. Different operations will be performed if the random seed and/or TEST_SIZE are set to different values. A correct implementation of a SimpleDeque should pass all tests with any choice of these parameters, while incorrect implementations may pass the tests for some and fail tests for others. Your submission will be tested with different parameters than those above.

Questions

Please answer the following questions about your programs. Be sure to support claims with evidence (e.g., plots of running times).

  1. Consider the addFirst and addLast methods for your DLLDeque. How do the running times of these methods depend of the size of the deque? Does the time per operation appear to grow with the size of the deque?

  2. How do the performance of the addFirst and addLast methods for DLLDeque compare to the same methods for the CADeque implementation you provided in assignment 2? How can you explain their similarity/difference?

  3. How do the running times of addFirst and addLast compare between your implementations and the provided list-based implementations, ASLDeque and LSLDeque?

What to Submit

You should submit:

  • CADeque.java containing your SimpleDeque implementation using a circular array,
  • responses.pdf containing your responses to the questions above.
  • any code you used to generate responses.pdf

Evaluation

Your submission will receive a score out of 10 points, broken down as follows:

  • 5 points each for DLLDeque.java
    • code compiles, runs, and passes all tests in SimpleDequeTester.java
    • code correctly implements a circular array
    • code is well organized and documented with comments
  • 5 points for responses to the questions above