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

(a)

To complete the meld in linear time, we use two chain iterators ia and ib to march through the chains a and b respectively. When we fall off of one chain, the balance of the remaining chain is copied over to the melded chain c. Since elements from a and b are to be added to the end of the chain c, we use the single parameter add method of ExtendedChain (this appends an element to the right end of the chain). The code is given below.

---

public class MeldExtendedChain
{
   /** meld alternately from a and b */
   public static ExtendedChain meld(ExtendedChain a, ExtendedChain b)
   {
      // initialize iterators for a and b
      Iterator ia = a.iterator();  // iterator for a
      Iterator ib = b.iterator();  // iterator for b
   
      // create result chain
      ExtendedChain c = new ExtendedChain();
   
      // do the meld
      while (ia.hasNext() && ib.hasNext())
      {
         c.add(ia.next());   // append at right end
         c.add(ib.next());   // append at right end
      }
   
      // append the rest
      // 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)

Each invocation of add, hasNext, and next takes Theta(1) time. So, the time spent in all of the while loops is linear in the sum of the lengths of the chains a, and b. As a result, the complexity of meld is linear in the sum of the lengths of the two input chains a and b.

(c)

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