/**
 *  Manipulates a list using java.util.LinkedList (or java.utilArrayList) class
 *  and iterators.
 */
import java.util.LinkedList;
import java.util.Iterator;
import java.util.ListIterator;

public class LinkedListUsingJavaUtil
{
	/**
	 *  Creates and returns a list containing three nodes 
	 *  with the values from String[] values.
	 */
	public static LinkedList createOriginalList(String[] values)
	{
		LinkedList list = new LinkedList();
	
		for(int k=0; k < values.length; k++) 
		{	// add each to end
			list.add(values[k]);
		}
		return list;
	}
	/**
	 *  Doubles the number of nodes in list
	 *  After each node with the value "X" inserts a new node with the value "X*".
	 *  Returns the modified list
	 *  For example, if the original list is "A", "B", "C", then the modified
	 *  list contains "A", "A*", "B", "B*", "C", "C*"
	 */
	public static LinkedList doubleList(LinkedList list)
	{
		ListIterator iter = list.listIterator();
	
		while (iter.hasNext())
		{
			String s = (String) iter.next() + "*";  // cast is optional
			iter.add(s);
		}
		return list;
	} 
  
	/**
	 *  Displays the list with consecutive values separated by a space
	 */ 
	public static void displayList(LinkedList list)
	{
		Iterator iter = list.iterator();
		
		System.out.print("( ");
		while (iter.hasNext())
			System.out.print(iter.next() + " ");
		
		System.out.println(")");
	}
  
	/**
	 *  Displays the list IN REVERSE
	 *   (NOT in the AP subset)
	 */ 
	public static void displayListInReverse(LinkedList list)
	{
		// displays values starting at the end of the list 
		ListIterator iter = list.listIterator(list.size());

		System.out.print("( ");
		while (iter.hasPrevious())
			System.out.print(iter.previous() + " ");
		System.out.println(")");
	}
	
	/**
     * Remove duplicate values from a sorted list.
     */
	public static void removeDupes(LinkedList list)
	{
		// your turn!
	}

	public static void main(String[] args)
	{
		String[] values = { "A", "A", "B", "C", "C", "D" };
		
		LinkedList list = createOriginalList(values);

		System.out.println("\nOriginal List: ");
		displayList(list);
	
		list = doubleList(list);
	
		System.out.println("\nModified List:");
		displayList(list);
	
		System.out.println("\nModified List IN REVERSE:");
		displayListInReverse(list);
		
		removeDupes(list);
		
		System.out.println("\nList with duplicates removed:");
		displayList(list);		

		System.out.println();
	}	
}
