This code implements a Sorted Singly Linked List Class. It implements two merge
ID: 3594103 • Letter: T
Question
This code implements a Sorted Singly Linked List Class. It implements two merge functions. The program seems to run fine and it does return the sorted elements of the list from various input text files containing unosrted lists of numbers. However, I dont want the resulting lists to contain repeating elements. How do i do this?
public class SortedSLLClass ( class Node if(pointer1 null int value; Node next; Node(int val)kvalue-valnext null public void merge_smart(SortedSLLClass otherSSLLX Node temp pointers while(temp.nextl nullX Node pointer!=currentSSLL; Node pointer2=otherSSLL.currentSSLL; temp temp.next Node pointer3-null; Node currentSSLL; public SortedSLLClasso0 temp.next-pointer1 while(pointer! !=null && pointer21=null){ if(pointer1.valueExplanation / Answer
SLLMainClass.java
---------------------------------------------------------------
import java.util.Scanner;
import java.io.File;
public class SLLMainClass {
public static SortedSLLClass ParseArray(String file_name){
Scanner sc = null;
int tmpi;
SortedSLLClass myssll = new SortedSLLClass();
try {
sc = new Scanner(new File(file_name));
while (sc.hasNext()) {
tmpi = sc.nextInt();
myssll.insert(tmpi);
System.out.print(tmpi + " ");
}
System.out.println("");
sc.close();
return myssll;
} catch (Exception e) {
return null;
}
}
public static void main(String[] args) {
int n = args.length; // number of lists to read
if(n <= 0)
return;
long startTime, endTime, totalTime;
String fname;
startTime = System.currentTimeMillis();
SortedSLLClass[] ssll_list = new SortedSLLClass[n];
for(int i = 0; i < n; ++i){
fname = args[i];
System.out.println("Input "+i + ": ");
ssll_list[i] = ParseArray(fname); // read one list
if(ssll_list[i] == null){
// if invalid input file, print NULL and exit
System.out.println("NULL");
System.out.println("Error parsing file: "+fname);
return;
}
}
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
System.out.println("List constructing time: " + totalTime );
// naive implementation
startTime = System.currentTimeMillis();
SortedSLLClass merged_naive = new SortedSLLClass( ssll_list[0] ); // copy the first list into merged_naive
for(int i = 1; i < n; ++i)
merged_naive.merge_naive(ssll_list[i]);
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
System.out.println("Naive merging result: ");
// output the final result
int[] naive_result = merged_naive.getAllElements();
for(int i = 0; i < naive_result.length; i++)
System.out.print(naive_result[i] + " ");
System.out.println(" ");
System.out.println("Naive merging time: " + totalTime );
// smart implementation
startTime = System.currentTimeMillis();
SortedSLLClass merged_smart = new SortedSLLClass( ssll_list[0] ); // copy the first list into merged_naive
for(int i = 1; i < n; ++i)
merged_smart.merge_smart(ssll_list[i]);
endTime = System.currentTimeMillis();
totalTime = endTime - startTime;
System.out.println("Smart merging result: ");
// output the final result
int[] smart_result = merged_smart.getAllElements();
for(int i = 0; i < smart_result.length; i++)
System.out.print(smart_result[i] + " ");
System.out.println(" ");
System.out.println("Smart merging time: " + totalTime );
}
}
---------------------------------------------------------------------------------------------
SortedSLLClass.java
-----------------------------------------------------
public class SortedSLLClass {
class Node{
int value;
Node next;
Node(int val){value=val;next=null;}
}
Node currentSSLL;
public SortedSLLClass(){
currentSSLL=null;
}
public SortedSLLClass(SortedSLLClass otherSSLL){
this.currentSSLL=otherSSLL.currentSSLL;
}
public boolean insert(int val){
Node temp=new Node(val);
if(currentSSLL==null || currentSSLL.value> temp.value){
temp.next=currentSSLL;
currentSSLL=temp;
}else{
Node currentNode=currentSSLL;
while(currentNode.next!=null && currentNode.next.value < temp.value){
currentNode=currentNode.next;
}
temp.next=currentNode.next;
currentNode.next=temp;
}
return true;
}
public void merge_naive(SortedSLLClass otherSSLL){
Node otherListNode=otherSSLL.currentSSLL;
while(otherListNode!=null){
insert(otherListNode.value);
otherListNode=otherListNode.next;
}
}
public void merge_smart(SortedSLLClass otherSSLL){
Node pointer1=currentSSLL;
Node pointer2=otherSSLL.currentSSLL;
Node pointer3=null;
while(pointer1!=null && pointer2!=null){
if(pointer1.value<pointer2.value){
if(pointer3==null){
Node temp=pointer1;
temp.next=null;
pointer3=temp;
}
else{
Node temp=pointer3;
while(temp.next!=null){
temp=temp.next;
}
temp.next=pointer1;
temp.next.next=null;
}
pointer1=pointer1.next;
}else {
if(pointer3==null){
Node temp=pointer2;
temp.next=null;
pointer3=temp;
}
else{
Node temp=pointer3;
while(temp.next!=null){
temp=temp.next;
}
temp.next=pointer2;
temp.next.next=null;
}
pointer2=pointer2.next;
}
}
if(pointer1!=null){
Node temp=pointer3;
while(temp.next!=null){
temp=temp.next;
}
temp.next=pointer1;
}
if(pointer2!=null){
Node temp=pointer3;
while(temp.next!=null){
temp=temp.next;
}
temp.next=pointer2;
}
currentSSLL=pointer3;
}
public int[] getAllElements(){
Node temp=currentSSLL;
int k=0;
while(temp!=null){
k++;
temp=temp.next;
}
temp=currentSSLL;
int[] a = new int[k];
int i=0;
while(temp!=null){
a[i]=temp.value;
temp=temp.next;
i++;
}
return a;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.