Using Java language,

1. Implement addBefore(String beforeThis, String toAdd)in the Doubly linked list. (hint: use findNode in this method and check the code for addAfter!)

2. Implement toStringBackwards(), which returns a String containing all the Strings held in the list beginning at the tail and ending at the head. (hint: this should look similar to the code in toString!)

3. Run main.java. Your output should be:

   ' Tony Cheryl Bob Susan Jessica ' ' Jessica Susan Bob Cheryl Tony ' 

   ' Susan Jessica ' ' Jessica Susan ' 

DLinkedList.java

public class DLinkedList { private Node firstNode; private Node lastNode;

public DLinkedList() { // create two dummy Nodes for firstNode and lastNode to reference firstNode = new Node("Head"); lastNode = new Node("Tail");

firstNode.setNext(lastNode); lastNode.setPrev(firstNode); } // methods go here

public void addToStart(String s) { Node nodeToAdd = new Node(s); Node currentFirst = firstNode.getNext(); nodeToAdd.setNext(currentFirst); nodeToAdd.setPrev(firstNode); currentFirst.setPrev(nodeToAdd); firstNode.setNext(nodeToAdd); }

public void addToEnd(String s) { Node nodeToAdd = new Node(s); Node currentLast = lastNode.getPrev(); nodeToAdd.setPrev(currentLast); nodeToAdd.setNext(lastNode); currentLast.setNext(nodeToAdd); lastNode.setPrev(nodeToAdd); }

public void remove(String stringToRemove) { Node nodeToRemove = findNode(stringToRemove); if(nodeToRemove != null) { nodeToRemove.getPrev().setNext(nodeToRemove.getNext()); nodeToRemove.getNext().setPrev(nodeToRemove.getPrev()); } }

public boolean addAfter(String afterThis, String toAdd) { Node nodeToAddAfter = findNode(afterThis); if(nodeToAddAfter == null) { return false; } Node nodeToAdd = new Node(toAdd); nodeToAdd.setPrev(nodeToAddAfter); nodeToAdd.setNext(nodeToAddAfter.getNext()); nodeToAddAfter.getNext().setPrev(nodeToAdd); nodeToAddAfter.setNext(nodeToAdd); return true; }

public boolean addBefore(String beforeThis, String toAdd) { // TODO return false; }

private Node findNode(String s) { for(Node iterator = firstNode.getNext(); iterator.getNext() != null; iterator = iterator.getNext()) { if(iterator.getValue().equals(s)) { return iterator; } } return null; }

public String toStringBackwards() { // TODO return null; }

public String toString() { StringBuilder sb = new StringBuilder(); sb.append("' "); for(Node n = firstNode.getNext(); n.getNext() != null; n = n.getNext()) { sb.append(n).append(" "); } sb.append("'"); return sb.toString(); }

private class Node { private Node next = null; private Node prev = null; String value;

private Node(String s) { value = s; } private Node getNext() { return next; } private Node getPrev() { return prev; } private void setNext(Node n) { next = n; } private void setPrev(Node n) { prev = n; } private String getValue() { return value; } public String toString() { return value;} } }

Main.java

public class Main { public static void main(String[] args) { DLinkedList list = new DLinkedList(); list.addToEnd("Bob"); list.addAfter("Bob", "Jessica"); list.addBefore("Jessica", "Susan"); list.addToStart("Cheryl"); list.addBefore("Cheryl", "Tony"); System.out.println(list); System.out.println(list.toStringBackwards()); System.out.println(); list.remove("Bob"); list.remove("Cheryl"); list.remove("Tony"); System.out.println(list); System.out.println(list.toStringBackwards()); } }