//Konstantin Voevodski, Lab2 CAS CS112 Spring 2010

public class mySimpleLinkedList{
    private static class Node{
        public int data;
        public Node prev;
        public Node next;
        
        public Node(int d, Node p, Node n){
            data = d;
            prev = p;
            next = n;
        }
    }
    
    private int size;
    private Node beginMarker;
    private Node endMarker;
    
    public mySimpleLinkedList(){
        clear();
    }
    
    public void clear(){
        beginMarker = new Node(-1,null,null);
        endMarker = new Node(-1,beginMarker,null);
        //it is irrelevant what is stored in the data field of beginMarker and endMarker
        beginMarker.next = endMarker;
        size = 0;
    }
    
    public int size(){
        return size;
    }
    
    public boolean isEmpty(){
        return(size == 0);
    }
    
    private Node getNode(int idx){
    //return a Node at the specified position; positions are indexed starting at 0
        if(idx < 0 || idx > size())
        {
            throw new IndexOutOfBoundsException();
        }
        Node 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;
    }
	
	//fill in the two private "helper" methods below
	
	private void addBefore(Node p, int x){
    //add node containing x before p
    }
    
    private int remove(Node p){
    //remove node p from the list, return element that p contains
    }
    
    public boolean add(int x){
	//add element to the back of the list
        add(size(),x);
        return true;
    }
    
	//fill in the methods below, use the helper methods where appropriate
	
	
    public void add(int index, int x){
	//add element at specified position
    }
    
    public int get(int index){
	//get element at specified position
    }
    
    public int set(int index, int newVal){
	//set element at specified position to newVal, return old element
    }
    
    public int remove(int index){
	//remove and return element at specified position
    }
}