Program 2 Take the LinkedList class that we developed in lecture, and is shown at the bottom of this handout, and add the following methods to the class: * clear() - makes the list empty * deleteFirst() - detetes the first element in the list and returns the deleted element. Returns -1 if the list was already empty. Three cases: list is already empty, list has only one element and will become empty, and the list has two or more elements. * deleteFirstHalf() - deletes the front half of the list (no return value -- this is a void method). If there are an odd number of elements then the middle element is gets deleted also. * indexOf(E) - returns the index of the first value E found in the list. Return -1 if E is not in the list. * copy() - returns a copy of the linked list (i.e., creates a new list with a new set of nodes and returns a reference to the newly created list). * toString() - returns a String describing the contents of the list (hint -- do something like the print method, but add to a growing String instead printing with System.out.println). Use the main method in the given Program2 class to test the methods that you wrote. Requirements 1. Assume that LinkedList is a list of positive integers that keeps its values in ascending order. Modify the code to maintain the integrity of the list (i.e., it will only hold positive integers and they are always kept in ascending order). 2. You must start with the code given on the course web site for LinkedList and add to that code. You can add whatever you need to that implementation, and modify it as necessary, but it must be a singly-linked non-circular list (without header and trailer nodes). 3. Use the exact driver given below (do not change anything inside of the main method). 4. Program2 should generate the output shown below when run with your LinkedList class. 5. Use good style, as described on the course web site. Suggestions 1. Just work on one new method at a time. Comment out the parts of the driver that call methods you have not developed yet. 2. When working on a method, draw a quick sketch of the how the method is affecting a typical linked list (and also identify the special cases). Program2 should generate this output when run with your LinkedList class: isEmpty should be true: true Print should show 10, 20, 30, 40, 50: 10, 20, 30, 40, 50 isEmpty should be false: false Testing toString for an empty string (should show nothing): isEmpty should be true after list has been cleared: true Loading list with values from 11 to 41 counting by 10 Print should show 11, 21, 31, 41: 11, 21, 31, 41 Deleting values 11 to 41, one-at-a-time with deleteFirst: 11 21 31 41 toString should show an empty list after all elements have been deleted: Loading list with values from 13 to 63 counting by 10 Before deleting the first half: 13, 23, 33, 43, 53, 63 After deleting the firset half: 43, 53, 63 Loading list with values from 14 to 54 counting by 10 Before deleting the first half (odd number of elements): 14, 24, 34, 44, 54 After deleting the firset half: 44, 54 Loading list with values from 10 to 10 counting by 10 Before deleting the first half (one element): 10 After deleting the firset half: Loading list with values from 10 to 50 counting by 10 Current list: 10, 20, 30, 40, 50 index of 10: 0 index of 30: 2 index of 50: 4 index of 99: -1 index of -22: -1 Loading list with values from 1 to 10 counting by 1 list1: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 list2: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 list1 after deletions and additions: 6, 7, 8, 9, 10, 20, 30 list2 (should not have changed): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 Use this driver (exactly as shown below): /** The Program2 main method is a driver for the LinkedList class. The LinkedList is a singly-linked non-circular list (without header and trailer nodes). The LinkedList class keeps its integer elements in ascending order. */ public class Program2 { public static void main(String [] args) { LinkedList order = new LinkedList(); System.out.println("isEmpty should be true: " + order.isEmpty()); order.add(40); // insert into empty order.add(10); // front order.add(20); // middle order.add(30); // middle order.add(50); // end System.out.print("Print should show 10, 20, 30, 40, 50: "); System.out.println(order); // toString supplies the string here System.out.println("isEmpty should be false: " + order.isEmpty()); order.clear(); System.out.println("Testing toString for an empty string (should show nothing): " + order); System.out.println("isEmpty should be true after list has been cleared: " + order.isEmpty()); load(order, 11, 41, 10); System.out.print("Print should show 11, 21, 31, 41: "); System.out.println(order); // toString supplies the string here System.out.println("Deleting values 11 to 41, one-at-a-time with deleteFirst: "); while (!order.isEmpty()) System.out.println(order.deleteFirst()); System.out.println("toString should show an empty list after all elements have been deleted: " + order); load(order, 13, 63, 10); System.out.println("Before deleting the first half: " + order); order.deleteFirstHalf(); System.out.println("After deleting the firset half: " + order); order.clear(); load(order, 14, 54, 10); System.out.println("Before deleting the first half (odd number of elements): " + order); order.deleteFirstHalf(); System.out.println("After deleting the firset half: " + order); order.clear(); load(order, 10, 10, 10); System.out.println("Before deleting the first half (one element): " + order); order.deleteFirstHalf(); System.out.println("After deleting the firset half: " + order); order.clear(); load(order, 10, 50, 10); // This is NOT a safe way of writing the code for this test -- can you think // of a better way to code it? System.out.println("Current list: " + order); System.out.println("index of 10: " + order.indexOf(10) ); System.out.println("index of 30: " + order.indexOf(30) ); System.out.println("index of 50: " + order.indexOf(50) ); System.out.println("index of 99: " + order.indexOf(99) ); System.out.println("index of -22: " + order.indexOf(-22) ); LinkedList list1 = new LinkedList(); LinkedList list2; load(list1, 1, 10, 1); list2 = list1.copy(); System.out.println("list1: " + list1); System.out.println("list2: " + list2); list1.deleteFirstHalf(); list1.add(20); list1.add(30); System.out.println("list1 after deletions and additions: " + list1); System.out.println("list2 (should not have changed): " + list2); } private static void load(LinkedList list, int from, int to, int increment) { System.out.printf("\nLoading list with values from %d to %d counting by %d\n", from, to, increment); for (int i = from; i <= to; i += increment) list.add(i); } } Start with this implementation of LinkedList: public class LinkedList { private Node start; private static class Node { int data; Node next; public Node(int data) { this.data = data; } public Node(int data, Node next) { this.data = data; this.next = next; } } /* preconditions: The value is not already in the list. postconditions: The value inserted in ascending order. */ public void add(int val) { // empty if (start == null || val < start.data) start = new Node(val, start); else // middle or end { Node p = start; while ( p.next != null && val > p.next.data ) p = p.next; p.next = new Node(val, p.next); } } public void print() { Node p = start; while (p != null) { System.out.println(p.data); p = p.next; } } // ************** Add your code here ****************** }