Suppose you have a doubly linked list in which the prev references have the correct values but the next references have not yet been initialized. Write a static method called initNexts$()$ that:

$1.$ Takes one parameter, a reference to the last node of the linked list

$2.$ Traverses the linked list from back to front, filling in the next references

$3.$ Returns a reference to the first node in the linked list.

You may assume that there is at least one node in the list.

$/*$

$*$ A class for representing a string using a doubly$-$linked list.

$*$ Each character of the string is stored in a separate node.

$*$

$*$ This class represents one node of the linked list. The string as a

$*$ whole is represented by storing a reference to the first node in

$*$ the linked list. Empty strings are represented using a value of null.

$*/$

public class DNode $\{$

private char ch;

private DNode prev;

private DNode next;

$/*$

$*$ Constructor

$*/$

public DNode$($char c$,$ DNode p$,$ DNode n$)\{$

this.ch $=$ c;

this.prev $=$ p;

this.next $=$ n;

$\}$

$/*$

$*$ convert $-$ converts a standard Java String object to a doubly$-$linked

$*$ list and returns a reference to first node in that doubly$-$linked list

$*/$

public static DNode convert$($String s$)\{$

if $($s$.$length$()==0)\{$

return null;

$\}$

DNode firstNode $=$ new DNode$($s$.$charAt$(0),$ null, null$)$;

DNode prevNode $=$ firstNode;

DNode nextNode;

for $($int i $=1$; i $<$ s$.$length$()$; i$++)\{$

nextNode $=$ new DNode$($s$.$charAt$($i$),$ prevNode, null$)$;

prevNode.next $=$ nextNode;

prevNode $=$ nextNode;

$\}$

return firstNode;

$\}$

$/*$

$*$ removeNexts $-$ takes a reference to the first node in a

$*$ doubly$-$linked list, sets all of the next fields in the nodes

$*$ to null, and returns a reference to the last node in the

$*$ linked list.

$*$

$*$ This method can be used to create a scenario like the one

$*$ envisioned for the initNexts$()$ method that you need to write for

$*$ Problem $3.$

$*/$

public static DNode removeNexts$($DNode first$)\{$

DNode trav $=$ first;

DNode trail $=$ null; $//$ will stay one behind trav

while $($trav $!=$ null$)\{$

$//$ the order of these statements matters!

trail $=$ trav;

trav $=$ trav.next;

trail.next $=$ null;

$\}$

$//$ at the end of the loop, trail will be pointing

$//$ to the last node

return trail;

$\}$

$//$ problem $3$

public static DNode initNexts$($DNode last$)\{$

$//$ add your implementation of the method here

$\}$

$/*$

$*$ toString $-$ creates and returns the Java string that

$*$ the current DNode represents. Note that this

$*$ method is non$-$static method, and thus it won't work

$*$ for empty strings, since they are represented by a

$*$ value of null, and we can't use null to invoke this method.

$*/$

public String toString$()\{$

String str $=""$;

DNode trav $=$ this; $//$ start trav on the current node $($this$)$

while $($trav $!=$ null$)\{$

str $=$ str $+$ trav.ch;

trav $=$ trav.next;

$\}$

return str;

$\}$

public static void main$($String$[]$ args$)\{$

DNode str $=$ DNode.convert$("$crimson$")$;

System.out.println$("$

initial str: $"+$ str$)$;

DNode last $=$ DNode.removeNexts$($str$)$;

System.out.println$("$after setting next fields to null: $"+$ str$)$;

str $=$ DNode.initNexts$($last$)$;

System.out.println$("$after calling initNexts$()$: $"+$ str$)$;

$\}$

$\}$