Program To Implement a Sorted Linked List and Comparator Using Java Programming Language Assignment Solutions.

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, Sorted Linked List 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 Country Comparator that implements the Comparator interface for Country:

public class Country Comparator implements Comparator :

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 takes 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 Country Comparator by making a new one in the main(String[] args) method of CountryComparator.java with some test Country objects.

Sorted Linked List

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 Sorted Linked List that implements the provided interface Sorted List just for Country:

public class Sorted Linked List implements Sorted List

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 my Comparator;

Copy the method signatures and comments from the Sorted List interface and turn them into method stubs in Sorted Linked List by returning something of the correct type for each method.

Constructor

Create a constructor that takes a Comparator 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 is Empty methods

Start by implementing the size and is Empty methods since they are short.

Using your test method, make sure that these work.

To String method

Adapt the to String 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 Index Out Of Bounds Exception:

throw new Index Out Of Bounds Exception();

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:

1. adding to the middle of the list
2. adding to the beginning of the list
3. 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 Sorted Linked List that each of the three cases for add works

Source Code

COUNTRY COMPARATOR import java.util.Comparator; public class CountryComparator implements Comparator { 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 { private final Comparator comparator; private int size; private Node head; public SortedLinkedList(Comparator 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 { /** * 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(); }