Question

Please implement the java method addInOrder() that allows you to create and maintain the lists in the order required. The addInOrder method must work with different external Comparator objects. (Hint: Consider creating and using a private compare method and a private Comparator reference as members of your SLL class. If your SLL is constructed without any parameter, then you should initialize the internal Comparator object reference to null. Otherwise, you should initialize it to the external Comparator object passed as a parameter to the constructor. The private compare method should then make the comparison based on the external Comparator if it exists, and based on the data item’s internal Comparable implementation otherwise.)

I have tried to implement this in my below code for the SLL java class and think that everything besides the addInOrder method meets the above requirements but the addInOrder needs to be corrected.

Here is the code for the Node java class I was using for the Singly Linked List:

public class Node<T extends Comparable<T>> {

   private T data;
   private Node next;

   /**
   * Constructor for objects of class Node
   */
   public Node(T d) {
       data = d;
       next = null;
   }

   public T getData() {
       return data;
   }

   public void setData(T o) {
       data = o;
   }

   public Node getNext() {
       return next;
   }

   public void setNext(Node n) {
       next = n;
   }

   @Override
   public String toString() {
       return "Node [data=" + data + ", next=" + next + "]";
   }  

  

}

Here is the current code for my SinglyLinked java class that needs the addInOrder method to be implemented:

import java.util.Comparator;

//Generic type that restrict type to objects that have implemented the comparable interface.
public class SLL<T extends Comparable<T>> {
   private Node <T> head;
   private Node <T> tail;

   private int size;

   private Comparator <T> comparator;

   public SLL() {
       head = null;
       size = 0;

       comparator = null;
   }

   //External comparator
   public SLL(Comparator <T> externalComp) {

       head = null;
       comparator = externalComp;
       size = 0;

   }

   //Method that gives size of the list
  
   public int size() {
       for(Node <T> n = head; n.getNext() != null; n = n.getNext())
       size++;   
       return size;
       }

   //this method will be used with the add in order method
   private int compare(T obj1, T obj2) {
       if(comparator == null) {
           return obj1.compareTo(obj2);
       }

       else {
           return comparator.compare(obj1, obj2);
       }
   }

   //addInOrder, add, delete, find, etc and once these methods are finished we can work with the A2 SLL and implement the rest of the assignment with   
   private void addHead(Node <T> n) {
       if (head == null) {
           head = n;
           tail = n;
       } else {
           n.setNext(head);
           head = n;
       }

   }

   private void addTail(Node<T> n) {
       if (tail == null) { // list is empty
           head = n;
           tail = n;
       } else {
           tail.setNext(n);
           tail = n;
       }
   }

   private Node<T> findItem(T key) {
       Node <T> currentNode = head;
       while (currentNode != null) {
           /**
           * Visit the node. In this case,
           * if the data in the currentNode is equal to the key,
           * return the reference to the node.
           */

           if (currentNode.getData().equals(key))
               return currentNode;
           // else, move to the next node
           else
               currentNode = currentNode.getNext();
       }
       // Return null if it didn't find the node.
       return null;
   }

   private Node<T> deleteItem(T key) {
       Node <T> currentNode = head;
       Node <T> previousNode = head;
       while (currentNode != null) {
           // Visit the node. In this case,
           // if the data in the currentNode is equal to the key,
           // remove the current node from the list by updating the reference
           // of the previous node to point to the node after the currentNode.
           if (currentNode.getData().equals(key)) {
               if (head == tail) {
                   head = null;
                   tail = null;
                   return currentNode;
               }

               if (currentNode == head)
                   head = currentNode.getNext();
               else {
                   previousNode.setNext(currentNode.getNext());
               }
               if (currentNode == tail) {
                   tail = previousNode;
               }

               return currentNode;
           }
           // else, move to the next node
           else {
               previousNode = currentNode;
               currentNode = currentNode.getNext();
           }
       }
       // Return null if it didn't find the node.
       return null;
   }
  

   private void addInOrder(Node <T> n) {
      
       if(head == null || compare(n,head) <= 0){
          
           addHead(n);

       }

       else if(compare(n, tail) > 0) {
           addTail(n);
       }

       else{
           Node mover = head;

           while(mover.getNext() != null && compare(n, mover.getNext()) > 0)
           {
               mover = mover.getNext();
           }

           n.setNext(mover.getNext());
           mover.setNext(n);
       }
      
   }

}

Answer 1

// Node.java
public class Node<T extends Comparable<T>> {

private T data;
private Node next;

/**
* Constructor for objects of class Node
*/
public Node(T d) {
data = d;
next = null;
}

public T getData() {
return data;
}

public void setData(T o) {
data = o;
}

public Node getNext() {
return next;
}

public void setNext(Node n) {
next = n;
}

@Override
public String toString() {
return "Node [data=" + data + ", next=" + next + "]";
}

  

}

// end of Node.java

// SLL.java

import java.util.Comparator;

//Generic type that restrict type to objects that have implemented the comparable interface.
public class SLL<T extends Comparable<T>> {
private Node <T> head;
private Node <T> tail;

private int size;

private Comparator <T> comparator;

public SLL() {
head = null;
size = 0;

comparator = null;
}

//External comparator
public SLL(Comparator <T> externalComp) {

head = null;
comparator = externalComp;
size = 0;

}

//Method that gives size of the list
  
public int size() {
for(Node <T> n = head; n.getNext() != null; n = n.getNext())
size++;   
return size;
}

//this method will be used with the add in order method
private int compare(T obj1, T obj2) {
if(comparator == null) {
return obj1.compareTo(obj2);
}

else {
return comparator.compare(obj1, obj2);
}
}

//addInOrder, add, delete, find, etc and once these methods are finished we can work with the A2 SLL and implement the rest of the assignment with   
private void addHead(Node <T> n) {
if (head == null) {
head = n;
tail = n;
} else {
n.setNext(head);
head = n;
}

}

private void addTail(Node<T> n) {
if (tail == null) { // list is empty
head = n;
tail = n;
} else {
tail.setNext(n);
tail = n;
}
}

private Node<T> findItem(T key) {
Node <T> currentNode = head;
while (currentNode != null) {
/**
* Visit the node. In this case,
* if the data in the currentNode is equal to the key,
* return the reference to the node.
*/

if (currentNode.getData().equals(key))
return currentNode;
// else, move to the next node
else
currentNode = currentNode.getNext();
}
// Return null if it didn't find the node.
return null;
}

private Node<T> deleteItem(T key) {
Node <T> currentNode = head;
Node <T> previousNode = head;
while (currentNode != null) {
// Visit the node. In this case,
// if the data in the currentNode is equal to the key,
// remove the current node from the list by updating the reference
// of the previous node to point to the node after the currentNode.
if (currentNode.getData().equals(key)) {
if (head == tail) {
head = null;
tail = null;
return currentNode;
}

if (currentNode == head)
head = currentNode.getNext();
else {
previousNode.setNext(currentNode.getNext());
}
if (currentNode == tail) {
tail = previousNode;
}

return currentNode;
}
// else, move to the next node
else {
previousNode = currentNode;
currentNode = currentNode.getNext();
}
}
// Return null if it didn't find the node.
return null;
}
  

private void addInOrder(Node <T> n) {
  
       // pass the value stored in the node, not the node objects to compare method
       if(head == null || compare(n.getData(),head.getData()) <= 0){
  
addHead(n);

       }

       // pass the value stored in the node, not the node objects to compare method
       else if(compare(n.getData(), tail.getData()) > 0) {
addTail(n);
       }

else{

       Node mover = head;

while(mover.getNext() != null && compare(n.getData(), mover.getNext().getData()) > 0)
{
mover = mover.getNext();
}

n.setNext(mover.getNext());
mover.setNext(n);
       }
  
}

}

//end of SLL.java