Exercise

In the class Fields are: T data, Node link. You need - getLink( ) and setLink( ).

Constructor: generic.

Define the addNodeAfter( ) method, use the generic type as needed.

3. Add a toString() method to the Node class. toString( ) is a recursive method in this class. In the applications you will check the stack size your operating system can tolerate when your toString( ) method is called.

Follow the steps below to implement toString().

toString( ) takes no parameter and returns a String (note that it overloads the Object toString method)

Declare two local variables of type String, say var1, var2, both initialized to the empty string.

If data is null, assign var1 the String value dummy, otherwise assign data.toString( ) (notice that this is not a recursive call)

If link is null, assign var2 the value null value, otherwise assign link.toString() (notice that this is the recursive call).

Return a message such that it concatenates var1 and var2 with a character separating them.

See the output templates below for hint.

4. Add a method displayList() to the Node class.

This method is also recursive and it keeps printing the data stored in the list, from head to tail.

The method is void and takes no parameter

Prints data to the console

if link is null, the method returns (the base case of the recursive sequence)

otherwise calls displayList() with respect to link

5. Testing the Node class

Add a NodeAppplications class to the project to test your methods.

Specify the generic type parameter of the Node class as String, declare and instantiate a head node with constructor parameters Sunday and null.

Test toString( ) for head, print the return value to the console.

Declare tail in the main method and assign it the return value of the addNodeAfter( ) method called with respect to head. Use the data value, Monday as parameter.

Test toString( ) again with respect to head to see if the recursion works as intended.

Call addNodeAfter once with respect or head to insert an element between the current head and tail.

Create an artificial node named dummy (not part of the list of the actual data structure) to be positioned in front of head.

Declare dummy as a node reference and instantiate it: the constructor takes parameters null for data and head for link

Call addNodeAfter with respect to dummy three times to extend the list at head.

Call toString( ) with respect to dummy and print the result to produce the required output. Using the display( ) method the next test will reveal the size of the activation stack.

Create a new linked list of length 100,000 such that it stores all the integer numbers from 1 to 100,000. The numbers only used for printing, therefore we represent the numbers in String format (use the valueOf() method from the String class)). In this manner we can use the same Node type as before.

Re-assign head a new Node to store 1 as a String (do not use the literal, use the valueOf( ) method).

Run a for loop and feed the list at tail until the list contains all the numbers from 1 to 100,000. Call display( ) with respect to head and run the program.

Create a comment block after the NodeApplications class to report (i) the exception thrown that stopped the program (ii) the last number printed to the console, which shows the number of recursive executions of display( ).