CS342-Project 1 Generic Lists in Java Solved

In this project you will implement your own versions of the stack and queue data structures. Although the Java API provides built-in support for them, you will write your own to practice the constructs and language details we have seen in class. That means you are NOT allowed to use any pre existing libraries or classes for this assignment.

Essentially, you are writing your own data structure library that could be used by others in the same way that one can use ArrayList<. Your library provides data structures as classes, the method calls expected with those data structures and the definition for an iterator so that the clients of your libraries can iterate through the lists in the same way as most generic data structures in Java.

In this simplified version, each data structure is a singly linked list. The stack is LIFO (last in first out) while the queue is FIFO (first in first out). Your implementation must be generic, like ArrayList,  as to allow for different types when each data structure object is instantiated.

You will also implement the Iterator design pattern; allowing users access to a custom Iterator for your data structures.

Implementation Details: 

You will download and use the Maven project template GLMaven_Project1_SP2020 from Blackboard. You will find a file called GLProject.java in the src folder. This class contains the main method. You should test this template with the Maven command “compile”. This command will both compile your src code and run exec:java; resulting in the line “hello generic lists” being printed and a successful build. The Maven command

“test” will run one test case that fails all the time. You will create a new file, inside of src/ main/java, for each outer class and interface. In comments at the top of the file GLProject.java, please include your name and netid and university email as well as a brief description of your project.

DO NOT add any folders or change the structure of the project in anyway. DO NOT alter the pom.xml file.

Create a generic abstract class called GenericList<I:

This class will contain only two data fields:


Node<I head (this is the head of the list and should be private).
int length (the length of the list and should be private)

This class should include the following methods:


print(): prints the items of the list, one value per line. If the list is empty, print “Empty

List”.


add(I data): adds the value to the list. This method is abstract since the implementation depends on what the data structure is.


public I delete(): returns the first value of the list and deletes the node. If the list is empty, return null.

public ArrayList<I dumpList(): this method stores and returns all values currently in the list into an ArrayList and returns it. At the end of this method, your list should be empty.

getLength()  setLength()  getHead()  setHead(), these are getters/setters for private data members head and length.

This class should also define a generic inner class Node<T: It will include two fields:  

T data and Node<T next;

***This class encapsulates a linked list. Defining a Node class and providing two methods that a queue and stack have in common while leaving adding a node to each implementation that inherits from it.***

Create two more classes GenericQueue<I and GenericStack<I. They both should inherit from GenericList<I.

The constructors for each class will take one parameter. That parameter will be a value that will go in the first node of the list encapsulated by each instance of the class. Each constructor should initialize the linked list head, with the value passed in by the constructor. Each class should also implement the method add(I data), GenericQueue will add to the back of the list while GenericStack will add to the front. Each class must also keep track of the length of it’s list using the length data field defined in the abstract class.

GenericQueue will have the methods enqueue(I data) and public I dequeue() which will call the methods add(I data) and delete() respectively. Enqueue and dequeue merely call add(I data) and delete(). The reason for this is that a user would expect these calls to be implemented in each of those data structures. You will do the same with GenericStack 

GenericStack will have the methods push(I data) and public I pop() which will call the methods add(I data) and delete() respectively.

Once implemented, you should be able to create instances of both GenericQueue and GenericStack in main with most primitive wrapper classes. You should be able to add and delete nodes to each data structure instance as well as print out the entire list and check for the length of the list. You must follow this implementation: meaning you can not add any additional data fields or classes. You may add getters/setters as need be.

Implementing Iterator Design Pattern: 

You are to create an interface called CreateIterator. It will have one abstract method: Iterator createIterator(). Since both GenericQueue and GenericStack classes iterate through a list the same way, you will want to implement this interface in GenericList.

You must also create a class to contain logic for iterating through your data structure. Call this class GLIterator. GLIterator should be a generic class since it provides the logic to iterate through a generic stack and queue.

It should implement the java interface Iterator (java.util.Iterator). You will have to implement two inherited methods: public boolean hasNext(), checks to see if there is another value in the data structure and returns true or false, and public I next(), returns the current value in the data structure and advances to the next item.

You are expected to fully comment your code and use good coding practices.