Create a class called ManyLists. It encapsulates an instance variable that is a

Question

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<linkArr.length; j++) // copy array
insert( linkArr[j] ); // to list
}
// -------------------------------------------------------------
public void insert(Link k) // insert (in order)
{
Link previous = null; // start at first
Link current = first;
// until end of list,
while(current != null && k.dData > 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<size; j++) // fill array with links
{ // random number
int n = (int)(java.lang.Math.random()*99);
Link newLink = new Link(n); // make link
linkArray[j] = newLink; // put in array
}
// display array contents
System.out.print(“Unsorted array: “);
for(int j=0; j<size; j++)
System.out.print( linkArray[j].dData + “ “ );
System.out.println(“”);
// create new list
// initialized with array
SortedList theSortedList = new SortedList(linkArray);
for(int j=0; j<size; j++) // links from list to array
linkArray[j] = theSortedList.remove();
// display array contents
System.out.print(“Sorted Array: “);
for(int j=0; j<size; j++)
System.out.print(linkArray[j].dData + “ “);
System.out.println(“”);
} // end main()
} // end class ListInsertionSortApp

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.

Explanation / Answer

package com.manylist;

public class ManyList {
   public long array; // data item
   public long getArray() {
       return array;
   }
   public void setArray(long array) {
       this.array = array;
   }
   public ManyList next; // next link in list
   // -------------------------------------------------------------
   public ManyList(int dd) // constructor
   { array = dd; }
  
   public long getDoubleEndedList(){
          
           long array=this.getArray();
           return array;
       }
}

package com.manylist;

public class SortedList {

   private ManyList first; // ref to first item on list
   // -------------------------------------------------------------
   public SortedList() // constructor (no args)
   { first = null; } // initialize list
   // -------------------------------------------------------------
   public SortedList(ManyList[] linkArr) // constructor (array
   { // as argument)
   first = null; // initialize list
   for(int j=0; j<linkArr.length; j++) // copy array
   insert( linkArr[j] ); // to list
   }
   // -------------------------------------------------------------
   public void insert(ManyList k) // insert (in order)
   {
   ManyList previous = null; // start at first
   ManyList current = first;
   // until end of list,
   while(current != null && k.array > current.array)
   { // 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 ManyList remove() // return & delete first link
   { // (assumes non-empty list)
   ManyList temp = first; // save first
   first = first.next; // delete first
   return temp; // return value
   }
}

public class ManyListDriver {
   public static void main(String[] args)
   {
   int size = 10;
   // create array of links
   ManyList[] linkArray = new ManyList[size];
   for(int j=0; j<size; j++) // fill array with links
   { // random number
   long n = (long)(java.lang.Math.random()*99);
   ManyList newLink = new ManyList(size); // make link
   newLink.setArray(n);
   long aa=newLink.getArray();
   System.out.print(aa);
   linkArray[j] = newLink; // put in array
   }
   // display array contents
   System.out.print("Unsorted array: ");
   for(int j=0; j<size; j++)
   System.out.print( linkArray[j].array + "" );
   System.out.println("");
   // create new list
   // initialized with array
   SortedList theSortedList = new SortedList(linkArray);
   for(int j=0; j<size; j++) // links from list to array
   linkArray[j] = theSortedList.remove();
   // display array contents
   System.out.print("Sorted Array: ");
   for(int j=0; j<size; j++)
   System.out.print(linkArray[j].array + " ");
   System.out.println("");
   }
}

Output:51
45
92
45
82
78
11
0
30
36
Unsorted array: 5145924582781103036
Sorted Array: 0 11 30 36 45 45 51 78 82 92

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.