java Linked-List Queue As you know from class, a linked list is a like an array
ID: 3857164 • Letter: J
Question
java Linked-List Queue
As you know from class, a linked list is a like an array but it is implement by a series of nodes, containing data, which point to each other. It is very efficient to add and remove items from a linked list but it is difficult to find items in the list. This is the opposite of an array where it is very efficient to find items but it is inefficient to add and remove items. However, for linked lists it is extremely efficient to add, remove and find items at the start or end of the list which makes them perfect for queues. Thus, the linked list is the most common way to implement a queue.
Before we can build a linked-list queue we must first build a linked list. For a queue all we need is a singly linked list meaning that each node is linked to the next node.
Class Node
A linked list is merely a group of nodes that are linked to each other. Thus, to implement a linked list we need only implement a Node class. Each Node must store some data, in our case the data should be of type Job. Because we are building a singly linked list, a Node must also store a linked to the next Node, if there is one. It there is no next Node then it should be null. The Node class merely stores data. Thus, for methods it should provide getters and setters for the variables. It should also have two constructors: one which gets the values for both variables from the user and one which only gets the Job from the user and assumes that the next Node is null.
Class LinkedListQueue
Since a queue is a “line” two important pieces of information are needed: the start of the line and the end of the line, called the head and tail respectively. These are obviously of type Node. The linked list, if properly implemented, will take care of storying everybody in between the head and tail.
enqueue works just like in a “line” in real life: a new person arrives and goes to the end of the line, becoming the new end of the line. In our case we simply add a new Node end to the linked list (the tail Node). This Node becomes the new tail.
dequeue is different than a “line” in real life. In real life, the whole line moves forward when a person at the front is served, but this is inefficient inJava. Instead, we can imagine the service counter moving forward towards the next person in line. Thus, the head Node is removed from the linked list (and its Job returned) and the next person in the line becomes the new head of the line. It is up to you to figure out how isEmpty and clear work
NodeNode data next Node Node | Node data data data data In Figure 1: A diagram of a singly linked listExplanation / Answer
/**
*
* @author Sam
*/
class Job{
}
class Node {
private Job data;
private Node next;
public Node(Job data) {
this.data = data;
next = null;
}
public Node(Job data, Node next) {
this.data = data;
this.next = next;
}
public Job getData() {
return data;
}
public void setData(Job data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
public class LinkedListQueue {
Node head, tail;
public LinkedListQueue() {
head = null;
tail = null;
}
public void enqueue(Job newJob) {
if (tail == null) {
head = tail = new Node(newJob);
return;
}
tail.setNext(new Node(newJob));
tail = tail.getNext();
}
public Job dequeue() {
if (head == null)
return null;
Job tmp = head.getData();
head = head.getNext();
if (head == null)
tail= null;
return tmp;
}
}
I have included three calsses:
1. Job: this is for your need. As nothing is mentioned in the question, the class is empty
2. Node class to describe the the various functions implememted by the Node as described in the question.
3. The main Queue class from the description in the question
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.