import java.util.Iterator;

public class Lenkeliste<T extends Comparable<T>> implements Iterable<T> {
    private int stoerrelse;
    private Node start, slutt;

    private class Node {
        public T innhold;
        public Node neste, forrige;

        public Node(T innhold) {
            this.innhold = innhold;
        }
        public int compareTo(Node other) {
            return innhold.compareTo(other.innhold);
        }
    }
    
    private class LenkeIterator implements Iterator<T> {
        Node gjeldende;

        public LenkeIterator() {
            gjeldende = start;
        }

        @Override
        public boolean hasNext() {
            return gjeldende != slutt.forrige;
        }
        @Override
        public T next() {
            gjeldende = gjeldende.neste;
            return gjeldende.innhold;
        }
    }

    public Lenkeliste() {
        stoerrelse = 0;
        start = new Node(null);
        slutt = new Node(null);
        start.neste = slutt;
        slutt.forrige = start;
    }
    
    public void leggTil(T x) {
        Node ny = new Node(x);
        ny.forrige  = slutt.forrige;
        ny.forrige.neste = ny;
        ny.neste = slutt;
        slutt.forrige = ny;

        stoerrelse++;
    }
    
    
    public void leggTil(T x, int pos) {
        if (pos > stoerrelse && pos < 0) {
            System.out.println("Feil i index");
            return;
        }
        Node ny = new Node(x);
        Node foran = start;
        for (int n=0; n < pos; n++) {
            foran = foran.neste;
        }
        ny.neste = foran.neste;
        ny.neste.forrige = ny;
        ny.forrige = foran;
        foran.neste = ny;
        stoerrelse++;

    }
    
    public void skrivUtFremover() {
        Node n = start.neste;
        while (n.innhold != null) {
            System.out.println(n.innhold);
            n = n.neste;
        }
    }
    
    public void skrivUtBakover() {
        Node n = slutt.forrige;
        while (n.innhold != null) {
            System.out.println(n.innhold);
            n = n.forrige;
        }
    }
    public T hentMinste() {
        Node minst = start.neste;
        Node iter = minst;
        for (int n = 0; n < stoerrelse - 1; n++) {
            iter = iter.neste;
            if (iter.compareTo(minst) < 0) {
                minst = iter;
            }
        }
        return minst.innhold;
    }
    public Iterator<T> iterator() {
        return new LenkeIterator();
    }
}