Data Structures, Algorithms, & Applications in Java
Chapter 6, Exercise 49

(a)

For the nonmember method, we can use essentially the same code as used in Exercise 15 to merge two chains. We must change all occurrences of ExtendedChain to DoubleCircularList. The modified code is given below.

---

public class MergeDoubleCircularList
{
   /** merge the sorted lists a and b */
   public static DoubleCircularList merge(DoubleCircularList a,
                                          DoubleCircularList b)
   {
      // initialize iterators for a and b
      Iterator ia = a.iterator();     // iterator for a
      Iterator ib = b.iterator();     // iterator for b
      Comparable elementA = null;     // current element of a
      if (ia.hasNext())
         elementA = (Comparable) ia.next();
      Object elementB = null;         // current element of b
      if (ib.hasNext())
         elementB = ib.next();
   
      // create result chain
      DoubleCircularList c = new DoubleCircularList();
   
      // do the merge
      while (elementA != null && elementB != null)
      {
         if (elementA.compareTo(elementB) <= 0)
         {// elementA goes next
            c.add(elementA);
            if (ia.hasNext())
               elementA = (Comparable) ia.next();
            else
               elementA = null;
         }
         else
         {// elementB goes next
            c.add(elementB);
            if (ib.hasNext())
               elementB = ib.next();
            else
               elementB = null;
         }
      }
   
      // add remaining elements
      if (elementA != null)
         c.add(elementA);
      if (elementB != null)
         c.add(elementB);

      // at most one of a and b can be nonempty now
      while (ia.hasNext())
         c.add(ia.next());
   
      while (ib.hasNext())
         c.add(ib.next());
   
      return c;
   }
}

(b)

In each iteration of the first while loop, we move one node right either in a or either in b. So, the complexity of this loop is O(a.size + b.size). The complexity of the second while loop is O(a.size), and that of the third loop is O(b.size). So, the overall complexity is O(a.size + b.size).

(c)

The test program and output are in the files MergeDoubleCircularList.*.

(d)

The code for the member method is given below.

---

public class DoubleCircularListWithMerge extends DoubleCircularList
{
   /** make this the result of merging the sorted lists a and b 
     * following the merge, both a and b are empty */
   public void merge(DoubleCircularListWithMerge a,
                     DoubleCircularListWithMerge b)
   {
      // special cases
      if (a.size == 0)
      {// a is empty
         // move all of b to this
         lastNode = b.lastNode;
         size = b.size;

         // make b empty
         b.clear();

         return;
      }

      if (b.size == 0)
      {// b is empty
         // move all of a to this
         lastNode = a.lastNode;
         size = a.size;

         // make a empty
         a.clear();

         return;
      }
   
      // neither a nor b is empty
      DoubleNode
                ca = a.lastNode.next,       // pointer to current node in a
                cb = b.lastNode.next,       // pointer to current node in b
                firstNode;                  // first node of this

      // make a and b noncircular
      a.lastNode.next = null;
      b.lastNode.next = null;

      // merge first node for this
      if (((Comparable) ca.element).compareTo(cb.element) <= 0)
      {// first node of this is from a
         firstNode = lastNode = ca;
         ca = ca.next;
      }
      else
      {// first node of this is from b
         firstNode = lastNode = cb;
         cb = cb.next;
      }
   
      // merge from a and b until one becomes empty
      while (ca != null && cb != null)
      {
         if (((Comparable) ca.element).compareTo(cb.element) <= 0)
         {// a element goes first
            lastNode.next = ca;
            ca.previous = lastNode;
            lastNode = ca;
            ca = ca.next;
         }
         else
         {// b element is smaller
            lastNode.next = cb;
            cb.previous = lastNode;
            lastNode = cb;
            cb = cb.next;
         }
      }

      // append the rest, exactly one of a and b is nonempty now
      if (cb == null)
      {
         lastNode.next = ca;
         ca.previous = lastNode;
         lastNode = a.lastNode;
      }
      else
      {
         lastNode.next = cb;
         cb.previous = lastNode;
         lastNode = b.lastNode;
      }

      size = a.size + b.size;
      lastNode.next = firstNode;   // make this circular

      // make a and b empty
      a.clear();
      b.clear();

      return;
   }
}

(e)

In each iteration of the while loop, we move one node right either in a or in b. So, the complexity of this loop is O(a.size + b.size). The remainder of the code takes Theta(1) time. So, the overall complexity is O(a.size + b.size).

(f)

The test program and output are in the files DoubleCircularListWithMerge.*.