import java.util.NoSuchElementException;

public class AbbreviatedLinkedList
{
    private Node first;

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

    /**
     * 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;
    }
    
    /**
     * Iteratively reverse the list.
     * @throws NoSuchElementException if the list is empty.
     */
    public void reverse()
    {
        if (first == null) {
            throw new NoSuchElementException();
        }
        
        Node p1 = first;
        Node p2 = p1.next;
        
        // Loop to reverse the links.
        while (p2 != null) {
            Node p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
        }
        
        first.next = null;  // old first is now the list end
        first = p1;         // set first to head of reversed list
    }
    
    /**
     * Return the linked list as a string.
     */
    public String toString()
    {
        StringBuilder str = new StringBuilder("[");
        Node p = first;
        
        while (p != null) {
            str.append(p.data);
            p = p.next;
            if (p != null) str.append(" ");
        }
        
        str.append("]");
        return str.toString();
    }

    class Node
    {
        public Object data;
        public Node next;
    }
    
    public static void main(String[] args)
    {
        AbbreviatedLinkedList list = new AbbreviatedLinkedList();
        list.addFirst("D");
        list.addFirst("C");
        list.addFirst("B");
        list.addFirst("A");

        System.out.println("       Original list: " + list);
        list.reverse();
        System.out.println("Iteratively reversed: " + list);
    }
}