ANSWER IN JAVA Write an addSorted method for the generic linked list code below
ID: 3767749 • Letter: A
Question
ANSWER IN JAVA
Write an addSorted method for the generic linked list code below such that the method adds a new node in the correct location so that the list remains in sorted order. Note that this will require that the type parameter T extend the Comparable interface. Write a suitable test program.
public class LinkedList3<T>
{
private class Node<T>
{
private T data;
private Node<T> link;
public Node( )
{
data = null;
link = null;
}
public Node(T newData, Node<T> linkValue)
{
data = newData;
link = linkValue;
}
}//End of Node<T> inner class
private Node<T> head;
public LinkedList3( )
{
head = null;
}
/**
Adds a node at the start of the list with the specified data.
The added node will be the first node in the list.
*/
public void addToStart(T itemData)
{
head = new Node<T>(itemData, head);
}
/**
Removes the head node and returns true if the list contains at least
one node. Returns false if the list is empty.
*/
public boolean deleteHeadNode( )
{
if (head != null)
{
head = head.link;
return true;
}
else
return false;
}
/**
Returns the number of nodes in the list.
*/
public int size( )
{
int count = 0;
Node<T> position = head;
while (position != null)
{
count++;
position = position.link;
}
return count;
}
public boolean contains(T item)
{
return (find(item) != null);
}
/**
Finds the first node containing the target item, and returns a
reference to that node. If target is not in the list, null is returned.
*/
private Node<T> find(T target)
{
Node<T> position = head;
T itemAtPosition;
while (position != null)
{
itemAtPosition = position.data;
if (itemAtPosition.equals(target))
return position;
position = position.link;
}
return null; //target was not found
}
/**
Finds the first node containing the target and returns a reference
to the data in that node. If target is not in the list, null is returned.
*/
public T findData(T target)
{
return find(target).data;
}
public void outputList( )
{
Node<T> position = head;
while (position != null)
{
System.out.println(position.data);
position = position.link;
}
}
public boolean isEmpty( )
{
return (head == null);
}
public void clear( )
{
head = null;
}
/*
For two lists to be equal they must contain the same data items in
the same order. The equals method of T is used to compare data items.
*/
public boolean equals(Object otherObject)
{
if (otherObject == null)
return false;
else if (getClass( ) != otherObject.getClass( ))
return false;
else
{
LinkedList3<T> otherList = (LinkedList3<T>)otherObject;
if (size( ) != otherList.size( ))
return false;
Node<T> position = head;
Node<T> otherPosition = otherList.head;
while (position != null)
{
if (!(position.data.equals(otherPosition.data)))
return false;
position = position.link;
otherPosition = otherPosition.link;
}
return true; //no mismatch was not found
}
}
}
Explanation / Answer
public class addSort<T implements Comparable<T>> extends LinkedList3<T>
public void addSort(T d){
if(empty()){
head(d);
} else {
LinkedList<T>.MyListIter it = begin();
int i = 0;
//This won't work obviously
for(; i < size() || it.current().compareTo(it.next()) == -1; ++i, it.next()){
//find node to place the new node before it
it.prev()
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.