Overview
In this request you will implement data structures that provide an implementation for four abstract data types: A double-ended singly linked list, a stack, a queue, and a binary search tree that allows duplicates. Along the way you will get more experience with implementing Java interfaces, writing JUnit test cases, and using the Adapter design pattern.
Part 1 - Double Ended Singly Linked List
DoubleEndedLLTester
Create DoubleEndedLLTester.java to test all public methods in DoubleEndedLL.java class, which implements DoubleEndedLLInterface. You must have at least one test for every method, but for some methods it is better to create multiple tests for separate conditions. For example, removing from an empty list should have a separate test from removing from a non-empty one.
You do not need to completely write your DoubleEndedLLTester before starting to define DoubleEndedLL. In fact, it is recommended that you use an iterative test-driven development process: write some tests in DoubleEndedLLTester, implement the functionality in DoubleEndedLL, test your implementation with DoubleEndedLLTester, write more tests, etc.
DoubleEndedLL
Read the documentation in the source code file for the DoubleEndedLLInterface. You will be creating DoubleEndedLL.java class to implement this interface. Think of the “implements” as a contract - it is your responsibility to ensure all of the methods in the interface are present and functional in your class. For method headers, you may simply copy over the appropriate comments from the interface file. However, you must still comment the constructor and any other methods not present in the interface.
DoubleEndedLL must be a Generic class that implements a singly-linked list with a head and tail reference, using an inner class Node. You may find it helpful to copy over your Node class from PA1 and modify it for this request. The only public methods you may have are the no-arg constructor and the interface methods.
Files to Submit
- DoubleEndedLLTester.java
- DoubleEndedLL.java
Part 2 - Implementing Stacks and Queues
Now that DoubleEndedLL is fully built and tested, use it to implement a Stack and a Queue. Both MyStack and MyQueue are generic classes that implement Stack_QueueInterface, however their functionality will differ.
In order to get full credit for this section, you must use the Adaptive Design Pattern to implement these classes. To do that, create an instance variable of type DoubleEndedLLInterface (instantiated to a DoubleEndedLL) and use it to perform all of the necessary class methods. If these classes are complicated, you are overthinking the problem.
As is often the case when the Adapter pattern is used, if the adapted class (DoubleEndedLL in this case) is thoroughly tested and debugged, the adapting class shouldn’t need much testing because almost all of the work is being handled by delegation to the adapted class’s methods. We provide you with a few simple tests (MyStackTester.java and MyQueueTester.java) which should be sufficient but you are welcome to write your own tests as well.
MyStack
Stacks are first-in last-out data structures, which you will implement using your internal DoubleEndedLL object by mapping the appropriate methods to your MyStack class methods. One choice of mappings is better than another. You must choose the most efficient mapping. In HW3.txt, indicate what methods were chosen to perform stack operations efficiently and why. You must mention every method in the MyStack class.
MyQueue
Queues are first-in first-out data structures, which you will implement using your internal DoubleEndedLL object by mapping the appropriate methods to your MyQueue class methods. One choice of mappings is better than another. You must choose the most efficient mapping. In HW3.txt, indicate what methods were chosen to perform stack operations efficiently and why. You must mention every method in the MyQueue class.
Files to Submit
- MyStack.java
- MyQueue.java
- HW3.txt
Part 3 - Duplicate Key BST
Most often it is assumed that a binary search tree does not contain duplicate keys. However, sometimes we need to deal with problems that contain duplicates. For example, a database of car services might contain one record for each service for every car; so if a car got serviced twice, there will be two records with the same key (car’s VIN) and different dates (service dates). To accomplish this, we might use a data structure called a “BST with duplicates”, or BSTDup.
Your node class might look something like this:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21protected class BSTDupNode {
private int key;
private ArrayList<T> elements;
private BSTDupNode left;
private BSTDupNode right;
// Constructor
public BSTDupNode(int key, T elem, BSTDupNode left, BSTDupNode right) {
this.key = key;
elements = new ArrayList<T>();
elements.add(elem);
this.left = left;
this.right = right;
}
/**
* Think about what other methods you might need...
* accessors (data, key, left, right)
* mutators (add/remove data, updates children)
*/
}
The image on the left is an example of just the tree structure, and each node displays only the key. The image on the right is an example of how your BST would actually be used, in this case to store the names of sweets. For your implementation, nodes will contain an ArrayList of elements, rather than a single one. That allows the BST structure to be preserved, while still allowing duplicate keys.