Data Structures, Algorithms, & Applications in Java
Chapter 11, Exercise 9

Before we can delete the minimum element, we must verify that the structure is not empty. When we have at least one element in the skip list, the minimum element is the first one in the level 0 chain. Therefore, the minimum element can be removed by the invocation remove(headNode.next[0].key).

Before we can delete the maximum element, we need to verify that such an element exists. This is so iff the structure is not empty. If there is a max element, it is in the last node on the level 0 chain. The max element is in the node with next[0] equal to tailNode. We can find this node by invoking search(tailKey). Following this invocation, last[0] points to the node just before the tail. This node contains the max element. This max element may be removed using the invocation return remove(last[0].key).

The code that implements the above strategy is given below. 

public class ExtendedSkipList1 extends SkipList
{
   // constructor
   public ExtendedSkipList1(Comparable largeKey, int maxElements, float theProb)
      {super(largeKey, maxElements, theProb);}

   /** @return element with smallest key and remove it
     * @return null if no element */
   public Object removeMinElement()
   {
      // make sure there is a min element
      if (headNode.next[0] == tailNode)
         // dictionary is empty
         return null;
   
      // remove the minimum element
      return remove(headNode.next[0].key); // min key
   }
   
   /** @return element with largest key and remove it
     * @return null if no element */
   public Object removeMaxElement()
   {
      // make sure there is a maximum element
      if (headNode.next[0] == tailNode)
         // dictionary is empty
         return null;
    
      // search for tail key
      search(tailKey);
      // remove element with largest key
      return remove(last[0].key);
   }
}
The call to remove in the above code for removeMinElement results in a search for the element with key theKey and the setting of the array last. This is unneccessary as we know that the element is in headNode.next[0] and that all last values are headNode. So we can eliminate the work done by the search that is invoked by remove and tailor the remainder of the code in remove to our situtaion.

We can also make the code for removeMax more efficient. The new, more efficient, codes are given below. 

public class ExtendedSkipList2 extends SkipList
{
   // constructor
   public ExtendedSkipList2(Comparable largeKey, int maxElements, float theProb)
      {super(largeKey, maxElements, theProb);}

   /** @return element with smallest key and remove it
     * @return null if no element */
   public Object removeMinElement()
   {
      // make sure there is a min element
      if (headNode.next[0] == tailNode)
         // dictionary is empty
         return null;
   
      // save pointer to node with min element
      SkipNode minNode = headNode.next[0];
   
      // remove minNode from structure
      for (int i = 0; i <= levels &&
               headNode.next[i] == minNode; i++)
         headNode.next[i] = headNode.next[i].next[i];
   
      // update levels
      while (levels > 0 && headNode.next[levels] == tailNode)
         levels--;
   
      // return min element
      return minNode.element;
   }
   
   /** @return element with largest key and remove it
     * @return null if no element */
   public Object removeMaxElement()
   {
      // make sure there is a maximum element
      if (headNode.next[0] == tailNode)
         // dictionary is empty
         return null;
    
      // search for max element
      SkipNode y = headNode;
      for (int i = levels; i >= 0; i--)
         while (y.next[i] != tailNode)
            y = y.next[i];
   
      // remove element with largest key
      return remove(y.key);
   }
}


The expected complexity of removeMinElement and removeMaxElement is O(log n). Here n is the number of elements in the skip list.

The test programs and output are in the files ExtendedSkipList1.* and ExtendedSkipList2.*.