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

(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 HeadDoubleCircularList. The modified code is given below.

---

public class MergeHeadDoubleCircularList
{
   /** merge the sorted lists a and b */
   public static HeadDoubleCircularList merge(HeadDoubleCircularList a,
                                              HeadDoubleCircularList 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
      HeadDoubleCircularList c = new HeadDoubleCircularList();
   
      // 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 HeadDoubleCircularListWithMerge extends HeadDoubleCircularList
{
   /** make this the result of merging the sorted lists a and b 
     * following the merge, both a and b are empty */
   public void merge(HeadDoubleCircularListWithMerge a,
                     HeadDoubleCircularListWithMerge b)
   {
      DoubleNode
                ca = a.headerNode.next,     // pointer to current node in a
                cb = b.headerNode.next,     // pointer to current node in b
                lastNode = headerNode;      // last node of this

      // merge from a and b until one becomes empty
      while (ca != a.headerNode && cb != b.headerNode)
      {
         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, at most one of a and b is nonempty now
      if (ca != a.headerNode)
      {
         lastNode.next = ca;
         ca.previous = lastNode;
         lastNode = a.headerNode.previous;
      }

      if (cb != b.headerNode)
      {
         lastNode.next = cb;
         cb.previous = lastNode;
         lastNode = b.headerNode.previous;
      }

      size = a.size + b.size;
      lastNode.next = headerNode;
      headerNode.previous = lastNode;

      // 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 HeadDoubleCircularListWithMerge.*.