In this lab you are going to implement a linked list that can have objects added to the back and removed from the front, otherwise known as a queue.
The file LinkedList.java contains
a template for a linked list class. It has instance data for
references to the first and last nodes in the list. These
references are of type Node, which is a private sub-class of
LinkedList. The node class has two public instance variables,
object and next.
The object instance variable is a generic type that
is a reference to the data stored in the linked list.
The next instance variable is a reference to the next
node in the linked list. If the next reference is null, then the
node is the last element in the list.
The LinkedList class contains a method
stub, addLast, for adding to the linked list. The
method should add the specified object to the end of the linked
list. The method should begin by creating a new node with the
object set to the object to add and the next reference set to null
(because it is the end of the list). Next, if the list is empty,
it should set the first and last instance variables to reference
the new node. If the list is not empty, it should update the
current last node in the list to reference the new node as the
next node and update the last instance variable to reference the
new node. Finally, increment the size instance variable.
Before testing the add method you will need to be able to print
a linked list. Complete the toString method. The
method should return a string that is a concatenation of all of
the elements in the linked list. In order to generate this string
you should create a Node variable that is initialized to the first
node in the list and write a loop that concatenates a string
representation of the object in the current node to the return
string and updates the current node to be the next node in the
list. The loop should terminate when there is no next element.
Write a program that tests both the add and
the toString method. Be sure to test the to string
on an empty list as well as a full list.
Complete the removeFirst method. The method
should remove the first element from the linked list. If the list
is empty, the method should throw
a NoSuchElementException
exception. If the list contains only one element, the method
should set the first and last references to null. If the list
contains more than one element, the method should set the first
reference to be the second element in the list. Finally,
decrement the size variable. Note, the remove method does not
actually delete any data. It simply changes references such that
there are no variables that reference the deleted node.
Eventually, the Java garbage collector will delete the node and
its data from memory. Test your remove method before
proceeding.
Queues are useful for storing data that needs to be processed. In the maze traversal program that we created in class we needed to store the location of branches in the path for future processing. Using a queue it is possible to create a looping version of the maze traversal program.
The file Maze.java contains the maze
traversal program that we created in class. Rewrite
the canTraverse method to use a loop and a queue
instead of recursion. The looping version should begin by adding
the location of the start cell to an empty queue. Then, while the
queue is not empty it should remove a cell from the queue. If the
removed cell is the end cell then the loop should stop and the
method should return true. If the cell is not the end cell it
should add all of its neighboring cells that are valid to the
queue. If the queue becomes empty without ever traversing to the
end cell, then the method should return false.
Submit a zip file of your code on the course Inquire site that uses your last names as the file name.