Explanation of Solution
Method definition for “removeMin()”:
The method definition for “removeMin()” is given below:
/* Method definition for "removeMin()" */
String removeMin()
{
/* If the list head is null, then */
if (first == null)
//Returns null
return null;
/* Set minimum string to "first" node */
Node minimumString = first;
/* Set minimum string predecessor to list head*/
Node minimumPred = first;
/* Set reference node to next node of list head */
Node refNode = first.next;
/* Set the reference of predecessor node */
Node refPred = first;
/* If the reference node "refNode" is not "null", then */
while (refNode != null)
{
/* Check condition */
if (refNode.value.compareTo(minimumString.value) < 0)
{
/* Assign minimum string to "refNode" */
minimumString = refNode;
/* Set minimum predecessor to reference of predecessor */
minimumPred = refPred;
}
/* Set "refPred" to "refNode*/
refPred = refNode;
/* Set "refNode" to next reference node */
refNode = refNode.next;
}
// Compute If the first node is the minimum or not
String resultantString = minimumString.value;
/* If the minimum string is list head, then */
if (minimumString == first)
{
//Remove the first string
first = first.next;
/* If the list head is "null", then */
if (first == null)
/* Set "last" to "null" */
last = null;
}
//Otherwise
else
{
//Remove an element with a predecessor
minimumPred.next = minimumString.next;
// If the last item removed, then
if (minimumPred.next == null)
/* Assign "last" to "minimumPred" */
last = minimumPred;
}
/* Finally returns the resultant string elements */
return resultantString;
}
Explanation:
The above method definition is used to remove a minimum element from a list.
- If the list head is null, then returns null.
- Set minimum string and minimum predecessor to “first” node.
- Set reference node to next node of list head and also set the reference of predecessor node.
- Performs “while” loop. This loop will perform up to the “refNode” becomes “null”.
- Check condition using “if” loop.
- If the given condition is true, then assign minimum string to “refNode”.
- Set minimum predecessor to reference of predecessor.
- Set “refPred” to “refNode”.
- Set “refNode” to next reference node.
- Check condition using “if” loop.
- Compute if the first node is minimum or not.
- If the minimum string is list head, then
- Remove the first string.
- If the list head is “null”, then set “last” to “null”.
- Otherwise,
- Remove an element with a predecessor.
- If the last item removed, then assign “last” to “minimumPred”.
- Finally returns the resultant string elements.
Complete code:
The complete executable code for remove a minimum string element from a linked list is given below:
//Define "LinkedList1" class
class LinkedList1
{
/** The code for this part is same as the textbook of "LinkedList1" class */
/* Method definition for "removeMin()" */
String removeMin()
{
/* If the list head is null, then */
if (first == null)
//Returns null
return null;
/* Set minimum string to "first" node */
Node minimumString = first;
/* Set minimum string predecessor to list head*/
Node minimumPred = first;
/* Set reference node to next node of list head */
Node refNode = first...
Want to see the full answer?
Check out a sample textbook solutionChapter 19 Solutions
Starting Out with Java: From Control Structures through Data Structures (4th Edition) (What's New in Computer Science)
- If N represents the number of elements in the collection, then the contains method of the ArrayCollection class is O(1). True or False If N represents the number of elements in the list, then the index-based add method of the ABList class is O(N). True or Falsearrow_forwardLAB: Inserting an integer in descending order (doubly-linked list) Given main() and an IntNode class, complete the IntList class (a linked list of IntNodes) by writing the insertInDescendingOrder() method to insert new IntNodes into the IntList in descending order. Ex. If the input is: 3 4 2 5 1 6 7 9 8 -1 the output is: 9 8 7 6 5 4 3 2 1 public class IntList {// Linked list nodes public IntNode headNode;public IntNode tailNode; public IntList() {// Front of nodes list headNode = null;tailNode = null;} // append public void append(IntNode newNode) {if (headNode == null) { // List empty headNode = newNode;tailNode = newNode;}else {tailNode.nextNode = newNode;newNode.prevNode = tailNode;tailNode = newNode;}} // prepend public void prepend(IntNode newNode) {if (headNode == null) { // list empty headNode = newNode;tailNode = newNode;}else {newNode.nextNode = headNode;headNode.prevNode = newNode;headNode = newNode;}}// insertAfter public void insertAfter(IntNode curNode, IntNode…arrow_forwardLAB: Inserting an integer in descending order (doubly-linked list) Given main() and an IntNode class, complete the IntList class (a linked list of IntNodes) by writing the insertInDescendingOrder() method to insert new IntNodes into the IntList in descending order. Ex. If the input is: 3 4 2 5 1 6 7 9 8 -1 the output is: 9 8 7 6 5 4 3 2 1 ______________________________ import java.util.Scanner; public class SortedList { public static void main (String[] args) {Scanner scnr = new Scanner(System.in);IntList intList = new IntList();IntNode curNode;int num; num = scnr.nextInt(); while (num != -1) {// Insert into linked list in descending order curNode = new IntNode(num);intList.insertInDescendingOrder(curNode);num = scnr.nextInt();}intList.printIntList();}} __________________________________ public class IntList {// Linked list nodespublic IntNode headNode;public IntNode tailNode; public IntList() {// Front of nodes listheadNode = null;tailNode = null;} // appendpublic void…arrow_forward
- Lab 17 Using a linked list with an iterator Build a class called LinkedListRunner with a main method that instantiates a LinkedList. Add the following strings to the linked list: aaa bbb ddd еее fff ggg hhh ii Build a ListIterator and use it to walk sequentially through the linked list using hasNext and next, printing each string that is encountered. When you have printed all the strings in the list, use the hasPrevious and previous methods to walk backwards through the list. Along the way, examine each string and remove all the strings that begin with a vowel. When you arrive at the beginning of the list, use hasNext and next to go forward again, printing out each string that remains in the linked list.arrow_forwardWrite an equals method for the LBList class. Return true if the lists have the same number of elements and the elements in each position of the lists are the same; otherwise return false. DO NOT USE ANY OTHER METHODS OF THE LBLIST CLASS.arrow_forwardLab 17 Using a linked list with an iterator Build a class called LinkedListRunner with a main method that instantiates a LinkedList. Add the following strings to the linked list: aaa bbb cc ddd eee fff ggg hhh iii Build a ListIterator and use it to walk sequentially through the linked list using hasNext and next, printing each string that is encountered. When you have printed all the strings in the list, use the hasPrevious and previous methods to walk backwards through the list. Along the way, examine each string and remove all the strings that begin with a vowel. When you arrive at the beginning of the list, use hasNext and next to go forward again, printing out each string that remains in the linked list.arrow_forward
- Part2: LinkedList implementation 1. Create a linked list of type String Not Object and name it as StudentName. 2. Add the following values to linked list above Jack Omar Jason. 3. Use addFirst to add the student Mary. 4. Use addLast to add the student Emily. 5. Print linked list using System.out.println(). 6. Print the size of the linked list. 7. Use removeLast. 8. Print the linked list using for loop for (String anobject: StudentName){…..} 9. Print the linked list using Iterator class. 10. Does linked list hava capacity function? 11. Create another linked list of type String Not Object and name it as TransferStudent. 12. Add the following values to TransferStudent linked list Sara Walter. 13. Add the content of linked list TransferStudent to the end of the linked list StudentName 14. Print StudentName. 15. Print TransferStudent. 16. What is the shortcoming of using Linked List?arrow_forwardQuestion 1 If N represents the number of elements in the collection, then the add method of the SortedArrayCollection class is O(N). True False Question 2 If N represents the number of elements in the list, then the index-based remove method of the ABList class is O(N). True False Question 3 The add method of our Collection ADT might throw the CollectionOverflowException. True False Question 4 A list allows retrieval of information based on the size of the information. True False Question 5 Our CollectionInterface defines a single constructor. True False Question 6 Our lists allow null elements. True False Question 7 Even though our collections will be generic, our CollectionInterface is not generic. True False Question 8 Our lists are unbounded. True False Question 9 If N represents the number of elements in the collection, then the contains method of the ArrayCollection class is O(N). True False Question 10 Our lists allow duplicate elements. True Falsearrow_forwardWe can access the element using subscript directly even if it is somewhere in between, we cannot do the same random access with a linked list. * True O Falsearrow_forward
- maxLength Language/Type: Related Links: Java Set collections Set Write a method maxLength that accepts as a parameter a Set of strings, and that returns the length of the longest string in the set. If your method is passed an empty set, it should return 0. 1 9 10 Method: Write a Java method as described, not a complete program or class. N345678 2arrow_forwardWhat is the ArrayList list's starting size?arrow_forward3. void insert (Node newElement) or def insert(self, newElement) (4) Pre-condition: None. Post-condition: This method inserts newElement at the tail of the list. If an element with the same key as newElement already exists in the list, then it concludes the key already exists and does not insert the key.arrow_forward
- EBK JAVA PROGRAMMINGComputer ScienceISBN:9781337671385Author:FARRELLPublisher:CENGAGE LEARNING - CONSIGNMENT