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

(a)

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

---

public class MergeDoublyLinkedList
{
   /** merge the sorted lists a and b */
   public static DoublyLinkedList merge(DoublyLinkedList a, DoublyLinkedList 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 list
      DoublyLinkedList c = new DoublyLinkedList();
   
      // 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 codes and output are in the files MergeDoublyLinkedList.*.

(d)

The code for the member method is given below.

---

public class DoublyLinkedListWithMerge extends DoublyLinkedList
{
   /** make this the result of merging the sorted lists a and b 
     * following the merge, both a and b are empty */
   public void merge(DoublyLinkedListWithMerge a, DoublyLinkedListWithMerge b)
   {
      // special cases
      if (a.size == 0)
      {// a is empty
         firstNode = b.firstNode;
         lastNode = b.lastNode;
         size = b.size;
         b.clear();
         return;
      }

      if (b.size == 0)
      {// b is empty
         firstNode = a.firstNode;
         lastNode = a.lastNode;
         size = a.size;
         a.clear();
         return;
      }
   
      // neither a nor b is empty
      DoubleNode
                ca = a.firstNode,       // pointer to current node in a
                cb = b.firstNode;       // pointer to current node in b
      // 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;

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