/** * A class that implements the ADT list by using a chain of linked nodes that
ID: 3905904 • Letter: #
Question
/**
* A class that implements the ADT list by using a chain of linked nodes that
* has a head reference.
*
* @author
*/
public class LListWithTail<T extends Comparable<? super T>> implements ListInterface<T>
{
private Node firstNode; // Head reference to first node
private Node lastNode; // Tail reference to last node
private int numberOfEntries; // Number of entries in list
public LListWithTail()
{
initializeDataFields();
} // end default constructor
public void clear()
{
initializeDataFields();
} // end clear
// Initializes the class's data fields to indicate an empty list.
private void initializeDataFields()
{
firstNode = null;
lastNode = null;
numberOfEntries = 0;
} // end initializeDataFields
public T[] toArray()
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[]) new Comparable<?>[numberOfEntries];
int index = 0;
Node currentNode = firstNode;
while ((index < numberOfEntries) && (currentNode != null))
{
result[index] = currentNode.getData();
currentNode = currentNode.getNextNode();
index++;
} // end while
return result;
} // end toArray
private class Node
{
private T data; // Entry in list
private Node next; // Link to next node
private Node(T dataPortion)
{
data = dataPortion;
next = null;
} // end constructor
private Node(T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
} // end constructor
private T getData()
{
return data;
} // end getData
private void setData(T newData)
{
data = newData;
} // end setData
private Node getNextNode()
{
return next;
} // end getNextNode
private void setNextNode(Node nextNode)
{
next = nextNode;
} // end setNextNode
} // end Node
} // end LList
Here is the list interface
/**
* An interface for the ADT list. Entries in a list have positions that begin
* with 1.
*
* @author
*
*/
public interface ListInterface<T extends Comparable<? super T>>
{
/**
* Adds a new entry to the correct position in this list, so that
* entries in this list are in nondecreasing order.
*
* The list's size is increased by 1.
*
* @param newEntry
* The object to be added as a new entry.
*/
public void add(T newEntry);
/**
* Removes the entry at a given position from this list. Entries originally at
* positions higher than the given position are at the next lower position
* within the list, and the list's size is decreased by 1.
*
* @param givenPosition
* An integer that indicates the position of the entry to be removed.
* @return A reference to the removed entry.
* @throws IndexOutOfBoundsException
* if either givenPosition < 1 or givenPosition > getLength().
*/
public T remove(int givenPosition);
/** Removes all entries from this list. */
public void clear();
/**
* Retrieves the entry at a given position in this list.
*
* @param givenPosition
* An integer that indicates the position of the desired entry.
* @return A reference to the indicated entry.
* @throws IndexOutOfBoundsException
* if either givenPosition < 1 or givenPosition > getLength().
*/
public T getEntry(int givenPosition);
/**
* Retrieves all entries that are in this list in the order in which they occur
* in the list.
*
* @return A newly allocated array of all the entries in the list. Note: If the
* list is empty, the returned array is empty.
*/
public T[] toArray();
/**
* Sees whether this list contains a given entry.
*
* @param anEntry
* The object that is the desired entry.
* @return True if the list contains anEntry, or false if not.
*/
public boolean contains(T anEntry);
/**
* Gets the length of this list.
*
* @return The integer number of entries currently in the list.
*/
public int getLength();
/**
* Sees whether this list is empty.
*
* @return True if the list is empty, or false if not.
*/
public boolean isEmpty();
/**
* Returns the smallest object in this list.
*/
public T getMin();
/**
* Returns the largest object in this list.
*/
public T getMax();
/**
* Removes and returns the smallest object in this list.
*
*/
public T removeMin();
/**
* Removes and returns the largest object in this list.
*
*/
public T removeMax();
/**
* Returns a new list that are less than some given item.
*
*/
public ListInterface<T> getAllLessThan(T anObject);
} // end ListInterface
Explanation / Answer
here is your program : ----------->>>>>>>>
public class LListWithTail<T extends Comparable<? super T>> implements ListInterface<T>
{
private Node firstNode; // Head reference to first node
private Node lastNode; // Tail reference to last node
private int numberOfEntries; // Number of entries in list
public LListWithTail()
{
initializeDataFields();
} // end default constructor
public void clear()
{
initializeDataFields();
} // end clear
// Initializes the class's data fields to indicate an empty list.
private void initializeDataFields()
{
firstNode = null;
lastNode = null;
numberOfEntries = 0;
} // end initializeDataFields
public T[] toArray()
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] result = (T[]) new Comparable<?>[numberOfEntries];
int index = 0;
Node currentNode = firstNode;
while ((index < numberOfEntries) && (currentNode != null))
{
result[index] = currentNode.getData();
currentNode = currentNode.getNextNode();
index++;
} // end while
return result;
} // end toArray
private class Node
{
private T data; // Entry in list
private Node next; // Link to next node
private Node(T dataPortion)
{
data = dataPortion;
next = null;
} // end constructor
private Node(T dataPortion, Node nextNode)
{
data = dataPortion;
next = nextNode;
} // end constructor
private T getData()
{
return data;
} // end getData
private void setData(T newData)
{
data = newData;
} // end setData
private Node getNextNode()
{
return next;
} // end getNextNode
private void setNextNode(Node nextNode)
{
next = nextNode;
} // end setNextNode
} // end Node
public void add(T newEntry){
if(isEmpty()){
Node newNode = new Node(newEntry);
firstNode = newNode;
lastNode = newNode;
numberOfEntries = 1;
return;
}
Node current = firstNode;
Node prev = null;
while(current != null){
if(current.getData().compareTo(newEntry) > 0){
if(prev == null){
Node newNode = new Node(newEntry,firstNode);
numberOfEntries++;
return;
}
prev.setNextNode(new Node(newEntry,current));
numberOfEntries++;
return;
}
prev = current;
current = current.getNextNode();
}
Node newNode = new Node(newEntry);
prev.setNextNode(newNode);
lastNode = newNode;
numberOfEntries++;
}
public T remove(int givenPosition)throws IndexOutOfBoundsException{
if(givenPosition > numberOfEntries || givenPosition < 1){
throw new IndexOutOfBoundsException();
}
Node current = firstNode;
Node prev = null;
for(int i=1;i<=givenPosition;i++){
prev = current;
current = current.getNextNode();
}
if(prev == null){
firstNode = firstNode.getNextNode();
numberOfEntries--;
}else{
prev.setNextNode(current.getNextNode());
numberOfEntries--;
}
return current.getData();
}
public T getEntry(int givenPosition)throws IndexOutOfBoundsException{
if(givenPosition > numberOfEntries || givenPosition < 1){
throw new IndexOutOfBoundsException();
}
Node current = firstNode;
for(int i=1;i<=givenPosition;i++){
current = current.getNextNode();
}
return current.getData();
}
public boolean contains(T anEntry){
if(isEmpty()){
return false;
}
Node current = firstNode;
while(current != null){
if(anEntry.compareTo(current.getData()) == 0){
return true;
}
}
return false;
}
public int getLength(){
return numberOfEntries;
}
public boolean isEmpty(){
if(firstNode == null && numberOfEntries == 0){
return true;
}
return false;
}
public T getMin(){
if(!isEmpty())
return firstNode.getData();
return (T)null;
}
public T getMax(){
if(!isEmpty()){
return lastNode.getData();
}
return (T)null;
}
public T removeMin(){
if(!isEmpty()){
T data = firstNode.getData();
firstNode = firstNode.getNextNode();
if(firstNode == null){
lastNode == null;
}
numberOfEntries--;
return data;
}
return (T)null;
}
public T removeMax(){
if(!isEmpty()){
T data = lastNode.getData();
if(firstNode == lastNode){
initializeDataFields();
return data;
}
Node current = firstNode;
Node prev = null;
while(current != lastNode){
prev = current;
current = current.getNextNode();
}
if(prev != null){
prev.setNextNode(null);
lastNode = prev;
numberOfEntries--;
}
return data;
}
return (T)null;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.