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

(a)

The code to split a chain is given below.

public class SplitExtendedChain
{
   /** split a into b and c */
   public static void split(ExtendedChain a, ExtendedChain b,
                            ExtendedChain c)
   {
      // first empty out b and c
      b.clear();
      c.clear();
   
      // assign elements of a alternately to b and c using an
      // iterator ia for a
      Iterator ia = a.iterator();
      while (ia.hasNext())
      {
         // first give b an element
         b.add(ia.next());
         if (!ia.hasNext()) break;

         // now give c an element
         c.add(ia.next());
      }
   }
}

(b)

The time needed to empty the lists b and c is Theta(1). Each add takes Theta(1) time because the new element is added at the end of the list. The while loop iterates at most ceil(a.size / 2) times. This loop may terminate earlier because it is possible for add to fail for lack of memory. So, the complexity is O(a.size).

(c)

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