Data Structures, Algorithms, & Applications in Java
Chapter 5, Exercise 29

(a)

The method dataStructures.ArrayCircularListWithReverse, which reverses a list represented using Equation 3.3, is given below.

/** reverse the linear list */
public void reverse()
{
   int size = size();
   for (int i = 0; i < size / 2; i++)
       MyMath.swap(element, (first + i) % element.length,
                  (element.length + last - i) % element.length);
}

(b)

The complexity of the method is Theta(size).

(c)

A sample test program is given as the mathod ArrayCircularListWithReverse.main. For completeness, we could also test using an empty list and one of length one.

(d)

The code is given below.

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

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

(e)

Each invocation of remove takes Theta(1) time (as the element is removed from the right end of the list). The complexity of add(y, i) is Theta(min{i, size - i}). So, the time needed to perform all the inserts is Theta(size2). This is also the overall complexity of the method reverse.