Linked-List Queue

Java. 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

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 Node Node Node Node Node data data data data data next Figure 1: A diagram of a singly linked list Class Node A linked list is merely a group of nodes that are inked 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 construc- tors: 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 in