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

(a)

The code to split a doubly linked list is given below. It is obtained from the code for Exercise 17 by replacing all occurrences of ExtendedChain by DoublyLinkedList

public class SplitDoublyLinkedList
{
   /** split a into b and c */
   public static void split(DoublyLinkedList a, DoublyLinkedList b,
                            DoublyLinkedList 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 SplitDoublyLinkedList.*.

(d)

The code is given below.

public class DoublyLinkedListWithSplit extends DoublyLinkedList
{
   /** split this into lists a and b,
     * this becomes empty following the split */
   public void split(DoublyLinkedListWithSplit a,
                     DoublyLinkedListWithSplit b)
   {
      // handle this.size < 2 as special cases
      if (size < 2)
      {
         if (size == 0)
         {// both a and b are empty
            a.clear();
            b.clear();
            return;
         }

         // size = 1
         // a gets the element, this and b become empty
         a.firstNode = a.lastNode = firstNode;
         a.size = 1;
         clear();
         b.clear();
         return;
      }

      // length is >= 2, assign a and b their first nodes
      a.firstNode = firstNode;
      a.lastNode = a.firstNode;
      b.firstNode = firstNode.next;
      b.lastNode = b.firstNode;
      b.firstNode.previous = null;
   
      // assign remaining nodes
      DoubleNode ct = b.firstNode.next;   // cursor for this
      while (ct != null)
      {
         // first give a node to a
         a.lastNode.next = ct;
         ct.previous = a.lastNode;
         a.lastNode = ct;
         ct = ct.next;
         if (ct == null)
            break;

         // now give a node to b
         b.lastNode.next = ct;
         ct.previous = b.lastNode;
         b.lastNode = ct;
         ct = ct.next;
      }
   
      // set null pointers in last nodes
      a.lastNode.next = b.lastNode.next = null;

      // set size values for a and b
      b.size = size / 2;
      a.size = size - b.size;
   
      // this is now empty
      clear();
   
      return;
   }
}

(e)

The while loop iterates ceil(size/2) times. So, the complexity is O(size).

(f)

A test program and output appear in the files DoublyLinkedListWithSplit.*.