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