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

The code for fromList is 
/** convert f into its chain representation */
public void fromList(ArrayLinearList f)
{
   // first make this empty
   firstNode = null;
   ChainNode lastNode = null;
   
   // copy elements from f
   int len = f.size();
   for (int i = 0; i < len; i++)
   {
      // create a node for the next element
      ChainNode node = new ChainNode(f.get(i));

      // put this node into the chain
      if (firstNode == null)  // chain is empty
         firstNode = node;
      else // chain is not empty
         lastNode.next = node;

      lastNode = node;
   }

   // set next field of last node
   if (lastNode != null)
      lastNode.next = null;
}


Each iteration of the for loop takes Theta(1) time. The loop is iterated O(f.size) time (note that fewer than f.size iterations may be made if we do not have adequate memory to create the needed nodes). Therefore, the overall complexity of fromList is O(f.size).

The code for toList is 
/** convert this into its array-based representation f */
public void toList(ArrayLinearList f)
{
   // first make f empty
   int len = f.size() - 1;
   for (int i = len; i >= 0; i--)
      f.remove(i);

   // copy from this
   ChainNode current = firstNode;
   int i = 0;       // index of current element
   while (current != null)
   {// copy current element
      f.add(i, current.element);
      current = current.next;  // move to next node
      i++;
   }
}
Each iteration of the for loop and each iteration of the while loop takes Theta(1) time. The overall complexity is, therefore, O(f.size + this.size), where f.size is the size of f at the time toList is invoked.

Sample test data and output can be found in the files dataStructures.ChainWithConvert.*.