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

/** The list head */ private Node head;

/** A Node is the building block for a single-linked list. */ private static class Node { // Data Fields

/** The reference to the data. */ private E data; /** The reference to the next node. */ private Node next;

// Constructors /** * Creates a new node with a null next field. * @param dataItem The data stored */ private Node(E dataItem) { data = dataItem; next = null; }

/** * Creates a new node that references another node. * @param dataItem The data stored * @param nodeRef The node referenced by new node */ private Node(E dataItem, Node nodeRef) { data = dataItem; next = nodeRef; } } //end class Node

/** * Finds the size of a list. * @param head The head of the current list * @return The Size of the Current List */ private int size(Node head) { if (head == null) { return 0; } else { return 1 + size(head.next); } }

/** * Wrapper method for finding the size of a list. * @return The size of the list */ public int size() { return size(head); }

/** * Returns the string representation of a list. * @param head The head of the current list * @return The state of the current list */ private String toString(Node head) { if (head == null) { return ""; } else { return head.data + " " + toString(head.next); } }

/** * Wrapper method for returning the string representation of a list. * @return The string representation of the list */ @Override public String toString() { return toString(head); }

/** * Replaces all occurrences of oldObj with newObj. * @post Each occurrence of oldObj has been replaced by newObj. * @param head The head of the current list * @param oldObj The object being removed * @param newObj The object being inserted */ 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); } }

/* Wrapper method for replacing oldObj with newObj. * @post Each occurrence of oldObj has been replaced by newObj. * @param oldObj The object being removed * @param newObj The object being inserted */ public void replace(E oldObj, E newObj) { replace(head, oldObj, newObj); }

/** * Adds a new node to the end of a list. * @param head The head of the current list * @param data The data for the new node */ 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. } }

/** * Wrapper method for adding a new node to the end of a list. * @param data The data for the new node */ 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 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 */ 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); }

/** * 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 aListInt = new LinkedListRec();

aListInt.add(2);

aListInt.add(4);

aListInt.add(15);

aListInt.add(8);

aListInt.add(10);

aListInt.add(3);

aListInt.add(6);

aListInt.add(1);

System.out.println("The integer type linked list is:");

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

int index;

int item;

//Uncomment the following code to test the assignment A05_Q1:

/* item = 10;

index = aListInt.searchIndex(item);

if (index >= 0) {

System.out.printf("The item %d can be found in the linked list, "

+ "its index is %d.", item, index);

}

else {

System.out.printf("The item %d cannot be found in the linked list.", item);

}

item = 12;

index = aListInt.searchIndex(item);

if (index >= 0) {

System.out.printf(" The item %d can be found in the linked list, "

+ "its index is %d.", item, index);

}

else {

System.out.printf(" The item %d cannot be found in the linked list.", item);

}*/

}

}