//a link list implementation
//Author: Konstantin Voevodski
//Date: 6/4/07

import java.util.*;

public class myLinkedList<AnyType> implements Iterable<AnyType>
{
    private static class Node<AnyType>
    {
        public AnyType data;
        public Node<AnyType> prev;
        public Node<AnyType> next;
        
        public Node(AnyType d, Node<AnyType> p, Node<AnyType> n)
        {
            data = d;
            prev = p;
            next = n;
        }
    }
    
    private int size;
    private int modCount = 0;
    private Node<AnyType> beginMarker;
    private Node<AnyType> endMarker;
    
    public myLinkedList()
    {
        clear();
    }
    
    public void clear()
    {
        beginMarker = new Node<AnyType>(null,null,null);
        endMarker = new Node<AnyType>(null,beginMarker,null);
        beginMarker.next = endMarker;
        size = 0;
        modCount++;
    }
    
    public int size()
    {
        return size;
    }
    
    public boolean isEmpty()
    {
        return(size == 0);
    }
    
    private void addBefore(Node<AnyType> p, AnyType x)
    //add new node before p, conceptually modifying four links
    {
        Node<AnyType> newNode = new Node<AnyType>(x,p.prev,p);
        newNode.prev.next = newNode;
        p.prev = newNode;
        size++;
        modCount++;
    }
    
    private AnyType remove(Node<AnyType> p)
    //remove node p, conceptually modifying two links
    {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        size--;
        modCount++;
        return p.data;
    }
    
    private Node<AnyType> getNode(int idx)
    //return a Node at the given index
    {
        if(idx < 0 || idx > size())
        {
            throw new IndexOutOfBoundsException();
        }
        Node<AnyType> p;
        if(idx < size()/2)
        //traverse list from the front
        {
            p = beginMarker.next;
            for(int i = 0; i < idx; i++)
            {
                p = p.next;
            }
        }
        else
        //traverse list from the back
        {
            p = endMarker;
            for(int i = size(); i > idx; i--)
            {
                p = p.prev;
            }
        }
        return p;
    }
    
    public boolean add(AnyType x)
    {
        add(size(),x);
        return true;
    }
    
    public void add(int index, AnyType x)
    {
        addBefore(getNode(index),x);
    }
    
    public AnyType get(int index)
    {
        return (getNode(index).data);
    }
    
    public AnyType set(int index, AnyType newVal)
    {
        Node<AnyType> p = getNode(index);
        AnyType oldVal = p.data;
        p.data = newVal;
        return oldVal;
    }
    
    public AnyType remove(int index)
    {
        return(remove(getNode(index)));
    }
    
    public Iterator<AnyType> iterator()
    {
        return new LinkedListIterator();
    }
    
    private class LinkedListIterator implements Iterator<AnyType>
    {
        private Node<AnyType> current = beginMarker.next;
        private int expectedModCount = modCount;
        private boolean okToRemove = false;
        
        public boolean hasNext()
        {
            return (current != endMarker);
        }
        
        public AnyType next()
        {
            if(modCount != expectedModCount)
            {
                throw new ConcurrentModificationException();
            }
            if(!hasNext())
            {
                throw new NoSuchElementException();
            }
            AnyType nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }
        
        public void remove()
        {
            if(modCount != expectedModCount)
            {
                throw new ConcurrentModificationException();
            }
            if(!okToRemove)
            {
                throw new IllegalStateException();
            }
            myLinkedList.this.remove(current.prev);
            okToRemove = false;
            //you can only remove the last element returned by the iterator
            //so another call to next is needed before removed can be called again
        }
    }
}