/** * A recursive linked list class with recursive methods. * @param The element type **/ public class LinkedListRec {

private Node head;

private static class Node { // Data Fields private E data; private Node next;

private Node(E dataItem) { data = dataItem; next = null; }

/** * Creates a new node that references another node. */ private Node(E dataItem, Node nodeRef) { data = dataItem; next = nodeRef; } } //end class Node public void insertBefore(E target, E inData) { if (head == null) { head = new Node<>(target, null); return; } if (head.data.equals(target)) { head = new Node<>(inData, head); return; } insertBefore(target, inData, head); }

/** * Recursive method to insert a specified data object before the * first occurrence of another specified data object. If the object is * not found, then the item is inserted at the end of the list. * @param target the item that inData is to be inserted before * @param inData the item to be inserted * @param node the current node */ private void insertBefore(E target, E inData, Node node) { if (node.next == null) { node.next = new Node<>(inData, null); return; } if (target.equals(node.next.data)) { node.next = new Node<>(inData, node.next); return; } insertBefore(target, inData, node.next); } public void insertAfter(E target, E inData) { if (head == null) { head = new Node<>(target, null); return; } if (head.data.equals(target)) { head.next = new Node<>(inData, head.next); return; } insertAfter(target, inData, head); } //A05_Q2 //Please complete the following method /** * Recursive method to insert a specified data object after the * first occurrence of another specified data object. If the object is * not found, then the item is inserted at the end of the list. * @param target the item that inData is to be inserted after * @param inData the item to be inserted * @param node the current node */ private void insertAfter(E target, E inData, Node node) {

} private int size(Node head) { if (head == null) { return 0; } else { return 1 + size(head.next); } }

public int size() { return size(head); }

private String toString(Node head) { if (head == null) { return ""; } else { return head.data + " " + toString(head.next); } }

@Override public String toString() { return toString(head); }

private void replace(Node head, E oldObj, E newObj) { if (head != null) { if (oldObj.equals(head.data)) { head.data = newObj; } replace(head.next, oldObj, newObj); } }

public void replace(E oldObj, E newObj) { replace(head, oldObj, newObj); }

private void add(Node head, E data) { // If the list has just one element, add to it. if (head.next == null) { head.next = new Node<>(data); } else { add(head.next, data); // Add to rest of list. } }

public void add(E data) { if (head == null) { head = new Node<>(data); // List has 1 node. } else { add(head, data); } }

/** * Removes a node from a list. * @post The first occurrence of outData is removed. * @param head The head of the current list * @param pred The predecessor of the list head * @param outData The data to be removed * @return true if the item is removed * and false otherwise */ private boolean remove(Node head, Node pred, E outData) { if (head == null) // Base case -- empty list. { return false; } else if (head.data.equals(outData)) { // 2nd base case. pred.next = head.next; // Remove head. return true; } else { return remove(head.next, head, outData); } }

/** * Wrapper method for removing a node (in LinkedListRec). * @post The first occurrence of outData is removed. * @param outData The data to be removed * @return true if the item is removed, * and false otherwise */ public boolean remove(E outData) { if (head == null) { return false; } else if (head.data.equals(outData)) { head = head.next; return true; } else { return remove(head.next, head, outData); } } /** * Method to insert an object at a specified index * @param obj The object to be inserted * @param index the index */ public void insert(E obj, int index) { if (index < 0) { throw new IndexOutOfBoundsException(); } if (index == 0) { head = new Node<>(obj, head); } else { insert(obj, head, index - 1); } }

/** * Method to insert an object at a specified index * @param obj The object to be inserted * @param pred the node preceding the node at the current index * @param index the current index */ private void insert(E obj, Node pred, int index) { if (pred == null) { throw new IndexOutOfBoundsException(); } if (index == 0) { pred.next = new Node<>(obj, pred.next); } else { insert(obj, pred.next, index - 1); } } /** * Method to search a LinkedListRec to see if an item is contained * in it. * @param item The item being sought * @return true if the item is in the list, false otherwise */ public boolean search(E item) { return search(item, head); }

/** * Recursive method to search a LinkedListRec. * @param item the item being sought. * @param node the current node * @return true if the item being sought is found */ private boolean search(E item, Node node) { if (node == null) { return false; } if (item.equals(node.data)) { return true; } return search(item, node.next); } }

______________________________

public class LinkedListRecTest {

public static void main(String[] args) {

LinkedListRec aListDouble = new LinkedListRec();

aListDouble.add(2.5);

aListDouble.add(3.4);

aListDouble.add(5.8);

aListDouble.add(8.2);

aListDouble.add(16.5);

System.out.println("The current double type linked list:");

System.out.println(aListDouble.toString());

aListDouble.insertAfter(2.5, 10.5);

System.out.println("The updated double type linked list: insert after 2.5:");

System.out.println(aListDouble.toString());

aListDouble.insertAfter(16.5, 1.5);

System.out.println("The updated double type linked list: insert after 16.5:");

System.out.println(aListDouble.toString());

aListDouble.insertAfter(8.2, 120.5);

System.out.println("The updated double type linked list: insert after 8.5:");

System.out.println(aListDouble.toString());

}

}