Chapter 20, Problem 4AW

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.
• 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...