Create a class called ManyLists. It encapsulates an instance variable that is a
ID: 3798878 • Letter: C
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
import java.io.*;
import java.util.*;
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("");
}
// -------------------------------------------------------------
//Method to update data of ith Link object
public void update(int i,long data)
{
int counter=0;
Link current=first;
//Loops until counter==i
while(counter!=i)
{
current=current.next;
counter++;
}
//Link new_link=new Link(data);
current.dData=data;
}
} // end class FirstLastList
//ManyLists class
class ManyLists
{
long array[]; //Array to store data
FirstLastList list; //DoubleEndedList object
int len; //To number of elements in list and array
int count; //number of elements inserted in list
//Constructor
public ManyLists()
{
len=100;
count=0;
array=new long[len];
list=new FirstLastList();
}
//Parameterized constructor
public ManyLists(int d)
{
len=d;
count=0;
array=new long[len];
list=new FirstLastList();
}
//Set method to insert and update data in list and array
public void set(int i,long data)
{
//Condition for checking already inserted a data at that index in array or not.
if(i<count)
{
array[i]=data;
list.update(i,data);
}
else
{
array[i]=data;
list.insertLast(data);
count++;
}
}
//Return data at index i
public long get(int i)
{
return array[i];
}
//Return double ended list
public FirstLastList getDoubleEndedList()
{
return list;
}
}
//driver class
public class ManyListDriver
{
public static void main(String args[])
{
Scanner s=new Scanner(System.in);
int n;
System.out.println("Enter total number of elements to insert : ");
n=s.nextInt();
ManyLists m=new ManyLists(n);
System.out.println("Enter n elements to insert in array and DoubleEndedList");
for(int i=0;i<n;i++)
{
long data=s.nextLong();
m.set(i,data);
}
FirstLastList l=m.getDoubleEndedList();
l.displayList();
System.out.println("Enter the index of array to get element at that index");
System.out.println(m.get(s.nextInt()));
System.out.println("Enter the index to update data at that index and data");
int index=s.nextInt();
long data=s.nextLong();
m.set(index,data);
System.out.println("Updated list : ");
l.displayList();
}
}
Output :
G580:~/codes/schegg$ javac ManyListDriver.java
G580:~/codes/schegg$ java ManyListDriver
Picked up JAVA_TOOL_OPTIONS: -javaagent:/usr/share/java/jayatanaag.jar
Enter total number of elements to insert :
5
Enter n elements to insert in array and DoubleEndedList
432
423
23333
2332
323
List (first-->last): 432 423 23333 2332 323
Enter the index of array to get element at that index
2
23333
Enter the index to update data at that index and data
2
1
Updated list :
List (first-->last): 432 423 1 2332 323
G580:~/codes/schegg$
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.