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

(a)

A doubly linked circular list with header node may be reversed by swapping the two pointers in each node (this is equivalent to changing pointer directions). The code for the member method to reverse a doubly linked circular list is given below.

public class HeadDoubleCircularListWithReverse
             extends HeadDoubleCircularList
{
   /** in-place reversal of a doubly linked circular list */
   public void reverse()
   {
      // swap pointers in each node
      DoubleNode currentNode = headerNode.next;
      while (currentNode != headerNode)
      {
         // change pointer directions
         DoubleNode nextNode = currentNode.next;
         currentNode.next = currentNode.previous;
         currentNode.previous = nextNode;
   
         // move to next node
         currentNode = nextNode;
      }
      
      // change pointer directions in header node
      DoubleNode nextNode = headerNode.next;
      headerNode.next = headerNode.previous;
      headerNode.previous = nextNode;
   }
}

(b)

The complexity is linear in the length of the list.

(c)

A sample code to test this method is given in the file HeadDoubleCircularListWithReverse.java and the output is given in the file HeadDoubleCircularListWithReverse.output.

An alternative is to use the strategy employed in Exercise 5.18--swap elements from the two ends of the list. This strategy works well in Java because the items being swapped are actually 4-byte references. In languages such as C and C++ this strategy may swap large elements and, hence, be quite a bit more time consuming than swapping pointers as is done above. The code to reverse by swapping elements is given below.

---

public class HeadDoubleCircularListWithReverse2
             extends HeadDoubleCircularList
{
   /** in-place reversal of a doubly linked circular list */
   public void reverse()
   {
      int numberToSwap = size / 2;

      // swap numberToSwap pairs of elements
      DoubleNode leftSwapNode = headerNode.next;
      DoubleNode rightSwapNode = headerNode.previous;
      for (int i = 0; i < numberToSwap; i++)
      {
         // swap a pair
         Object temp = leftSwapNode.element;
         leftSwapNode.element = rightSwapNode.element;
         rightSwapNode.element = temp;
   
         // move to next pair
         leftSwapNode = leftSwapNode.next;
         rightSwapNode = rightSwapNode.previous;
      }
   }

(d)

The nonmember code, given below, is identical to the nonmember reversal codes for the other list classes.

---

public class ReverseHeadDoubleCircularList
{
   public static void reverse(HeadDoubleCircularList 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);
      }
   }
}

---

(e)

The complexity is O(size2) because each remove takes O(1) time and each add takes O(size) time.

(f)

The above code together with sample test program is in the file ReverseHeadDoubleCircularList.java.