What is the efficiency of each of the queue methods? What would the efficiency be if we insert elements in the front of the queue and remove them from the back (still using singly linked lists)?
public class IntQueue {
private LinkedList list = new LinkedList();
private Node endOfQueue; // the last element on the queue
public boolean isEmpty() {
return list.isEmpty();
}
public void enqueue(int k) {
// insert the element at the end of the queue
Node newLast = new Node(k);
if (this.isEmpty()) { // calling the isEmpty method of this queue
list.setFirst(newLast);
endOfQueue = list.getFirst(); // the new node created by setFirst
} else {
endOfQueue.setNext(newLast);
endOfQueue = newLast;
}
}
public int dequeue() {
// remove the element from the front of the queue
int data = list.getFirst().getData();
list.removeFront();
if (list.isEmpty()) endOfQueue = null;
return data;
}
// can be used for testing
public void printQueue() {
Node n = list.getFirst();
while (n != null) {
System.out.println(n.getData());
n = n.getNext();
}
}
}
// This is a second implementation of Linked Lists.
// It makes sure that the list is in the consistent state
// when elements are added to it.
public class LinkedList {
private Node first;
public LinkedList() {
first = null;
}
public boolean isEmpty() {
return (first == null);
}
public Node getFirst() {
return first;
}
// allows to set the first node to null
public void setFirst(Node n) {
if (n == null) {
first = null;
} else {
Node newFirst = new Node(n.getData());
newFirst.setNext(null); // this is the only element on the list
first = newFirst;
}
}
// works for non-null parameters only
public void addFront(Node n) {
// assume that n != null, otherwise NullPointerException
Node internal = new Node(n.getData());
internal.setNext(first);
first = internal;
}
public void removeFront() {
// assume that there is an element to remove,
// otherwise NullPointerException
first = first.getNext();
}
}
public class Node {
private int data;
private Node next;
public Node(int d) {
data = d;
next = null; // can skip this line: null is the default value
}
public int getData() {
return data;
}
// return the next node
public Node getNext() {
return next;
}
// set the node
public void setNext(Node n) {
next = n;
}
}