8. [14 pts] Implement an extractLessThan operation on a singly-linked list with

Question

8. [14 pts] Implement an extractLessThan operation on a singly-linked list with no tail pointer. Your code SHOULD NOT delete memory, only return a new LinkedList with the value less than parameter value. Your code must not call other LinkedList functions. Order of the extracted nodes does not matter. struct LinkNode t Data data; /mote that you can cospare by calling data->compareTo (other) LinkNodenext; class LinkedList t LinkNode head; /es . Returns a nev LinkedList that contains all of the LinkNodes from this * LinkedList that have node->data->compareTo(value) ? LinkedList.x/x containe [5, 8, 1, 3 * Data value nev IntegerData(4); * LinkedList . y-z->extractLeseThan(value); 11 z nov contains (5, 8] and y now contains (3, 1 o/ // You have access to head and to this LinkedList extractLeseThan(Data value) ( LinkedList nevList nev LinkedList O LinkNode current head; Linklode previous SULL

Explanation / Answer

Ans.

As it was not mandatory to solve this question in c++ so i am providing the solution in java. It may be possible that some of the line you will not understant so feel free to ask in the commen. I had tried to provide as much comment in the solution but if due to any reason you are not able to understand the solution feel free to ask. My solution is below:-

import java.util.Scanner;
/**
* This class is used to create a linked list from a existing linked list
* whose value is less than a value which will be passed to the method.
* @author Nirankar
*
*/
public class LinkedList {
/**
* Inner class to create a node.
* @author Nirankar
*
*/
class LinkNode{
int data;
LinkNode next;
}
/**
* This is the starting point of the linkedList
*/
LinkNode head;
/**
* This method is used to create two list one contain a list whose element is greater
* than or equal to the value and one whose element less than value
* @param value
* @return
*/
public LinkNode exactLessThan(int value){
//this will point the head of second list
LinkNode newList=null;
//this will be the head of the first list
LinkNode current=head;
//this will be the previous node of the first list which will be use to remove the element which
//will be less than the value.
LinkNode previous=head;
//this is used to creating the second list
LinkNode currentNewList=null;
while(null!=current){
//check for node data less than value
if(current.data<value){
//check if node is the first node whose data is less than the value
if(head==current){
head=head.next;
previous=head;
if(null==newList){
newList=new LinkNode();
newList=current;
currentNewList=newList;
newList.next=null;
currentNewList.next=null;
}else{
currentNewList.next=current;
currentNewList=current;
currentNewList.next=null;
}
current=head;
}
//check if node is not the first node whose data is less than the value
else{
previous.next=current.next;
if(null==newList){
newList=new LinkNode();
newList=current;
currentNewList=newList;
newList.next=null;
currentNewList.next=null;
}else{
currentNewList.next=current;
currentNewList=current;
currentNewList.next=null;
}
current=previous.next;
}
continue;
}
previous=current;
current=current.next;
}
return newList;
}
/**
* This method is used to create a node with the specified value.
* @param val
* @return
*/
public LinkNode createNode(int val){
LinkNode node=new LinkNode();
node.data=val;
node.next=null;
return node;
}
/**
* This is the main method to check whether my program is working correctly or not.
* @param args
*/
public static void main(String[] args) {
LinkedList list=new LinkedList();
LinkNode newNode=list.head;
System.out.println("Enter Number Of Node:");
Scanner sc=new Scanner(System.in);
int i=sc.nextInt();
for(int j=0;j<i;j++){
LinkNode node=list.createNode(sc.nextInt());
if(list.head==null){
list.head=node;
newNode=list.head;
}else{
newNode.next=node;
newNode=node;
}
}
System.out.println("Enter a value for which two list has to create:");
int value=sc.nextInt();
LinkNode newList=list.exactLessThan(value);
printValue(newList);
printValue(list.head);
}
/**
* This method is used to print the value of the list.
* @param newList
*/
private static void printValue(LinkNode newList) {
while(null!=newList){
System.out.print(newList.data+",");
newList=newList.next;
}
System.out.println();
}
}

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.