import java.util.*;      // innehåller gränssnittet List

public class MyLinkedList2 extends MyListAdapter implements List {

    private  Node header = new Node(null, null, null);
    private  int size = 0;
    private  int modCount = 0;

    private  class Node {
	Object element;
	Node next;
	Node previous;

	Node(Object element, Node next, Node previous) {
	    this.element = element;
	    this.next = next;
	    this.previous = previous;
	}
    }

    private Node addBefore(Object o, Node e) {
	Node newNode = new Node(o, e, e.previous);
	newNode.previous.next = newNode;
	newNode.next.previous = newNode;
	size++;
	modCount++;
	return newNode;
    }

    private Object remove(Node e) {
	if (e == header)
	    throw new NoSuchElementException();
        Object result = e.element;
	e.previous.next = e.next;
	e.next.previous = e.previous;
        e.next = e.previous = null;
        e.element = null;
	size--;
	modCount++;
        return result;
    }

    public MyLinkedList2() {
        header.next = header.previous = header;
    }


    public Object getFirst() {
	if (size==0)
	    throw new NoSuchElementException();
	return header.next.element;
    }


    public Object getLast()  {
	if (size==0)
	    throw new NoSuchElementException();
	return header.previous.element;
    }


    public Object removeFirst() {
	return remove(header.next);
    }


    public Object removeLast() {
	return remove(header.previous);
    }


    public void addFirst(Object o) {
	addBefore(o, header.next);
    }


    public void addLast(Object o) {
	addBefore(o, header);
    }


    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }


    public int size() {
	return size;
    }


    public boolean add(Object o) {
	addBefore(o, header);
        return true;
    }


    public boolean remove(Object o) {
        if (o==null) {
            for (Node e = header.next; e != header; e = e.next) {
                if (e.element==null) {
                    remove(e);
                    return true;
                }
            }
        } else {
            for (Node e = header.next; e != header; e = e.next) {
                if (o.equals(e.element)) {
                    remove(e);
                    return true;
                }
            }
        }
        return false;
    }


    public void clear() {
        Node e = header.next;
        while (e != header) {
            Node next = e.next;
            e.next = e.previous = null;
            e.element = null;
            e = next;
        }
        header.next = header.previous = header;
        size = 0;
	modCount++;
    }


    // Positional Access Operations


    public Object get(int index) {
        return entry(index).element;
    }


    public Object set(int index, Object element) {
        Node e = entry(index);
        Object oldVal = e.element;
        e.element = element;
        return oldVal;
    }


    public void add(int index, Object element) {
        addBefore(element, (index==size ? header : entry(index)));
    }


    public Object remove(int index) {
        return remove(entry(index));
    }


    private Node entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+size);
        Node e = header;
        if (index < (size >> 1)) {
            for (int i = 0; i <= index; i++)
                e = e.next;
        } else {
            for (int i = size; i > index; i--)
                e = e.previous;
        }
        return e;
    }


    // Search Operations


    public int indexOf(Object o) {
        int index = 0;
        if (o==null) {
            for (Node e = header.next; e != header; e = e.next) {
                if (e.element==null)
                    return index;
                index++;
            }
        } else {
            for (Node e = header.next; e != header; e = e.next) {
                if (o.equals(e.element))
                    return index;
                index++;
            }
        }
        return -1;
    }


    public int lastIndexOf(Object o) {
        int index = size;
        if (o==null) {
            for (Node e = header.previous; e != header; e = e.previous) {
                index--;
                if (e.element==null)
                    return index;
            }
        } else {
            for (Node e = header.previous; e != header; e = e.previous) {
                index--;
                if (o.equals(e.element))
                    return index;
            }
        }
        return -1;
    }


    public ListIterator listIterator(int index) {
	return new ListItr(index);
    }

    public Iterator iterator() {
	return new ListItr(0);
    }

    private class ListItr implements ListIterator {
	private Node lastReturned = header;
	private Node next;
	private int nextIndex;
	private int expectedModCount = modCount;

	ListItr(int index) {
	    if (index < 0 || index > size)
		throw new IndexOutOfBoundsException("Index: "+index+
						    ", Size: "+size);
	    if (index < (size >> 1)) {
		next = header.next;
		for (nextIndex=0; nextIndex<index; nextIndex++)
		    next = next.next;
	    } else {
		next = header;
		for (nextIndex=size; nextIndex>index; nextIndex--)
		    next = next.previous;
	    }
	}

	public boolean hasNext() {
	    return nextIndex != size;
	}

	public Object next() {
	    checkForComodification();
	    if (nextIndex == size)
		throw new NoSuchElementException();
	    lastReturned = next;
	    next = next.next;
	    nextIndex++;
	    return lastReturned.element;
	}

	public boolean hasPrevious() {
	    return nextIndex != 0;
	}

	public Object previous() {
	    if (nextIndex == 0)
		throw new NoSuchElementException();

	    lastReturned = next = next.previous;
	    nextIndex--;
	    checkForComodification();
	    return lastReturned.element;
	}

	public int nextIndex() {
	    return nextIndex;
	}

	public int previousIndex() {
	    return nextIndex-1;
	}

	public void remove() {
            checkForComodification();
            Node lastNext = lastReturned.next;
            try {
                MyLinkedList2.this.remove(lastReturned);
            } catch (NoSuchElementException e) {
                throw new IllegalStateException();
            }
	    if (next==lastReturned)
                next = lastNext;
            else
		nextIndex--;
	    lastReturned = header;
	    expectedModCount++;
	}

	public void set(Object o) {
	    if (lastReturned == header)
		throw new IllegalStateException();
	    checkForComodification();
	    lastReturned.element = o;
	}

	public void add(Object o) {
	    checkForComodification();
	    lastReturned = header;
	    addBefore(o, next);
	    nextIndex++;
	    expectedModCount++;
	}

	final void checkForComodification() {
	    if (modCount != expectedModCount)
		throw new ConcurrentModificationException();
	}
    }



}