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 20 Solutions
Starting Out with Java: From Control Structures through Data Structures (3rd Edition)
- 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_forwardPart2: 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_forwardmaxLength 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_forward
- What is the ArrayList list's starting size?arrow_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_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
- Make a doubly linked list and apply all the insertion, deletion and search cases. The node willhave an int variable in the data part. Your LinkedList will have a head and a tail pointer.Your LinkedList class must have the following functions: 1) insert a node1. void insertNodeAtBeginning(int data);2. void insertNodeInMiddle(int key, int data); //will search for keyand insert node after the node where a node’s data==key3. void insertNodeAtEnd(int data);2) delete a node1. bool deleteFirstNode(); //will delete the first node of the LL2. bool deleteNode(int key); //search for the node where its data==keyand delete that particular node3. bool deleteLastNode(); //will delete the last node of the LL3) Search a node1. Node* searchNodeRef(int key); //will search for the key in the datapart of the node2. bool searchNode(int key); The program must be completely generic, especially for deleting/inserting the middle nodes. Implement all the functions from the ABOVE STATEMENTS and make a login and…arrow_forward· Write a method to insert an element at index in a Doubly Linked List data structure and test it. The method receives this list by parameters. * in javaarrow_forwardjava program java method: Write a method replace to be included in the class KWLinkedList (for doubly linked list) that accepts two parameters, searchItem and repItem of type E. The method searches for searchItem in the doubly linked list, if found then replace it with repItem and return true. If the searchItem is not found in the doubly linked list, then insert repItem at the end of the linked list and return false. Assume that the list is not empty. You can use ListIterator and its methods to search the searchItem in the list and replace it with repItem if found. Do not call any method of class KWLinkedList to add a new node at the end of the list. Method Heading: public boolean replace(E searchItem, E repItem) Example: searchItem: 15 repItem: 17 List (before method call): 9 10 15 20 4 5 6 List (after method call) : 9 10 17 20 4 5 6arrow_forward
- o create the linkage for the nodes of our linkedlist. The class includes several methods for adding nodes to the list, removingnodes from the list, traversing the list, and finding a node in the list. We alsoneed a constructor method that instantiates a list. The only data member inthe class is the header node.use c#arrow_forwardpublic LLNode secondHalf(LLNode head) { }arrow_forwardSuppose that you want an operation for the ADT list that adds an array of items to the end of the list. The header of the method could be as follows: public void addAll( T[ ] items) Write an implementation of this method for the class LinearLinkedListarrow_forward
- EBK JAVA PROGRAMMINGComputer ScienceISBN:9781337671385Author:FARRELLPublisher:CENGAGE LEARNING - CONSIGNMENT