Implement the ADT sorted list by using a linked binary search tree public interf
ID: 3582136 • Letter: I
Question
Implement the ADT sorted list by using a linked binary search tree
public interface SortedListInterface<T extends Comparable<? super T>> {
/**
* Adds a new entry to this list in its proper order, if it does not match
* an existing object in the list.
*
* @param newEntry
* An object to be added to the list.
* @return True if the object was added to the list, otherwise return false.
*/
public boolean add(T newEntry);
/**
* Removes the only occurrence of a specified entry from this
* sorted list.
*
* @param anEntry
* The object to be removed.
* @return True if anEntry was located and removed; otherwise returns false.
*/
public boolean remove(T anEntry);
/**
* 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);
/** Removes all entries from this list. */
public void clear();
/**
* 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();
/**
* 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.
*/
// Note: Can change return type to Object[] if T[] causes problems
public Object[] toArray();
/**
*
* @return the sorted list of values with a space between each value
*/
public String toString();
} // end SortedListInterface
Explanation / Answer
public class OrderedList implements SortedListInterface{
private static final boolean True = false;
int currentSize; // current #of elements in the lsit
int maxSize; // maximum number of elements the list can hold
int[] elements; // storage for elements
public OrderedList(Comparable maxElements) {
currentSize =0;
maxSize = (int) maxElements;
elements = new int[maxSize];
}
public boolean add(Comparable newEntry){
int insertLocation;
// test if the list is full
if (this.isFull())
//return false;
System.out.println("Insert failed, list full");
else { //not full
// Added first element to an empty list
if (currentSize ==0) this.elements[0] = (int) newEntry;
// add new element at end new value > existing values
else if(newEntry >= this.elements[currentSize-1])
this.elements[currentSize] = (int) newEntry;
else{
insertLocation=0;
while(this.elements[insertLocation] < newEntry) insertLocation++;
for(int i=currentSize-1; i >= insertLocation; i--)
this.elements[i+1] = this.elements[i];
this.elements[insertLocation] = newEntry;
this.currentSize++;
}}
}
private boolean isFull() {
// TODO Auto-generated method stub
return false;
}
public boolean remove(Comparable anEntry) {
// This method deletes the first element containing
// the specified value
int location;
if (this.isEmpty()) {
System.out.println("List is empty, delete aborted");
return false;
}
else {// list not empty
location = this.find(anEntry);
if (location == -999) {
System.out.println("Value not in list, delete aborted");
return false;
}
else {
this.delete(location);
}
}// end list not empty
return true;
}// end deleteValue
private int find(Comparable anEntry) {
// TODO Auto-generated method stub
return 0;
}
private void delete(int location) {
// TODO Auto-generated method stub
}
public boolean contains(int anEntry)
{
int location= -999;
//Begin searching at the first element, to the last
for (int i=0; i <= this.currentSize-1; i++) {
if (this.elements[i] == anEntry) {
location = i+1;
break; // if found exit loop
}
} // end for
return True;
}// end find
public void clear()
{
int size;
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
}public boolean isEmpty(){
return (currentSize == 0);
}
}