public class Node { private String data; private Node next;

public Node(String d, Node n ) { data = d; next = n; } // The usual get/set methods, plus toString() public void setData(String d) { data = d; } public void setNext(Node n) { next = n; } public String getData() { return data; } public Node getNext() { return next; } public String toString() { return data + " --> "; } }

public class LinkedList { private Node front; //private int count; //private Node end;

public LinkedList(Node f ) { front = f;

}

public LinkedList() { front = null;

} public void addToFront(String d) { Node n = new Node(d, front); front = n; }

public boolean isEmpty() { if(front == null) return true; else return false; }

public void clear() { front = null;

}

public String getFrontData() { return front.getData();

}

public Node getFrontNode() { return front;

} public String toString() { String ts = "["; Node cur = front; while(cur != null) { ts += cur; cur = cur.getNext(); } return ts + "]"; }

public int size() { int count = 0; Node cur = front; while(cur != null) { count++; cur = cur.getNext(); } return count; }

public void removeFront() { if(!isEmpty()) front = front.getNext(); // else // System.out.println(No front to remove!);

}

public void addToEnd(String d) { Node n = new Node(d, null); if(isEmpty()) front = n; else { Node cur = front; while(cur.getNext() != null) cur = cur.getNext(); cur.setNext(n); } }

public void removeLast() { if(!isEmpty()) { if(front.getNext() == null) front = null; else { Node cur = front; while(cur.getNext() != null) cur = cur.getNext(); cur.setNext(null); } //} else { System.out.println(No end to remove!); } }

public int contains(String d) { Node cur = front; boolean found = false; int index = -1;

while(cur != null && !found) { index++; if(cur.getData().equals(d)) found = true; cur = cur.getNext(); } if(!found) index = -1; return index; }

public void add(int index, String d) { if(index >= 0 && index

public void remove(int index) { if(index >= 0 && index

public Node getNode(int index) { Node cur = null; if(index >= 0 && index

public void addAll(LinkedList other) { Node cur = other.getFrontNode(); while(cur != null) { addToEnd(cur.getData()); cur = cur.getNext(); } }

public static LinkedList merge(LinkedList first, LinkedList second) { LinkedList result = new LinkedList();

Node cur = first.getFrontNode(); while(cur != null) { result.addToEnd(cur.getData()); cur = cur.getNext(); }

cur = second.getFrontNode(); while(cur != null) { result.addToEnd(cur.getData()); cur = cur.getNext(); } return result; }

public LinkedList subList(int start, int end) { LinkedList result = new LinkedList(); if(!(start >= end || start size() || end >= size() )) { Node cur = getFrontNode(); for(int i=0; i

public static LinkedList union(LinkedList first, LinkedList second) { LinkedList result = new LinkedList(); Node cur = first.getFrontNode(); while(cur != null) { result.addToEnd(cur.getData()); cur = cur.getNext(); }

cur = second.getFrontNode(); while(cur != null) { if(result.contains(cur.getData()) == -1) result.addToEnd(cur.getData()); cur = cur.getNext(); }

return result; }

public static LinkedList intersection(LinkedList first, LinkedList second) { LinkedList result = new LinkedList(); Node cur = first.getFrontNode(); while(cur != null) { if(second.contains(cur.getData()) != -1) result.addToEnd(cur.getData()); cur = cur.getNext(); }

return result; }

}

Exercise 2 In class, we also wrote an implementation for a Queue using an ArravList Write your own Queue class (Queue.java) that uses a LinkedList to store the underlying (String) data. Your implementation should have (at least) a constructor, an enqueue method, a deaueue method, and a peek method. The Liukedlist class you use should be based off of the version we wrote in class