Create a class called ManyLists. It encapsulates an instance variable that is a long array. The length of the array should be dependent on an argument passed into a constructor. Include get and set methods so you can assign values to the elements of the array. The ManyLists class should also have the following methods.

getDoubleEndedList() -- which returns a double-ended linked list based on the data in the instance variable array. That kind of linked list is described below ;

// firstLastList.java // demonstrates list with first and last references // to run this program: C>java FirstLastApp //////////////////////////////////////////////////////////////// class Link { public long dData; // data item public Link next; // next link in list // ------------------------------------------------------------- public Link(long d) // constructor { dData = d; } // ------------------------------------------------------------- public void displayLink() // display this link { System.out.print(dData + ); }

// ------------------------------------------------------------- } // end class Link //////////////////////////////////////////////////////////////// class FirstLastList { private Link first; // ref to first link private Link last; // ref to last link // ------------------------------------------------------------- public FirstLastList() // constructor { first = null; // no links on list yet last = null; } // ------------------------------------------------------------- public boolean isEmpty() // true if no links { return first==null; } // ------------------------------------------------------------- public void insertFirst(long dd) // insert at front of list { Link newLink = new Link(dd); // make new link if( isEmpty() ) // if empty list, last = newLink; // newLink <-- last newLink.next = first; // newLink --> old first first = newLink; // first --> newLink } // ------------------------------------------------------------- public void insertLast(long dd) // insert at end of list { Link newLink = new Link(dd); // make new link if( isEmpty() ) // if empty list, first = newLink; // first --> newLink else last.next = newLink; // old last --> newLink last = newLink; // newLink <-- last } // ------------------------------------------------------------- public long deleteFirst() // delete first link { // (assumes non-empty list) long temp = first.dData; if(first.next == null) // if only one item

last = null; // null <-- last first = first.next; // first --> old next return temp; } // ------------------------------------------------------------- public void displayList() { System.out.print(List (first-->last): ); Link current = first; // start at beginning while(current != null) // until end of list, { current.displayLink(); // print data current = current.next; // move to next link } System.out.println(); } // ------------------------------------------------------------- } // end class FirstLastList //////////////////////////////////////////////////////////////// class FirstLastApp { public static void main(String[] args) { // make a new list FirstLastList theList = new FirstLastList(); theList.insertFirst(22); // insert at front theList.insertFirst(44); theList.insertFirst(66); theList.insertLast(11); // insert at rear theList.insertLast(33); theList.insertLast(55); theList.displayList(); // display the list theList.deleteFirst(); // delete first two items theList.deleteFirst(); theList.displayList(); // display again } // end main() } // end class FirstLastApp

getDoublyLinkedList() -- which returns a doubly linked list based on the data in the instance variable array. That kind of linked list is described below

// listInsertionSort.java // demonstrates sorted list used for sorting // to run this program: C>java ListInsertionSortApp //////////////////////////////////////////////////////////////// class Link { public long dData; // data item public Link next; // next link in list // ------------------------------------------------------------- public Link(long dd) // constructor { dData = dd; } // -------------------------------------------------------------

} // end class Link //////////////////////////////////////////////////////////////// class SortedList { private Link first; // ref to first item on list // ------------------------------------------------------------- public SortedList() // constructor (no args) { first = null; } // initialize list // ------------------------------------------------------------- public SortedList(Link[] linkArr) // constructor (array { // as argument) first = null; // initialize list for(int j=0; j current.dData) { // or key > current, previous = current; current = current.next; // go to next item } if(previous==null) // at beginning of list first = k; // first --> k else // not at beginning previous.next = k; // old prev --> k k.next = current; // k --> old current } // end insert() // ------------------------------------------------------------- public Link remove() // return & delete first link { // (assumes non-empty list) Link temp = first; // save first first = first.next; // delete first return temp; // return value } // ------------------------------------------------------------- } // end class SortedList

//////////////////////////////////////////////////////////////// class ListInsertionSortApp { public static void main(String[] args) { int size = 10; // create array of links Link[] linkArray = new Link[size]; for(int j=0; j

To create the above linked lists you will have to create something equivalent to the Link class and embed the aray's long data within objects of that class.

The project should contain any other classes you need to complete the test. Include a ManyListsDriver class that tests the ManyLists class, its methods, and the data structures returned by the methods listed above. The peculiar features of the two forms of linked list should be clearly demonstrated.