Write a linked-list version of a Queue class, which implements the same Queue interface using an array. Use the Singly Linked List ADT for your implementation. Note: Queue.java and Node.java & SLinkedList.java must be used without any modifications . SLinkedList.java includes the gotoTail() method. Test your implementation fully and submit the test code and results as well as the code for your Linked List Queue, and the usual development notes, etc. As part of your testing, I recommend that you enqueue the same items onto both a Linked List Queue and the Array Queue, and verify that you get the same results when you pop items from both. Some notes: Your main goal is to write a new class, LLQueue.java, similar in operation to ArrayQueue.java, but that uses the singly linked list as its internal storage instead of the array. Examine every method and see how it needs to be modified. Here are few examples to get you started: The Constructor will create an empty linked list, not an array You dont need to store its capacity and there is no fixed limit to the linked list storage You will have to decide how the enqueue and dequeue methods should operate relative to the head and tail of the underlying linked list. Is it easier to insert or delete objects at one end or the other?

public interface Queue { // most important methods public void enqueue(Object n); // add an object at the rear of the queue public Object dequeue(); // remove an object from the front of the queue // others public boolean isEmpty(); // true if queue is empty public boolean isFull(); // true if queue is full (if it has limited storage) public Object front(); // examine front object on queue without removing it } 

public class Node { // Instance variables: private Object element; private Node next; /** Creates a node with null references to its element and next node. */ public Node() { this(null, null); } /** Creates a node with the given element and next node. */ public Node(Object e, Node n) { element = e; next = n; } // Accessor methods: public Object getElement() { return element; } public Node getNext() { return next; } // Modifier methods: public void setElement(Object newElem) { element = newElem; } public void setNext(Node newNext) { next = newNext; } } 

public class SLinkedList { protected Node head; // head node of the list protected Node tail; // last position in the list protected Node curr; // node referencing current position in the list protected long size; // number of nodes in the list /** Default constructor that creates an empty list. */ public SLinkedList() { curr = tail = head = null; size = 0; } public long size() { return size; } public boolean isEmpty() { return (head == null); } public Object getCurr() { if (curr == null) // Verify that there is a current node return null; return curr.getElement(); } public boolean gotoHead() { if (isEmpty()) return false; curr = head; return true; } public boolean gotoNext() { if (curr == tail) return false; curr = curr.getNext(); return true; } public boolean gotoTail() { if (isEmpty()) return false; curr = tail; return true; } public void insertNext(Object el) { if (head == null) { insertHead(el); // If haven't inserted a head, do so now (for convenience) return; } Node newnode = new Node(el, curr.getNext()); // create new node with its next node equal to curr's next node curr.setNext(newnode); // update the next node of the current node to point to the new one size++; // update the tail if at the end of the list if (tail == curr) tail = newnode; // make this new node the current one curr = newnode; } public void deleteNext() { if (curr == null || curr.getNext() == null) return; // no next: list empty or already at end // update the tail if the node we are deleting is the tail if (tail == curr.getNext()) tail = curr; curr.setNext(curr.getNext().getNext()); // set curr's next equal to the next node's next // Note: Garbage collector will automatically clear up the node no longer referenced size--; } public void insertHead(Object el) { Node oldhead = head; head = new Node(el, oldhead); size++; curr = head; if (size == 1) // if this is the first node, it is both head and tail tail = head; } public void deleteHead() { if (head == null) return; // list already empty head = head.getNext(); size--; curr = head; if (size == 0) // if this was the only node, get rid of ref to tail as well as head tail = null; } }