Implement the class shown on the following slides. The class implements a sorted
ID: 3878827 • Letter: I
Question
Implement the class shown on the following slides. The class implements a sorted linked list of Comparable objects. The list is sorted in ascending order. I will provide a test driver. The main method of the test driver expects either one or two command line arguments. The first command line argument indicates the input type (1 for integer or 2 for string). If only one argument is given then the input is from standard in. If two command line arguments are given then the input comes for a text file whose name is given in the second command line argument.
import java.io.*;
import java.util.*;
public class SortedList<T extends Comparable<? super T>> { // Implements a
// generic singly
// linked list of
// Comparable
// objects //Sorted
// in ascending
// order
private class Node {
private T data;
private Node next;
private Node(T d, Node n) {
data = d;
next = n;
}
}
private Node head; // Reference to the first node in the list
private int size; // The number of elements in the list
public SortedList() { // Constructor for an empty list
head = null; // no sentinel node size = 0;
}
public SortedList(SortedList<T> s1, SortedList<T> s2) {
// PRE: s1.size() > 0 && s2.size() > 0
// Constructor for the list created from two SortedLists
// A new SortedList is created containing all the data from s1 and s2
// //The implementation must take advantage of the fact that s1 and s2
// //are sorted. The implementation cannot use the insert method
}
public void insert(T item) {
// Insert item into the list so the list remains sorted //The list can
// contain duplicates
}
public void remove(T item) {
// Remove all occurrences of item from the list
}
public int find(T item) {
// Return the number of times item is found on the list //Use equals or
// compareTo not == to compare items }
}
public int size() {
// Return the number of items in the list
return size;
}
public String toString() {
// Return a string representation of the list
// The string representation of the list is a [ followed by the items in
// the list //separated by commas followed by a ]
// For example a list of integers could look like [2,3,7,10,50,107]
}
}
TEST DRIVER
import java.io.*;
import java.util.*;
//Test driver for SortedList //Do not send me this file
public class TestSortedList {
public SortedList<Integer> getIntList(Scanner scan, boolean prompt) {
SortedList<Integer> list = new SortedList<>();
if (prompt)
System.out.print("Enter a line of ints separated by commas: ");
String line = scan.nextLine();
String input[] = line.split(",");
for (int i = 0; i < input.length; i++)
list.insert(new Integer(input[i]));
return list;
}
public SortedList<String> getStringList(Scanner scan, boolean prompt) {
SortedList<String> list = new SortedList<>();
if (prompt)
System.out.print("Enter a line of string separated by commas: ");
String line = scan.nextLine();
String input[] = line.split(",");
for (int i = 0; i < input.length; i++)
list.insert(input[i]);
return list;
}
public void removeInts(Scanner scan, SortedList<Integer> list, boolean prompt) {
if (prompt)
System.out.print("Enter a line of ints to remove separated by commas: ");
String line = scan.nextLine();
String input[] = line.split(",");
for (int i = 0; i < input.length; i++)
list.remove(new Integer(input[i]));
}
public void removeStrings(Scanner scan, SortedList<String> list, boolean prompt) {
if (prompt)
System.out.print("Enter a line of strings to remove separated by commas: ");
String line = scan.nextLine();
String input[] = line.split(",");
for (int i = 0; i < input.length; i++)
list.remove(input[i]);
}
public void testIntList(Scanner scan, boolean prompt) {
SortedList<Integer> list1 = getIntList(scan, prompt);
SortedList<Integer> list2 = getIntList(scan, prompt);
SortedList<Integer> list3 = new SortedList<Integer>(list1, list2);
removeInts(scan, list3, prompt);
System.out.println(list3);
}
public void testStringList(Scanner scan, boolean prompt) {
SortedList<String> list1 = getStringList(scan, prompt);
SortedList<String> list2 = getStringList(scan, prompt);
SortedList<String> list3 = new SortedList<String>(list1, list2);
removeStrings(scan, list3, prompt);
System.out.println(list3);
}
public TestSortedList(int dataType) {
Scanner scan = new Scanner(System.in);
if (dataType == 1) { // integer input
testIntList(scan, true);
} else { // string input
testStringList(scan, true);
}
}
public TestSortedList(int dataType, String filename) throws IOException {
Scanner scan = new Scanner(new File(filename));
if (dataType == 1) { // integer input
testIntList(scan, false);
} else { // string input
testStringList(scan, false);
}
}
public static void main(String args[]) throws IOException {
if (args.length == 0) { // Error
System.out.println(
"Error: you must provide at least one command line argument: the data type of the input. 1 means integers and 2 means strings");
} else if (args.length == 1) { // get input from standard in
new TestSortedList(new Integer(args[0]));
} else if (args.length == 2) { // get input from a file with a name
// given in args[1]
new TestSortedList(new Integer(args[0]), args[1]);
}
}
}
Explanation / Answer
Given below is the completed code for the question. Please pass appropriate command line arguments for the test program. I have passed 1 and given the output at end
Please do rate the answer if it was helpful. Thank you
To indent code in eclipse , select code by pressing ctrl+a and then indent using ctrl+i
import java.io.*;
import java.util.*;
public class SortedList<T extends Comparable<? super T>> { // Implements a
// generic singly
// linked list of
// Comparable
// objects //Sorted
// in ascending
// order
private class Node {
private T data;
private Node next;
private Node(T d, Node n) {
data = d;
next = n;
}
}
private Node head; // Reference to the first node in the list
private int size; // The number of elements in the list
public SortedList() { // Constructor for an empty list
head = null; // no sentinel node size = 0;
}
public SortedList(SortedList<T> s1, SortedList<T> s2) {
// PRE: s1.size() > 0 && s2.size() > 0
// Constructor for the list created from two SortedLists
// A new SortedList is created containing all the data from s1 and s2
// //The implementation must take advantage of the fact that s1 and s2
// //are sorted. The implementation cannot use the insert method
Node h1 = s1.head;
Node h2 = s2.head;
Node last = null;
Node n;
while(h1 != null && h2 != null)
{
if(h1.data.compareTo(h2.data) < 0) //node from s1 is lesser than node from list s2
{
n = new Node(h1.data, null);
h1 = h1.next;
}
else
{
n = new Node(h2.data, null);
h2 = h2.next;
}
if(head == null)
head = last = n;
else
{
last.next = n;
last = n;
}
size++;
}
while(h1 != null)
{
n = new Node(h1.data, null);
h1 = h1.next;
if(head == null)
head = last = n;
else
{
last.next = n;
last = n;
}
size++;
}
while(h2 != null)
{
n = new Node(h2.data, null);
h2 = h2.next;
if(head == null)
head = last = n;
else
{
last.next = n;
last = n;
}
size++;
}
}
public void insert(T item) {
// Insert item into the list so the list remains sorted //The list can
// contain duplicates
Node n = new Node(item, null);
if(head == null)
{
head = n;
size++;
return;
}
Node prev = null, curr = head;
while(curr != null)
{
if(item.compareTo(curr.data) < 0)
break;
prev = curr;
curr = curr.next;
}
if(curr == head) //insert before head
{
n.next = head;
head = n;
}
else
{
prev.next = n;
n.next = curr;
}
size++;
}
public void remove(T item) {
// Remove all occurrences of item from the list
Node prev = null;
Node curr = head;
while(curr != null)
{
if(curr.data.equals(item))
{
if(prev == null) //removing head node?
{
head = head.next;
curr = head;
}
else
{
prev.next = curr.next;
curr = prev.next;
}
size--;
}
else
{
prev = curr;
curr = curr.next;
}
}
}
public int find(T item) {
// Return the number of times item is found on the list //Use equals or
// compareTo not == to compare items }
int times = 0;
Node n = head;
while(n != null)
{
if(n.equals(item))
times++;
n = n.next;
}
return times;
}
public int size() {
// Return the number of items in the list
return size;
}
public String toString() {
// Return a string representation of the list
// The string representation of the list is a [ followed by the items in
// the list //separated by commas followed by a ]
// For example a list of integers could look like [2,3,7,10,50,107]
String s = "[";
Node n = head;
if(n != null)
{
s += n.data;
n = n.next;
while(n != null)
{
s += "," + n.data;
n = n.next;
}
}
s += "]";
return s;
}
}
output
=====
Enter a line of ints separated by commas: 5,3,9,2
Enter a line of ints separated by commas: 8,0,6,4
Enter a line of ints to remove separated by commas: 5,8
[0,2,3,4,6,9]