import java.util.*;

public class LinkedList {
    private class Node {
        private String data;
        private Node link;

        public Node(String newData, Node newLink) {
            data = newData;
            link = newLink;
        }
    }

    private Node head;

    public LinkedList() {
        head = null;
    }

    public void clear() {
        head = null;
    }

    public int indexOf(String item) {
        Node position = head;
        int count = 0;
        while (position != null) {
            if (item.equals(position.data)) {
                return count;
            }
            count++;
            position = position.link;
        }
        throw new NoSuchElementException();
    }

    public String get(int index) {
        Node position = head;
        int count = 0;
        while (position != null && count < index) {
            count++;
            position = position.link;
        }
        if (count != index) {
            throw new NoSuchElementException();
        }
        return position.data;
    }

    public void showList() {
        Node position = head;
        while (position != null) {
            System.out.println(position.data);
            position = position.link;
        }
    }

    public void addToStart(String newData) {
        head = new Node(newData, head);
    }

    public void removeFromStart() {
        if (head == null) {
            throw new IllegalStateException();
        } else {
            head = head.link;
        }
    }

    public class ListIter implements Iterator {
        private Node position;
        private Node previous;

        ListIter() {
            position = head;
            previous = null;
        }

        public boolean hasNext() {
            return position != null;
        }

        public String next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            String value = position.data;
            previous = position;
            position = position.link;
            return value;
        }

        public void remove() {
            if (position == null) { // no nodes
                throw new IllegalStateException();
            } else if (previous == null) { // at head
                head = head.link;
                position = head;
            } else { // usual case
                previous.link = position.link;
                position = position.link;
            }
        }

        public void add(String newData) {
            if (position == null && previous != null) {
                // at end of list
                previous.link = new Node(newData, null);
            } else if (position == null || previous == null) {
                // list is empty or position is at head node
                addToStart(newData);
            } else {
                // usual case: previous and position are
                // consecutive nodes
                Node temp = new Node(newData, position);
                previous.link = temp;
                previous = temp;
            }
        }
    }

    ListIter iterator() {
        return new ListIter();
    }
}