1. reverse() Method for List class Start with classes List.java and ListDemo.java that can be found next to this assignment. **Add a new public method void reverse() to the class. **The method must reverse the linked list data structure. **You can implement either iterative or recursive solution. **Test your method in ListDemo.java. **Make sure it works for empty list as well as with a list with just one element. Requirement: Complexity of your solution must be O(N).

2. reverseToString() and recReverseToString() Continue working with the same List.java class. **Add two more methods to the class: **public String reverseToString() method creates a string that holds all the integers in the list in reverse order. Requirements: - DO NOT reverse list, just traverse it and create a string that holds the elements in reverse order. - Your solution must be O(N). -This solution must be iterative. **public String recReverseToString() is a RECURSIVE method with the same functionality - creates a string that holds all the integers in the list in reverse order. Requirements: -DO NOT reverse list, just traverse it and create a string that holds the elements in reverse order. -Your solution must be O(N). -This solution must be recursive.

3. Copy Constructor Method Continue working with the same List.java class. **Add a copy constructor to create a deep copy of the list.

4. smallestFirst() Method Continue working with the same List.java class. **Add void smallestFirst() method that moves the node with the smallest integer in the list to become the first node.

***************************** package listdemo; public class ListDemo { /** * @param args the command line arguments */ public static void main(String [] args) { List myList = new List(); myList.add(1); myList.add(2); myList.add(0, 3); myList.add(2, 4); myList.add(4, 5); System.out.println("The members of the list are:"); System.out.print(myList); myList.reverseList(); System.out.println("After reversal:"); System.out.print(myList); } } ***************************** package listdemo; public class List { private class Node { int value; Node next; /** Constructor. @param val The element to store in the node. @param n The reference to the successor node. */ Node(int val, Node n) { value = val; next = n; } /** Constructor. @param val The element to store in the node. */ Node(int val) { // Call the other (sister) constructor. this(val, null); } } private Node first; // list head /** Constructor. */ public List() { first = null; } /** The isEmpty method checks to see if the list is empty. @return true if list is empty, false otherwise. */ public boolean isEmpty() { return first == null; } /** The size method returns the length of the list. @return The number of elements in the list. */ public int size() { int count = 0; Node p = first; while (p != null) { // There is an element at p count ++; p = p.next; } return count; } /** The add method adds an element to the end of the list. @param e The value to add to the end of the list. */ public void add(int e) { if (isEmpty()) { first = new Node(e); } else { // Add to end of existing list Node current = first; // moving current reference to the ent of the list while(current.next!=null) current = current.next; current.next = new Node(e); } } /** The add method adds an element at a position. @param e The element to add to the list. @param index The position at which to add the element. @exception IndexOutOfBoundsException When index is out of bounds. */ public void add(int index, int e) { if (index < 0 || index > size()) { String message = String.valueOf(index); throw new IndexOutOfBoundsException(message); } // Index is at least 0 if (index == 0) { // New element goes at beginning first = new Node(e, first); return; } // Set a reference pred to point to the node that // will be the predecessor of the new node Node pred = first; for (int k = 1; k <= index - 1; k++) { pred = pred.next; } // Splice in a node containing the new element pred.next = new Node(e, pred.next); } /** The toString method computes the string representation of the list. @return The string form of the list. */ public String toString() { StringBuilder strBuilder = new StringBuilder(); // Use p to walk down the linked list Node p = first; while (p != null) { strBuilder.append(p.value + " "); p = p.next; } return strBuilder.toString(); } /** The remove method removes the element at an index. @param index The index of the element to remove. @return The element removed. @exception IndexOutOfBoundsException When index is out of bounds. */ public int remove(int index) { if (index < 0 || index >= size()) { String message = String.valueOf(index); throw new IndexOutOfBoundsException(message); } int element; // The element to return if (index == 0) { // Removal of first item in the list element = first.value; first = first.next; } else { // To remove an element other than the first, // find the predecessor of the element to // be removed. Node pred = first; // Move pred forward index - 1 times for (int k = 1; k <= index -1; k++) pred = pred.next; // Store the value to return element = pred.next.value; // Route link around the node to be removed pred.next = pred.next.next; } return element; } }