Lab: 28 - LinkedList Implementation

Assigned

Friday, 3 November 2023

In this lab, you will develop a singly linked list (a singly-linked queue using a linked-list to store data). You will work with the following files:

• QueueNode.java stores queue items.
• Queue207.java defines an interface for queue operations.
• Queue207Implementation.java implements the Queue207 interface.

Create an Eclipse project called queues. Import the Queue207 java source file from the following path in MathLAN /home/jimenezp/csc207/LinkedListImp to the Eclipse project.

QueueNode

A Queue can be implemented by a singly linked list of QueueNodes. The QueueNode.java class has the following structure:

public class QueueNode<AnyType> { 
    private AnyType data; // data is stored inside a node. 
    private QueueNode<AnyType> next; // this field references the next node. 
 
    public QueueNode() { 
        data = null; 
        next = null; 
    } 
 
    public QueueNode( AnyType origData, QueueNode<AnyType> origNext ) { 
        data = origData; 
        next = origNext; 
    } 
} 

The data field stores a reference to some actual data. The next field stores a reference to the next QueueNode of the list. This class has two overloaded constructors: one that sets the data and next fields to null and the other sets them to parameters passed to the constructor.

You will used this code in your Queue207Implementation.java. Create your Node as a static nested class.

• Would you need getters or setters methods for your nested class?
• What happens if you change the constructors modifier to private (can you still access them)?
• Do we need the default constructor? Which missing constructor will be helpful to have?

Write down your answers and verify them when you are implementing the Queue207Implementation class

The LinkedList

Write the Queue207Implementation class that implements the Queue207 interface.

By considering the above structure, the Queue207Implementation class contains three private fields: size, head, and tail.

• size specifies the number of items in the queue.
• head and tail references mark the two ends of the queue as shown in the following figure:

Items are deleted from the head reference and inserted at the tail reference. This indicates that the items are placed into the queue in the order that they are inserted there. In other words, the item, referenced by head, is the first item inserted in the queue while the item, referenced by tail, is the last item inserted in the queue.

Provide implementations for the constructor, add, remove, element, and size methods.

The implementation details of important methods in Queue207Implementation class are explained below:

• Queue207Implementation constructor: initializes three fields: size, head, and tail. size is initialized to zero. head and tail are initialized to null.

• add method: instantiates a new QueueNode that contains the specified data and null in the next field.
  • The next field of the QueueNode, referenced by the old tail of the queue, is updated to reference the new QueueNode.
  • The tail field of the queue is updated to reference the new QueueNode.
  • If the new QueueNode is the first QueueNode of the queue, the head and tail fields are updated to reference the new QueueNode.
• remove method: extracts data from a QueueNode referenced by the head field.
  • The head field is updated to reference the next QueueNode of the queue.
  • If data is extracted from the last QueueNode of the queue, the tail field is updated to reference null.

The Client Program

• Write Queue207ImplementationTester class to test all of the methods.
  • As a test case, create a queue and call the following methods in-order: add, add, remove, element, size, add, size, remove, remove, size. Verify the tester output.
  • Test the edge-cases.
  • Test your LinkedList with two different types of Objects.

Lab Submission

• (3 points) Queue207Implementation.java
• (1/2 point) Queue207ImplementationTester.java and output of running your test.
• (1/2 point) Lab report with posted questions

Remember: Do not use magic numbers, write your code anticipating errors and print user-friendly error messages, all your public methods should be well documented (use Javadoc comments). Please include comments or organize your code and report in a way that will help the grader to find the answer to the exercises or posted questions.