import java.util.Iterator;
import java.util.NoSuchElementException;


public class Lenkeliste<T extends Comparable<T>> implements Iterable<T>{
    Node start;
    Node slutt;

    private class Node {
        Node neste;
        T data;
        Node(T data){
            this.data = data;
        }
    }

    private class NodeIterator implements Iterator<T> {
        Node denne = start;

        @Override
        public boolean hasNext() {
            return denne != null;
        }

        @Override
        public T next() {
            if (denne == null) throw new NoSuchElementException();
            Node temp = denne;
            denne = denne.neste;
            return temp.data;
        }

    }

    /**
     * Remove and return first element
     * @return content of first node 
     */

    public T pop() { 
        Node skalReturneres = start;
        if (skalReturneres == null) return null;
        
        start = start.neste;
        if (start == null) slutt = null;

        return skalReturneres.data;
    }

    public void add(T nyData) {
        if (start == null) {
            start = new Node(nyData);
            slutt = start;
        } else {
            slutt.neste = new Node(nyData);
            slutt = slutt.neste; 
        }
    }

    // DISCLAIMER: sorted laget på 2 min, ikke testet.

    // public void addSorted(T ting){
    //     Node ny = new Node(ting);
    //     Node denne = start;
    //     Node forrige = null;

    //     while(denne.data.compareTo(ting) < 0){
    //         forrige = denne;
    //         denne = denne.neste;
    //     }

    //     ny.neste = denne;
    //     forrige.neste = ny;
    // }

    public T get(int index) throws IndexOutOfBoundsException {
        Node skalReturneres = start;

        for (int i = 0; i < index; i++) {
            if(skalReturneres == null) throw new IndexOutOfBoundsException();
            skalReturneres = skalReturneres.neste;
            if(skalReturneres == null) throw new IndexOutOfBoundsException();
        }
    
        return skalReturneres.data;
    }

    @Override
    public NodeIterator iterator() {
        return new NodeIterator();
    }
}