Your implementation can use either an expandable array or linked nodes- it is yo
ID: 3583257 • Letter: Y
Question
Your implementation can use either an expandable array or linked nodes- it is your choice. You can decide what instance variables are needed. You must implement every method from the interface. Make sure to account for special conditions such as empty lists and singleton lists. Note: your instance data variable should be either a) an array or b) one or more nodes. It should not be an AList or LList object or an ArrayList object.
You can use your Lab B solution file as the interface if you received 100% on Lab B. If you lost points, please first fix any errors before you use your interface file. You can post questions to the forum about how to fix an error. If you did not yet receive a grade on Lab B, you can use the interface file provided on Insight.
Your implementation must:
compile (10 points)
contain these implemented methods: (72 points)
insertHead
insertTail
deleteHead
deleteTail
display
contains
isEmpty
isFull
Also create a driver program to test your implementation (18 points). The driver program will operate from the client perspective. Your driver program should:
display an empty list
add five entries to the list- some at the head and some at the tail
display the list
remove the first entry
remove the last entry
display the list
test to see if elements are in the list (test one element that is in the list and one that is not)
remove the last three elements in the list
try to remove an element from the empty list
Extra Credit (20 points)
Write a second class to implement EntryWayListInterface. Instead of using an array or linked nodes, use either an AList or LList object as your instance data variable. In this way, you are using an existing data type (AList or LList) to implement a new data type (EntryWayListInterface). Inside the methods of this class, invoke methods on the AList or LList object to accomplish the task.
Note: if you run your test program using this class to initialize your EntryWayListInterface object, the program should run exactly the same as it did above.
Submitting
Review the Assignment Submission and Grading Guidelines before submitting your lab. Zip together all .java files (the interface, the implementation, the driver program, and the extra credit) for submission.
If submitting as a group, submit one assignment only through one group member's Insight account. Put the names of all group members in Java comments at the top of each Java file.
Explanation / Answer
package Sam;
public class Listinterface<T extends Comparable<T>> implements EntryWayListInterface<T>
{
//Iterator//
private Node firstNode;
//length of the String //
private int length;
//constructor//
public Listinterface()
{
clear();
}
//deleting the nodes//
public final void clear()
{
//object checking//
firstNode = null;
//check empty//
length = 0;
}
//List to sort//
public boolean add(T newEntry)
{
Node newNode = new Node(newEntry);
Node currentNode = firstNode;
newNode.next = firstNode;
firstNode = newNode;
length++;
//Implemented recursive method//
insertionSort(null,firstNode);
return true;
}
//Soting array//
private void insertionSort(Node nodeOne, Node nodeTwo)
{
//Condition
if(nodeTwo.next != null )
{
Node beforeNode = nodeOne;
Node currentNode = nodeTwo ;
Node nextNode = nodeTwo.next;
if(currentNode.data.compareTo(nextNode.data)>0 )
{
currentNode.next = nextNode.next;
nextNode.next = currentNode;
if(beforeNode != null)
{
beforeNode.next = nextNode;
}
else
{
firstNode = nextNode;
firstNode.next = currentNode;
}
//Call function//
insertionSort(nextNode,currentNode);
}
}
//Sorting ends//}
public boolean insertHead(T newEntry)
{
return true;
}
public boolean insertTail(T newEntry)
{
return true;
}
//removing the elements//
public T deleteHead()
{
int mypos=1;
Node curnode=getNodeAt(mypos);
firstNode=curnode.next;
curnode.next=null;
length--;
return curnode.data;
}
// deleting tail elements//
public T deleteTail()
{
int tail=length;
Node tailNode=getNodeAt(tail);
Node tailNode2=getNodeAt(tail-1);
tailNode2.next=null;
length--;
return tailNode.data;
}
//Interface with classes and methods//
public void display()
{
for (int position = 1; position <= length; position++)
{
Node currentNode = getNodeAt(position);
System.out.println(currentNode.data);
}
}
public boolean contains(T anEntry)
{
boolean found = false;
Node currentNode = firstNode;
// loop started//
while (!found && (currentNode != null))
{
if (anEntry.equals(currentNode.data))
found = true;
else
currentNode = currentNode.next;
} // loop ends//
return found;
}
//nodes return//
public int getLength()
{
return length;
}
//specified in interface BasicList //
public boolean isEmpty()
{
boolean result;
//Condition to check length//
if (length == 0)
{
assert firstNode == null;
result = true;
}
else
{
assert firstNode != null;
result = false;
} // end if loop//
return result;
}
public boolean isFull()
{
return true;
}
//Node situates in the position//
private Node getNodeAt(int givenPosition)
{
assert !isEmpty() &&(1 <= givenPosition) && (givenPosition <= length);
Node currentNode = firstNode;
//Loop//
for (int counter = 1; counter < givenPosition; counter++)
currentNode = currentNode.next;
assert currentNode != null;
return currentNode;
}
//Static nested class//
private class Node
{
private T data;
private Node next;
private Node(T dataPortion)
{
data = dataPortion;
next = null;
}
//Queue interface//
private Node(T dataPortion, Node nextNode)
{
//Object creation//
data = dataPortion;
next = nextNode;
}
}
}
Main
package Sam;
public class Listinterface
{
//Main function//
public static void main(String[] args)
{
//Linked list//
EntryWayListInterface<String> myList = new LList<String>();
System.out.println(" **********START************* ");
System.out.println("List should be empty; isEmpty returns :" +
myList.isEmpty());
//Printing in a new line//
System.out.println(" Testing add with insertion sorting:");
System.out.println("Add 45: returns " + myList.add("45"));
System.out.println("Add 55: returns " + myList.add("55"));
System.out.println("Add 75: returns " + myList.add("75"));
System.out.println("Add 10: returns " + myList.add("10"));
System.out.println("Add 20: returns " + myList.add("20"));
System.out.println(" Display the list: ");
myList.display();
System.out.println("Current head deleted " + myList.deleteHead());
myList.display();
System.out.println("Current tail deleted " + myList.deleteTail());
myList.display();
System.out.println(" ******** End*********");
} // end main
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.