Assignment •  Development Guide •  Code •  Checklist •

HW5 Assignment

What to do?

You must turn in your program by Wednesday, October 27th, 2021 at 11:59am (NOON).
In this assignment, you are to create a polymorphic generic container based on a linked-list data structure. In List.java, the List, ListEngine, Node, and NodeEngine classes are defined. The list is circular, so the next pointer of the last item points to the first item of the list, and the pre pointer of the first item points to the last item in the list. We keep track of the end item in the list with the end data field of ListEngine.

The ListEngine methods to write in List.java:

ListEngine (Base sample, String caller)
void jettisonList ()
void advanceNext ()
void advancePre ()
boolean checkToGoForward(long where)
boolean isEmpty ()
boolean insert (Base element, long where)
boolean locate (long where)
Base remove (long where)
Base view (long where)
void writeReverseList (PrintStream stream)

The NodeEngine methods to write in List.java:

NodeEngine (Node newNode, Base element, String caller)
void jettisonNodeAndData ()
void jettisonNodeOnly
Node insert (Node thisNode, Base element)
Base remove ()
Base view ()

Additional file and method headers to write in BaseStack.java:

In addition to writing file and method headers for all the methods you write, write headers for all methods in BaseStack.java. The actual methods are provided for you.

For all methods for the ListEngine class, make sure to include code to display the corresponding catastrophic error and debug messages. You can find all the messages you need at the beginning of the List.java file.

Method Descriptions

ListEngine methods

ListEngine Constructor:

Properly initialize the data fields of the ListEngine. Don't forget to increment the listCounter.

jettisonList:

Stop tracking the memory for all nodes, all data, and the list itself.

advanceNext:

Move the end of the list forward by one Node. This effectively shifts the elements of the list forward by one.

advancePre:

Move the end of the list backward by one Node. This effectively shifts the elements of the list backward by one.

checkToGoForward:

This method checks whether it would be more efficient to reach item number in the list by looping forwards from the end of the list (true is returned) or backwards from the end of the list (false is returned). For example, if the list had 50 elements, it would be more efficient to loop forwards from the last element to find the 5th element. However, to find the 45th element, it would be more efficient to loop backwards from the last element. Note: you have the flexibility to change the signature of this method to have a different return value or parameters depending on your implementation.

isEmpty:

Check whether the list is empty or not.

insert:

Insert a Base object into the list.

locate: // This should only be called from insert, remove, and view

This method is used to eliminate code duplication in the list methods by finding the location at which we wish to insert, remove, or view. locate should be used to locate the Node at location where. If your implementation of locate changes the end pointer of the list, be sure to save that value before calling this method. Note: you have the flexibility to change the signature of this method to have a different return value or parameters.

remove:

Remove a node from the list, return its data.

view:

Return the data stored at location where.

writeReverseList:

Write the elements of ListEngine backwards, starting with the last item. The list is printed to filestream stream.

NodeEngine methods

NodeEngine Constructor:

Creates a new node to hold element, or, if sample of the ListEngine is non-NULL, a copy of element.
Refer to your notes if you don't know what I am talking about.

jettisonNodeAndData

Jettison the NodeEngine and the data that it holds.

jettisonNodeOnly

Jettison the NodeEngine.

insert:

Create a new Node object to hold element. This new node is then incorporated into the list at the location AFTER thisNode. The insert method should return the new Node that it created.

remove:

"Unlinks" this Node object to be removed from the list by arranging the references of the surrounding Node objects so that they no longer reference to this Node object. The memory associated with the Node object is jettisoned, but the Node object's data is not jettisoned. A reference to the data is returned.

view:

Return the data stored in the Node object.

Implementation Restrictions

Due to the nature of the circular linked list, where insertion, remove or view operations can occur between any two nodes, having a multi-line block of code to handle an operation at the beginning, another block for sorted, and another block for the end means that you aren't taking full advantage of the efficiencies that the circular list has to offer. Therefore:

For full credit, the insert method of ListEngine should only contain one call to the insert of Node.
For full credit, the remove method of ListEngine should only contain one call to the remove of Node.
For full credit, the view method of ListEngine should only contain one call to the view of Node.

Grading breakdown

Comments/Documentation:

1/6

Style:

1/6

Correctness/Execution:

2/3

How to get started?

Enter the following commands into the terminal.

cd
cd ../public/hw5
make install
cd
cd hw5/java
mv List.java.empty List.java
ls

 

Assignment •  Development Guide •  Code •  Checklist •