Question

Add a generic Node class to the Java project.

In the class

Declare the fields using the generic type parameter, follow the book specification

Define the accessor method getLink( )

Define the constructor, follow the book implementation

Note: at the definition the name of the constructor is Node, however every time you use it as a type must postfix the generic type like Node<T>

Define the addNodeAfter( ) method as explained in the PP presentation, use the generic type as needed.

Usually Node classes do not need a toString method, but it is necessary when you test the Node class and want to verify the method behaviors. The purpose of toString( ) is, as always, to create and return a string representation of the state of the object, that is message that describes the field values.

Define a toString( ) method for the Node class, follow the bulleted hints below. Fields that are object references must call toString( ) for themselves. However, null reference cannot call any method, thus you have to take care about the cases when either of the fields data or link is null. Note that toString( ) never prints.

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

If data is null, assign field1 the String value “dummy”, otherwise assign data.toString( )

If link is null, assign field2 the value “null in tail”, otherwise link.toString().

Return a message containing the field1 and field2. See the output templates below. The indentation as shown in the templates is somewhat tricky and not required for points.

Make the toString method take a dummy parameter int count, we will overload the method.

Discovery 1: toString( ) is a recursive method in this class, because it applies to the subsequent links as long as the link is not null. As such it iterates through the list.

A recursive method cannot exit until all nested recursive calls finished, and for correct execution the operating system must keep track of all activation records. Activation records occupy a lot of memory space called activation stack, therefore the stack size is usually limited around 10,000 nested recursive calls. In the applications you will check the stack size your operating system can tolerate when your toString( ) method is called.

Add another non-recursive toString method to the class, this does not take any parameter and ignores the link field. It simply returns data.toString( ) if data is not null, otherwise it returns null.

Testing the Node class

Add a NodeAppplication class to the project to test your nodes and methods.

Specify the generic type parameter as String, declare and instantiate a head node with constructor parameters “Paul” and null (the type for head is Node<String>).

Declare tail in the main method and assign it the return value of the addNodeAfter method called with respect to head, and with parameter ”Saul” (the type for tail is Node<String>).

Call and print the toString( 1 ) method (the one with dummy parameter) with respect to head, you must have output Figure 1.

Call addNodeAfter for head and then for tail repeatedly to produce output

Figure 2 (must maintain the tail reference properly).

Discovery 2: addNodeAfter( ) cannot create a new head since there is no precursor to head, head is not a link.

You create an artificial node named dummy (not part of the list of the actual data structure) to be positioned in front of head. The dummy node has nothing to do with the dummy parameter count.

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

Call addNodeAfter with respect to dummy with parameter “Raul”, and assign the return value to head.

Call addNodeAfter for head with correct parameters and call toString( 1 ) for dummy to produce output Figure 3.

Change the toString (int count) definition such that count is updated in the parameter of the nested call with respect to link (now the dummy parameter is no longer dummy). The initial call should pass 1 for parameter. Since this test does not print the toString return value, you must add a printing statement first in the method’s body which prints the count value to the console.

Create a linked list of 100,000 nodes, each node carries a String data (those can all be same “Paul”). Call to string(1) and observe the last print of count before a StackOverflowError is thrown. Report your result as a comment added after the NodeApplication class.

Iterate over your large linked list, call the no-parameter non-recursive toString method w.r.t all the 100,000 nodes and print the return value to the console (you must use a loop).

Output templates

data: Paul

link: data: Saul

    link: null in tail!

                   Figure 1

data: Paul

link: data: mauls

    link: data: Saul

         link: data: Saul

             link: data: mauls

                 link: data: Raul

                      link: null in tail!

                   Figure 2                                                          

data: dummy

link: data: Raul

    link: data: mauls

        link: data: Paul

             link: data: Paul

                 link: data: mauls

                      link: data: Saul

                          link: data: Saul

                               link: data: mauls

                                   link: data: Raul

                                       link: null in tail!

Answer 1

File: NodeApplication.java

public class NodeApplication {

   public static void main(String[] args) {
       //For output 1
       Node<String> head = new Node<String>("Paul", null);
       Node<String> tail = head.addNodeAfter("Saul", null);
       System.out.println(head.toString(1));
      
       //For output 2
       tail = head.addNodeAfter("mauls", null);
       tail = tail.addNodeAfter("Saul", null);
       tail = tail.addNodeAfter("Saul", null);
       tail = tail.addNodeAfter("mauls", null);
       tail = tail.addNodeAfter("Raul", null);
       System.out.println(head.toString(1));
      
       //For output 3
       Node<String> dummy = new Node<String>("dummy", head);
       Node<String> temp = head;
       head = dummy.addNodeAfter("Raul", null);
       tail = head.addNodeAfter("mauls", null);
       tail = tail.addNodeAfter("Paul", temp);
       System.out.println(head.toString(1));
      
       //Creating list of 100000 nodes
       head = new Node<String>("Paul", head);
       tail = head;
       for(int i = 1;i<100000;i++){
           tail = tail.addNodeAfter("Paul", null);  
       }
      
       //head.toString(1);     //Code which creates StackOverflowError error
      
       //Printing toString for each node
       for(Node<String> pos = head; pos != null; pos = pos.getLink()){
           System.out.println(pos.toString());
       }
   }

}

class Node<T>{
   private T data;
   private Node<T> link;
  
   //constructor
   public Node(T data, Node<T> link) {
       super();
       this.data = data;
       this.link = link;
   }

   public Node<T> getLink() {
       return link;
   }
  
   //method to add node to existing node
   public Node<T> addNodeAfter(T data, Node<T> node){
       Node<T> nextNode = new Node<T>(data, node);
       link = nextNode;
       return nextNode;
   }

   //Recursive toString(int) method
   public String toString(int count) {
       //System.out.println(count);        //Code to display count during StackOverflowError
       String field1 = "", field2 = "";
       if (data == null){
           field1 = "dummy";
       } else {
           field1 = data.toString();
       }
       if (link == null){
           field2 = "null in tail";
       } else {
           field2 = link.toString(count+1);
       }
      
       // Code to adjust indentation
       String indentation = "";
       for (int i = 1;i<count;i++){
           indentation += "   ";
       }
      
       return "data: " + field1 + "\n" + indentation +"link: " + field2;   // Final value of toString method
   }

   // Non-Recursive toString() method
   public String toString() {
       if (data != null)
           return data.toString();
       else
           return null;
   }
  
  
}

The last count value displayed before StackOverflowError occured was 5817.

Below is stack trace for StackOverflowError

Exception in thread "main" java.lang.StackOverflowError
   at java.nio.charset.CharsetEncoder.encode(CharsetEncoder.java:579)
   at sun.nio.cs.StreamEncoder.implWrite(StreamEncoder.java:271)
   at sun.nio.cs.StreamEncoder.write(StreamEncoder.java:125)
   at java.io.OutputStreamWriter.write(OutputStreamWriter.java:207)
   at java.io.BufferedWriter.flushBuffer(BufferedWriter.java:129)
   at java.io.PrintStream.write(PrintStream.java:526)
   at java.io.PrintStream.print(PrintStream.java:597)
   at java.io.PrintStream.println(PrintStream.java:736)
   at Node.toString(NodeApplication.java:44)