import org.jetbrains.annotations.NotNull;
import java.util.*;
import java.util.function.Consumer;

public class MyCollection<T> implements List<T> {

    transient private Node<T> first;  //  null <-[first] -> <- [last] -> null
    transient private Node<T> last;
    transient private int size = 0;

    public MyCollection() {
        first = new Node<>(null, null, last);
        last = new Node<>(null, first, null);
    }
    @Override
    public int size() {
        return size;
    }

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

    @Override
    public boolean contains(Object o) {
        if (o == null) {
            for (Node<T> target = first; target != null; target = target.next){
                if(target.item == null)
                    return true;
            }
        }
        else {
            for (Node<T> target = first; target != null; target = target.next) {
                if (o.equals(target.item)) {
                    return true;
                }
            }
        }
        return false;
    }

    @NotNull
    @Override
    public Iterator<T> iterator() {
        if (isEmpty()) {
            return Collections.<T>emptyList().iterator();
        }
        return new Iterator<>() {

            private Node<T> currentNode = null;

            @Override
            public boolean hasNext() {
                return currentNode != last;
            }

            @Override
            public T next() {
                if (currentNode == null) {
                    currentNode = first;
                    return currentNode.item;
                }
                if (currentNode.next == null) {
                    throw new NoSuchElementException();
                }
                currentNode = currentNode.next;
                return currentNode.item;
            }
        };
    }

    @Override
    public void forEach(Consumer<? super T> action) {

    }

    @NotNull
    @Override
    public Object[] toArray() {
        int a = 0;
        Object[] newArray = new Object[size];
        for (Node<T> target = first; target != null; target = target.next) {
            newArray[a++] = target.item;
        }
        return newArray;
    }

    @NotNull
    @Override
    public <R> R[] toArray(@NotNull R[] a) {
        int b = 0;
        Object[] newArray = a;
        for (Node<T> target = first; target != null; target = target.next) {
            newArray[b++] = target.item;
        }
        return a;
    }

    @Override
    public boolean add(T t) {
        if (t == null) {
            throw new IllegalArgumentException("Null");
        }

        Node<T> prev = last;
        prev.item = t;
        last = new Node<>(null, prev, null);
        prev.next = last;
        size++;
        return true;
    }

    @Override
    public boolean remove(Object o) {
        return false;
    }

    @Override
    public boolean containsAll(@NotNull Collection<?> c) {
        return false;
    }

    @Override
    public boolean addAll(@NotNull Collection<? extends T> c) {
        return false;
    }

    @Override
    public boolean addAll(int index, @NotNull Collection<? extends T> c) {
        return false;
    }

    @Override
    public boolean removeAll(@NotNull Collection<?> c) {
        return false;
    }

    @Override
    public boolean retainAll(@NotNull Collection<?> c) {
        return false;
    }

    @Override
    public void clear() {

    }

    @Override
    public T get(int index) {
        if (index < 0 || index > size) {
            return null;
        }
        Node<T> target = first;
        for (int i = 0; i < index; i++) {
            target = getNext(target);
        }
        return target.item;
    }

    private Node<T> getNext(Node<T> current) {
        return current.next;
    }

    @Override
    public T set(int index, T element) {
        return null;
    }

    @Override
    public void add(int index, T element) {
        if (get(index) == null) {
            throw new NoSuchElementException();
        }
        else if (index < 0 || index >= size) {
            throw new NullPointerException();
        }

    }

    @Override
    public T remove(int index) {
        return null;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private void checkIndex(int index) {
        if (!correctIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean correctIndex(int index) {
        return index >= 0 && index < size;
    }

    @Override
    public int indexOf(Object o) {
        return 0;
    }

    @Override
    public int lastIndexOf(Object o) {
        return 0;
    }

    @NotNull
    @Override
    public ListIterator<T> listIterator() {
        return null;
    }

    @NotNull
    @Override
    public ListIterator<T> listIterator(int index) {
        return null;
    }

    @NotNull
    @Override
    public List<T> subList(int fromIndex, int toIndex) {
        return null;
    }

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(E element, Node<E> prev, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }

    }

}