Write a Java class named BinaryTreeSortedList to implement the SortedList interf
ID: 3577275 • Letter: W
Question
Write a Java class named BinaryTreeSortedList to implement the SortedList interface, 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 T[] toArray();
/**
*
* @return the sorted list of values with a space between each value
*/
public String toString();
} // end SortedListInterface
Explanation / Answer
/**
*
* @author paramesh
*/
class Node
{
protected int data;
protected Node link;
/* Constructor */
public Node()
{
link = null;
data = 0;
}
/* Constructor */
public Node(int d,Node n)
{
data = d;
link = n;
}
/* Function to set link to next Node */
public void setLink(Node n)
{
link = n;
}
/* Function to set data to current Node */
public void setData(int d)
{
data = d;
}
/* Function to get link to next node */
public Node getLink()
{
return link;
}
/* Function to get data from current Node */
public int getData()
{
return data;
}
}
public class linkedList<T> implements SortedListInterface{
protected Node start;
public int size;
public linkedList()
{
start=null;
size = 0;
}
@Override
public boolean add(Comparable newEntry) {
Node nodePtr, ptr, tmp = null;
nodePtr = new Node((int) newEntry, null);
boolean ins = false;
if (start == null)
start = nodePtr;
else if (((int) newEntry <= start.getData()))
{
nodePtr.setLink(start);
start = nodePtr;
}
else
{
tmp = start;
ptr = start.getLink();
while(ptr != null)
{
if ((int) newEntry >= tmp.getData() && (int) newEntry <= ptr.getData())
{
tmp.setLink(nodePtr);
nodePtr.setLink(ptr);
ins = true;
break;
}
else
{
tmp = ptr;
ptr = ptr.getLink();
}
}
if (ins == false)
{
tmp.setLink(nodePtr);
}
}
size++;
return ins;
}
@Override
public boolean remove(Comparable anEntry) {
int position = 0;
Comparable[] data = toArray();
for(int i=0;i<data.length;i++){
if(data[i] == anEntry){
position = i;
break;
}
}
if (position == 1)
{
start = start.getLink();
size--;
return true;
}
if (position == size)
{
Node nodePtr = start;
for (int i = 1; i < size - 1; i++)
nodePtr = nodePtr.getLink();
nodePtr.setLink(null);
size --;
return true;
}
Node ptr = start;
position = position - 1 ;
for (int i = 1; i < size - 1; i++)
{
if (i == position)
{
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size-- ;
return true;
}
@Override
public boolean contains(Comparable anEntry) {
Comparable[] data = toArray();
for(int i=0;i<data.length;i++){
if(data[i] == anEntry){
return true;
}
}
return false;
}
@Override
public void clear() {
start = null;
size = 0;
}
@Override
public int getLength() {
return size;
}
@Override
public boolean isEmpty() {
return start == null;
}
@Override
public Comparable[] toArray() {
Comparable[] data = new Comparable[size];
int index = 0;
System.out.print("Sorted Singly Linked List = ");
if (size == 0)
{
return data;
}
if (start.getLink() == null)
{
return data;
}
Node nodePtr = start;
data[index] = start.getData();
index++;
nodePtr = start.getLink();
while (nodePtr.getLink() != null) {
data[index] = nodePtr.getData();
nodePtr = nodePtr.getLink();
index++;
}
data[index] = start.getData();
return data;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.