Instructions
Objective
Write a program to implement a sorted linked list and comparator using Java programming language.
Requirements and Specifications
Specification
For this assignment, you’ll make a new class, SortedLinkedList that consists of a linked list that adds items in sorted order according to a previously set indicator and order.
Comparator
If you were thinking after the last assignment that there has got to be a better way of sorting, you are right! In Java, there is an interface called the Comparator that focuses on allowing two objects of the same type to be compared easily. First you will create a comparator that will then be stored in your linked list later.
Create a new class CountryComparator that implements the Comparator interface for Country:
public class CountryComparator implements Comparator<Country> {
This class will consist of just two methods: 1) a constructor, and 2) the compare method that is required for a Comparator.
Constructor
Your comparator needs to store the indicator that it compares by and the direction that it should sort by (greatest to least or least to greatest). Create those instance variables and a constructor that takess in value for those variables and sets them.
compare method
Next create a method compare that takes two Country instances as parameters. The way that comparators in Java work is that for two objects a and b, it returns -1 if a comes before b, 0 if a and b could be in either order, and 1 if b comes before a. Your compare method should work the same based on the indicator and order chosen by the constructor. If two countries have the same value for the indicator, you should return 0.
You should test your CountryComparator by making a new one in the main(String[] args) method of CountryComparator.java with some test Country objects.
SortedLinkedList
Now that you have an object for comparing two countries, let’s make a sorted linked list. Note that you are not allowed to use any built-in List classes or methods! The point of this homework is to understand linked lists by implementing your own.
Create a class SortedLinkedList that implements the provided interface SortedList just for Country:
public class SortedLinkedList implements SortedList<Country> {
Adapt your Node code from the Linked List Activity so that you have a private Node class, a head, and a size instance variable. In addition, declare a comparator instance variable:
Comparator<Country> myComparator;
Copy the method signatures and comments from the SortedList interface and turn them into method stubs in SortedLinkedList by returning something of the correct type for each method.
Constructor
Create a constructor that takes a Comparator<Country> as a parameter and sets the instance variables appropriately.
test method
Create a test method that first creates three Country objects with dummy data, then puts them into Nodes and then connects those Nodes together from the head so that other methods can be tested before you implement add.
size and isEmpty methods
Start by implementing the size and isEmpty methods since they are short.
Using your test method, make sure that these work.
toString method
Adapt the toString method from the Linked List Activity for this class so that it returns the names of the countries in the list.
Using your test method, make sure that this works.
get method
Implement a get method that returns the Country at the given position. If the user tries to access a position outside of the range, you should throw an IndexOutOfBoundsException:
throw new IndexOutOfBoundsException();
Using your test method, make sure that this works.
add method
The add method is the heavy-lifter of this class since it needs to add a given item in the correct place in the list.
There are three scenarios that you need to think about when implementing your add method:
- adding to the middle of the list
- adding to the beginning of the list
- adding to the end of the list
I recommend you go in that order and make sure each scenario works before moving on to the next one. You are allowed to include extra instance variables such as tail if you find them useful. I also highly recommend that you have an example written down on paper and trace through it by hand so that you have a firm idea of what you need to do. You will probably run into a lot of NullPointerExceptions as you do this; try not to let them fluster you and just remember that that means you are accessing a null thing somewhere and go back to your example to figure out where.
Demonstrate in the main() method of SortedLinkedList that each of the three cases for add works.
Source Code
COUNTRY COMPARATOR
import java.util.Comparator;
public class CountryComparator implements Comparator<Country> {
public enum Order {
ASC,
DESC;
}
private final String indicate;
private final Order order;
public CountryComparator(String indicate, Order order) {
this.indicate = indicate;
this.order = order;
}
@Override
public int compare(Country o1, Country o2) {
double diff = o1.getValue(indicate) - o2.getValue(indicate);
if (diff > 0) {
return order == Order.ASC ? 1 : -1;
}
if (diff < 0) {
return order == Order.ASC ? -1 : 1;
}
return 0;
}
}
SORTED LINKED LIST
import java.util.Comparator;
public class SortedLinkedList implements SortedList<Country> {
private final Comparator<Country> comparator;
private int size;
private Node head;
public SortedLinkedList(Comparator<Country> comparator) {
this.comparator = comparator;
this.size = 0;
this.head = null;
}
/**
* Puts in several Nodes with test values to enable testing methods before add is implemented
*/
@Override
public void test() {
Country a = new Country("A,1,1,2,2,3,3,0");
Country b = new Country("B,2,3,1,3,1,2,0");
Country c = new Country("C,3,2,3,1,2,1,0");
Node aNode = new Node(a);
Node bNode = new Node(b);
Node cNode = new Node(c);
head = aNode;
aNode.next = bNode;
bNode.next = cNode;
cNode.next = null;
size = 3;
}
/**
* Adds item to the list in sorted order.
*/
@Override
public void add(Country item) {
Node newNode = new Node(item);
if (head == null) {
head = newNode;
return;
}
if (comparator.compare(item, head.country) < 0) {
newNode.next = head;
head = newNode;
return;
}
Node currentNode = head;
while (currentNode.next != null) {
if (comparator.compare(item, currentNode.next.country) < 0) {
newNode.next = currentNode.next;
currentNode.next = newNode;
return;
}
currentNode = currentNode.next;
}
currentNode.next = newNode;
newNode.next = null;
}
/**
* Returns the item at a given index.
*
* @return the item, or throw an IndexOutOfBoundsException if the index is out of bounds.
*/
@Override
public Country get(int position) {
if (position >= size || position < 0) {
throw new IndexOutOfBoundsException(Integer.valueOf(position).toString());
}
Node currentNode = head;
int counter = 0;
while (counter < position) {
counter++;
currentNode = currentNode.next;
}
return currentNode.country;
}
/**
* Returns the length of the list: the number of items stored in it.
*/
@Override
public int size() {
return size;
}
/**
* Returns true if the list has no items stored in it.
*/
@Override
public boolean isEmpty() {
return size == 0;
}
/**
* Returns a string representation of the items in order.
*/
@Override
public String toString() {
Node currentNode = head;
StringBuilder builder = new StringBuilder();
while (currentNode != null) {
builder.append(currentNode.country.getName()).append(" ");
currentNode = currentNode.next;
}
return builder.toString();
}
private static class Node {
Country country;
Node next;
public Node(Country country) {
this.country = country;
}
}
}
SORTED LIST
/**
* SortedList interface adapted from Carrano and Henry's interface in Data
* Structures and Abstractions with Java. A sorted list ADT is like a list,
* but maintains its entries in sorted order (rather than in the order they
* were inserted or the order that the user specified).
*/
public interface SortedList<T> {
/**
* Puts in several Nodes with test values to enable testing methods before add is implemented
*/
public void test();
/**
* Adds item to the list in sorted order.
*/
public void add(T item);
/**
* Returns the item at a given index.
*
* @return the item, or throw an IndexOutOfBoundsException if the index is out of bounds.
*/
public T get(int position);
/**
* Returns the length of the list: the number of items stored in it.
*/
public int size();
/**
* Returns true if the list has no items stored in it.
*/
public boolean isEmpty();
/**
* Returns a string representation of the items in order.
*/
public String toString();
}