Here is the code!

class DNode {

// Node for building a Doubly-linked list

String contents;

DNode next;

DNode prev;

DNode (String k) { // Constructor: builds a node which can be searched forwards and backwards

next= null; prev= null;

contents= k;

}

DNode (String k, DNode prev, DNode next){ // Constructor: builds a node with given references

this.prev = prev;

this.next = next;

this.contents = k;

}

DNode searchForwards(DNode curr, String key) { //TODO

if(curr.contents==key)

return curr;

if(curr.next==null)

return null;

else

return searchForwards(curr.next,key);

}

DNode searchBackwards(DNode curr, String key) { //TODO

if(curr.contents==key)

return curr;

if(curr.prev==null)

return null;

else

return searchBackwards(curr.prev,key);

}

void insertAfter(DNode curr, DNode newNode) { //TODO

DNode temp=curr.next;

curr.next=newNode;

newNode.next=temp;

temp.prev=newNode;

newNode.prev=curr;

}

void insertBefore(DNode curr, DNode newNode) { //TODO

DNode temp=curr.prev;

curr.prev=newNode;

newNode.prev=temp;

temp.next=newNode;

newNode.next=curr;

}

}

class DLSList {

// Class invariant: The nodes in the list are sorted (ascending) according to the contents

// AND numNodes == the number of nodes in the list

// AND (lastVisited points to the node which was last valid access after method visit is called

// OR is set to head (in case removeNode demands it) or it is initialised)

DNode head; // The first node in the list

DNode lastVisited; // The address of the node last visited

int numNodes; // The number of nodes in the list

DLSList (){

head= null;

lastVisited= null;

numNodes= 0;

}

void addNewNode(DNode newNode) { //TODO

// Post: newNode is inserted into the current list in correct sorted order

// numNodes is adjusted to be equal to the number of nodes in the list

}

void removeNode(String key) { //TODO

// Post: All occurrences of nodes with contents field equal to key are removed.

// If lastVisited points to one of the removed nodes, then lastVisited is set to head

// numNodes is adjusted to be equal to the number of nodes in the list

}

DNode visit(String key) { //TODO

// Post: Returns the address of the first node (in ascending order) whose contents equal key, and null if there is no such node;

// lastVisited is set to the address returned if it is not null, otherwise lastVisited remains unchanged

return null;

}

All methods to be implemented are labelled //TODO