import java.util.NoSuchElementException;

/**
 * A linked list is a sequence of nodes with efficient element insertion and
 * removal. This class contains a subset of the methods of the standard
 * java.util.LinkedList class.
 */
public class LinkedListNoIterator
{
    public Node first;

    /**
     * Constructs an empty linked list.
     */
    public LinkedListNoIterator()
    {
        first = null;
    }

    /**
     * Removes the first element in the linked list.
     * 
     * @return the removed element
     */
    public Object removeFirst()
    {
        if (first == null) {
            throw new NoSuchElementException();
        }
        Object element = first.data;
        first = first.next;
        return element;
    }

    /**
     * Adds an element to the front of the linked list.
     * 
     * @param element the element to add
     */
    public void addFirst(Object element)
    {
        Node newNode = new Node();
        newNode.data = element;
        newNode.next = first;
        first = newNode;
    }

    public static class Node
    {
        public Object data;
        public Node next;
    }
    
    private static void add(LinkedListNoIterator list, Object elmts[])
    {
        for (int i = elmts.length-1; i >= 0; i--) list.addFirst(elmts[i]);
    }
    
    private static void print(LinkedListNoIterator list)
    {
        System.out.print("List: ");
        for (Node p = list.first; p != null; p = p.next) {
            System.out.print(p.data + " ");
        }
        System.out.println();
    }
    
    private static Node getPrevious(LinkedListNoIterator list, Object elmt)
    {
        for (Node p = list.first; p.next != null; p = p.next) {
            if (elmt.equals(p.next.data)) return p;
        }
        
        return null;
    }

    public static void main(String[] args)
    {
        LinkedListNoIterator list = new LinkedListNoIterator();
        add(list, new String[] {"C", "S", "4", "6", "B"});
        
        double values[] = new double[20];
        LinkedListNoIterator lists[] = new LinkedListNoIterator[100];
        
        values[14] = Math.PI;
        lists[42] = new LinkedListNoIterator();
        
        print(list);
        
        System.out.println("\nRemove B");
        Node prev = getPrevious(list, "B");
        prev.next = prev.next.next;
        print(list);
        
        System.out.println("\nAdd 1");
        prev = getPrevious(list, "4");
        Node one = new Node();
        one.data = "1";
        one.next = prev.next;
        prev.next = one;
        print(list);
    }
}