In this assignment you are to implement a simplified Node as a generic class wit
ID: 3869892 • Letter: I
Question
In this assignment you are to implement a simplified Node as a generic class with a type parameter E for the elements stored in a linked list.
Exercises - Requirements
(5pts) Add a generic Node class to the Java project.
(20pts) 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.
(25pts) 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. For this program you also defined overloaded versions of toString.
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, see point 5 below (a dummy parameter is to change the method signature, it is not needed and not used in 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.
(5pts)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 (this is the “official” toString method, which overrides toString Object).
(44pts) 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 are to 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 of the first toString method.
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 as the 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 toString(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!
Figure 3
nter an element for the array: 4 nter an element for the array: 4 nter an element for the array: 4 nter an element for the array: 4 Enter an element for the aray 4 Enter an element for the aray 6 nter an element for the array:1 Enter an element for the array:2 Enter an element for the array:3 Enter an element for the array-100 4 4 444 6 1 2 3 he sum is 32 The total run sum over 1 runs is 32 Continue? Enter an element for the array: 2 Enter an element for the array:2 Enter an element for the array: 2 Enter an element for the array: 2 Enter an element for the array 2 nter an element for the array:-100 he sum is 10 The total run sum over 2 runs is 42 ontinue?Explanation / Answer
Given is the code and output. Please don't forget to rate the answer if it helped. Thank you.
Node.java
public class Node<T> {
private T data;
private Node<T> link;
public Node(T data, Node<T> link)
{
this.data = data;
this.link = link;
}
public T getData()
{
return data;
}
public Node<T> getLink()
{
return link;
}
public void setData(T data)
{
this.data = data;
}
public void setLink(Node<T> link)
{
this.link = link;
}
public Node<T> addNodeAfter(T data)
{
this.link = new Node(data, this.link);
return this.link;
}
public String toString(int count)
{
System.out.println("count = " + count);
String field1 = "";
String field2 = "";
if(data == null)
field1 = "data: dummy";
else
field1 = "data: " + data.toString();
if(link == null)
field2 = "link: null in tail!";
else
field2 = "link: " + link.toString(count + 1);
return field1 + " " + field2;
}
}
NodeApplication.java
public class NodeApplication {
public static void main(String[] args) {
Node<String> head = new Node<String>("Paul", null);
Node<String> tail = head.addNodeAfter("Saul");
System.out.println(head.toString(1)); //print head
//add other nodes as in Fig 2
head.addNodeAfter("mauls");
tail = tail.addNodeAfter("Saul");
tail = tail.addNodeAfter("mauls");
tail = tail.addNodeAfter("Raul");
System.out.println(head.toString(1)); //print head
//create dummy node before head
Node<String> dummy = new Node<String>(null, head); //pass head as link
head = dummy.addNodeAfter("Raul");
Node<String> next = head.addNodeAfter("mauls");
next = next.addNodeAfter("Paul");
System.out.println(dummy.toString(1));//print dummy with count = 1
}
}
output
count = 1
count = 2
data: Paul link: data: Saul link: null in tail!
count = 1
count = 2
count = 3
count = 4
count = 5
count = 6
data: Paul link: data: mauls link: data: Saul link: data: Saul link: data: mauls link: data: Raul link: null in tail!
count = 1
count = 2
count = 3
count = 4
count = 5
count = 6
count = 7
count = 8
count = 9
count = 10
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!