In Java, Consider the complex linear data structure, a sorted set. A sorted set
ID: 3904875 • Letter: I
Question
In Java, Consider the complex linear data structure, a sorted set. A sorted set contains no duplicates and is sorted from smallest to largest.
Consider the following tasks:
a) Write a brief example of a practical use for such a data structure (invent something if you need to) and state whether your example would most benefit from an array?based implementation or a linked list?based implementation. There is no right or wrong answer, only properly and poorly supported justification. Consider ease of implementation and efficiency among your justification criteria.
b) Write an appropriate add method for a sorted set using either a linked list or array based on your argument in a). If you need helper methods, write them.
c) Write an appropriate remove method for a sorted set using either a linked list or array based on your argument in a). If you need helper methods, write them.
Explanation / Answer
Assumption :
Solution :
a) A sorted set can be used in a number of ways:
If we only need to search for data on a given sorted set, then array based implementation is preferable but if there are more add/remove operations than linked list based implementation is preferable.
The reasoning for above statement is :
b) As we are going to add values in the sorted set, I will use the linked list because of the reasoning done in part a) of this question.
Pseudo Code :
node * add(node * head, int key) // this function takes the sorted list and the key
// and returns the head of the new list with the key value
// inserted
{
new node * temp1;
new node * temp2;
temp2->next = NULL;
temp2->data = key;
if(home->data < key) // the new value is to be placed at the starting
{
temp2->next = head;
return temp2;
}
while ((temp->next->data < key)&&(temp->next != NULL))
{
temp = temp->next;
}
temp2->next = temp->next;
temp->next = temp2;
return head;
}
c) As we are going to remove values from the sorted set, I will use the linked list because of the reasoning done in part a) of this question.
Pseudo Code :
node * remove(node * head, int key) // this function takes the sorted list and the key
// and returns the head of the new list with the key value
// removed
{
node * temp1 = head;
node * temp2;
if(head->data == key)
{
head = head->next;
free(temp1); // freeing memory used by the deleted node of the set
return head;
}
while(temp1->next->data != key)
{
temp1 = temp1>next;
}
temp2 = temp1->next;
temp1->next = temp1->next->next;
free(temp2); // freeing memory used by the deleted node of the set
return head;
}
CODE:
// Java program to demonstrate insert/delete operation in Sorted LinkedList
import java.util.*;
import java.lang.*;
import java.io.*;
class LinkedList
{
/* Class containing next of current node and data value*/
class Node
{
int data;
Node next;
public Node(int item)
{
data = item;
next = null;
}
}
// Root of LinkedList
Node head;
// Constructor
LinkedList() {
head = null;
}
// This method mainly calls inst()
void insert(int key)
{
head = inst(head, key);
}
/* Function to insert a new key in LinkedList */
Node inst(Node head, int key)
{
Node temp = new Node(key);
Node tmp = null;
/* If the tree is empty, return a new node */
if (head == null) {
head = temp;
return head;
}
/* Otherwise, search for the correct position to insert the new node*/
if(head.data > key) //the correct position of the data is the first node
{
temp.next = head;
return temp;
}
tmp = head;
while((tmp.next!=null)&&(tmp.next.data < key))
// the correct posotion of the data is just after tmp Node
{
tmp = tmp.next;
}
temp.next = tmp.next;
tmp.next = temp;
/* return the head pointer */
return head;
}
// This method mainly calls remove()
void remove(int key)
{
head = rmv(head, key);
}
Node rmv(Node head, int key) // removes the deleting node and prints the List
{
Node temp = head;
if(temp.data == key)
{
temp = temp.next;
return temp;
}
else
{
while((temp.next!=null)&&(temp.next.data!=key))
{
temp = temp.next;
}
if(temp.next == null)
System.out.println("Error : Data not found");
else
{
temp.next = temp.next.next;
}
}
return head;
}
// This method prints the linked list
void P()
{
Node temp = head;
while(temp.next != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println(temp.data);
}
// Driver Program to test above functions
public static void main(String[] args) {
LinkedList lList = new LinkedList();
int i,key;
Scanner sc=new Scanner(System.in);
System.out.println(" Enter 1 to add a value in the sorted list");
System.out.println("Enter 2 to remove a value from the sorted list");
System.out.println("Enter -1 to exit the program ");
i = sc.nextInt();
while(i != -1)
{
if(i == 1)
{
System.out.print("Enter the value to be inserted : ");
key = sc.nextInt();
lList.insert(key);
}
else if (i == 2)
{
System.out.print("Enter the value to be deleted : ");
key = sc.nextInt();
lList.remove(key);
}
else
{
System.out.print("Error : Please enter a correct operation. ");
}
System.out.println(" Enter 1 to add a value in the sorted list");
System.out.println("Enter 2 to remove a value from the sorted list");
System.out.println("Enter -1 to exit the program ");
i = sc.nextInt();
lList.P();
}
// print the sorted set
lList.P();
}
}
*****************************NOTE*****************************
I have explained all answers to the best of my knowledge. If there is still some doubt left, please reply in the comments.
If everything is clear, please rate accordingly :)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.