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

(a)

The nonmember method to reverse a circular list is given below.

---

public class ReverseCircularList
{
   public static void reverse(CircularList x)
   {
      int sizeMinus1 = x.size() - 1;
      for (int i = 0; i < sizeMinus1; i++)
      {
         // retrieve and remove first element
         Object y = x.remove(0);

         // insert at proper place
         x.add(sizeMinus1 - i, y);
      }
   }
}

---

(b)

Each invocation of remove takes O(1) time, and each invocation add(sizeMinus1 - i, y) takes O(sizeMinus1 - i) time. Therefore, each iteration of the for loop takes O(sizeMinus1 - i) time. The overall complexity is O( (sum from i = 0 to sizeMinus1 - 1) (sizeMinus1 - i) = O(size2).

(c)

The test program and output appear in the files ReverseCircularList.*.