This class contains a generic Node inner class like the examples you$$ve seen in the lecture, except it has a prev $($short for $$previous$)$ instance variable in addition to next. Note that the data instance variable has the generic type T$.$

This class uses the generic Node class. Note that every Node declaration is $$Node$$ because every node$$s data is one of the characters A$,$ C$,$ G$,$ or T$.$The constructors for this class are already written. Your job is to finish writing $7$ methods plus a main method for testing.

append$($Node n$)$

matches$($Node startNode, String target$)$

find$($String target$)$

extract$($Node firstExtractedNode, Node lastExtractedNode$)$

insert$($DNALinkedList insertMe, Node insertionPoint$)$

reverse$()$

transpose$($String transposon, String target$)$

main$($String$[]$ args$).$ The comments in the methods will tell you what to do$.$

First, try to complete the first four methods $($append$,$ matches, find, extract$)$ that we talked about in class. Then, begin working on implementing the last three methods $($insert$,$ reverse, and transpose$).$

Reverse Method

The reverse method reverses the order of the nodes. Note that you are doing a similar problem for your homework, but on a singly linked list. Do you think the problem on your homework is harder or easier?

Transposon Method

This method removes sequence matching transposon, reverses it$,$ and inserts it back into this list immediately before target. It throws IllegalArgumentException if it can't find transposon or target. Hint: Use the methods you just wrote.

Main Method

In order to complete the main$()$ method, you will need to create your own test case. The code prompts you to specify a chromosome string, a transposon string, and a target string. These will be used to test the transpose$()$ method, which calls all the others. One way to test would be to use a real chromosome. The shortest human chromosome is $48$ million bases long.

package linked;

public class DNALinkedList

$\{$

private static class Node

$\{$

private T data;

private Node prev; $//$ previous

private Node next;

Node$($T data$)$

$\{$

this.data $=$ data;

$\}$

$//$ Returns data of prev node, this node, and next node. Uses $"<"$ if prev is

$//$ null, and $">"$ if next is null.

public String toString$()$

$\{$

String s;

if $($prev $==$ null$)$

s $="<"$;

else s $=$ prev.data.toString$()$;

s $+=$ data;

if $($next $==$ null$)$

s $+=">"$;

else

s $+=$ next.data;

return s;

$\}$

$\}$

private Node head; $//$ head.prev is always null

private Node tail; $//$ tail.next is always null

public DNALinkedList$($String s$)$

$\{$

append$($s$)$;

$\}$

$//$ Used by extraction methods. Not for public use.

private DNALinkedList$($Node head, Node tail$)$

$\{$

this.head $=$ head;

head.prev $=$ null;

this.tail $=$ tail;

tail.next $=$ null;

$\}$

$//$ Converts arg to nodes which are appended to end of this list.

public void append$($String s$)$

$\{$

for $($int i$=0$; i$($ch$))$;

$\}$

public String toString$()$

$\{$

String s $=$ "DNALinkedList: $"$;

if $($head $==$ null$)$

s $+=$ "Empty";

else

$\{$

Node n $=$ head;

while $($n $!=$ null$)$

$\{$

s $+=$ n$.$data;

n $=$ n$.$next;

$\}$

$\}$

return s;

$\}$

$//$ Appends n to tail of this list.

public void append$($Node n$)$

$\{$

$//$ Corner case: empty list.

if $($tail $==$ null$)$

$\{$

n$.$prev $=???$;

n$.$next $=???$;

head $=???$;

tail $=???$;

$\}$

$//$ General case.

else

$\{$

$//$fill this in

$\}$

$\}$

$//$ Returns true if the nodes starting at startNode match the target string. For example,

$//$ if the linked list looks like this:

$//($A$)>($B$)->($C$)->($D$)->($E$)->($F$)$

$//$ and if startNode is the $2$nd node $($B$),$ then matches$($startNode$,$BCDE$)$ should return true.

private boolean matches$($Node startNode, String target$)$

$\{$

return false;

$\}$

$//$ If this list contains a chain of nodes whose data is the target, returns

$//$ the node at the start of that chain. If the target appears multiple times

$//$ in this list, returns the first occurrence. If the target is not in this list,

$//$ returns null.