Write an addSorted method for the generic linked list from Display 15.8 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 extends Comparable<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;
}
//***********ADDSORTED METHOD**********************/
public void addSorted(T itemData){
if(head == null){//If there is no head
head = new Node<T>(itemData, null);//Then Create a head
}else{
if (head.data.compareTo(itemData) >=0){//If the parameter number is smaller than the head data
head = new Node<T>(itemData, head);//Then just create a Node with that data and make it the new head
}else{
Node<T> current = head;//Sets the current pointer to the head node
Node<T> previous = null;
while (current.link !=null && current.data.compareTo(itemData) <= 0){//As long as the pointer does not fall off the end of the list AND the next pointer data is larger than the new data
previous = current;//get a copy of the current pointer to be used later
current = current.link;//keeps pointer moving down the list
}
if(current.data.compareTo(itemData) >= 0){
previous.link = new Node<T>(itemData,current);//Inserts a Node before the next largest number compared to itemData
}else{
current.link = new Node<T>(itemData, null);//Adds a Node at the very end if it is the largest
}
}
}
}
/**
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.print(position.data + " ");
position = position.link;
}
System.out.println("");
}
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
{
@SuppressWarnings("unchecked")
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
}
}
}
import java.util.Random;
public class Main_SortedList{
public static void main(String args[]) {
LinkedList3 unsortedList = new LinkedList3<Integer>();
LinkedList3 sortedList = new LinkedList3<Integer>();
LinkedList3 sortedFruit = new LinkedList3<String>();
LinkedList3 unsortedFruit = new LinkedList3<String>();
Random rand = new Random();
int number;
int [] numbers = new int [15];
String[] fruits = {"bannana", "apple", "pinapple", "grape", "avocado", "stawberry", "watermellon", "peach", "pear", "papaya", "apricot"};
//create 15 random numbers and add them to a linked list
for(int x = 0; x < 15; x++){
number = rand.nextInt(100);
numbers[x] = number;
unsortedList.addToStart(number);
}
System.out.println("Add to list unsorted: " );
unsortedList.outputList();
for(int data : numbers){
sortedList.addSorted(data);
}
System.out.println("Add to sorted List: ");
sortedList.outputList();
for(String fruit : fruits){
unsortedFruit.addToStart(fruit);
}
System.out.println("Add to unsorted List: ");
unsortedFruit.outputList();
for(String fruit : fruits){
sortedFruit.addSorted(fruit);
}
System.out.println("Add to sorted List: ");
sortedFruit.outputList();
}
}