MyLinkedList.java

package Proj2;

import java.util.*;

public class MyLinkedList<AnyType> implements Iterable<AnyType>
{
    //1. nested Node class
    private static class Node<AnyType>
    {
        public Node(AnyType d, Node<AnyType> p, Node<AnyType> n)
        {data = d; prev = p; next = n;}

        public AnyType          data;
        public Node<AnyType>    prev;
        public Node<AnyType>    next;
    }//end of Node class

    //2. data fields and accessors
    private int theSize;
    private int modCount = 0;
    private Node<AnyType> beginMarker;
    private Node<AnyType> endMarker;

    public int size()
    {return theSize;}

    public boolean isEmpty()
    {return size() == 0;}

    //3. constructors
    public MyLinkedList()
    {clear();}

    //method clear: resets collection to 0
    public void clear()
    {
        beginMarker = new Node<AnyType>(null,null,null);
        endMarker = new Node<AnyType>(null,beginMarker,null);
        beginMarker.next = endMarker;

        theSize = 0;
        modCount++;
    }//end clear

    //4. more accessors and mutators
    public boolean add(AnyType x)
    {add(size(), x); return true;}

    public void add(int idx, AnyType x)
    {addBefore(getNode(idx), x);}

    public AnyType get(int idx)
    {return getNode(idx).data;}

    public AnyType set(int idx, AnyType newVal)
    {
        Node<AnyType> p = getNode(idx);
        AnyType oldVal = p.data;
        p.data = newVal;
        return oldVal;
    }

    public AnyType remove(int idx)
    {return remove(getNode(idx));}

    //5. getNode method
    private Node<AnyType> getNode(int idx)
    {
        Node<AnyType> p;
        if((idx<0)||(idx>size()))
        {throw new IndexOutOfBoundsException();}
        if(idx<(size()/2))
        {
            p = beginMarker.next;
            for(int i=0;i<idx;i++)
            {p = p.next;}
        }
        else
        {
            p = endMarker;
            for(int i=size();i>idx;i--)
            {p = p.prev;}
        }
        return p;
    }//end getNode method

    //6. addBefore method
    private void addBefore(Node<AnyType> p, AnyType x)
    {
        Node<AnyType> newNode = new Node<AnyType>(x, p.prev, p);
        newNode.prev.next = newNode;
        p.prev = newNode;
        theSize++;
        modCount++;
    }//end addBefore method

    //7. remove and iterator methods
    private AnyType remove( Node<AnyType> p)
    {
        p.next.prev = p.prev;
        p.prev.next = p.next;
        theSize--;
        modCount++;

        return p.data;
    }//end remove method

    //required by the Iterable interface
    public java.util.Iterator<AnyType> iterator()
    {return new LinkedListIterator<AnyType>();}

    //8. LinkedListIterator class
    private class LinkedListIterator<AnyType> implements Iterator<AnyType>
    {
        private Node<AnyType> current = (Node<AnyType>) beginMarker.next;

        //used to check for modifications to list
        private int expectedModCount = modCount;
        private boolean okToRemove = false;

        public boolean hasNext()
        {return current != endMarker;}

        public AnyType next()
        {
            System.out.println("modcount: "+modCount+" expectedModCount: "+expectedModCount);
            if(modCount != expectedModCount)
            {throw new ConcurrentModificationException();}

            if(!hasNext())
            {throw new NoSuchElementException();}

            AnyType nextItem = current.data;
            current = current.next;
            okToRemove = true;
            return nextItem;
        }//end of next method

        public void remove()
        {
            if(modCount != expectedModCount)
            {throw new ConcurrentModificationException();}
            if(!okToRemove)
            {throw new IllegalStateException();}
            MyLinkedList.this.remove(indexOf(current.prev));
            okToRemove = false;
            ++expectedModCount;
        }//end of remove method

        private int indexOf(Node<AnyType> x)
        {
            /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!warning!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
             * @self: likeliest source of OBOES.  Be sure to look here first if fit hits shan.
             */
            int idx = 0;
            Node<AnyType> searchCurrent = (Node<AnyType>) beginMarker;
            while((searchCurrent!= endMarker/*hasNext*/)&&(!searchCurrent.equals(x)))
            {idx++;searchCurrent = searchCurrent.next;}

            return idx;
        }//end of indexOf method
    }//end of LinkedListIterator class
}//end of MyLinkedList class