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

(a)

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

---

public class SplitCircularList
{
   /** split a into b and c */
   public static void split(CircularList a, CircularList b,
                            CircularList 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 codes and output are in the files SplitCircularList.*.