public class LenkeListe<T extends Comparable<T>>{
    private ListeHode lHode; // listehodet
    private ListeHale lHale; // listehalen
    private int antall; // antall objekter i lista
    LenkeListe() {
        antall = 0;
        lHode = new ListeHode(null);
        lHale = new ListeHale(null, lHode);
        lHode.neste = lHale;

    }

    private interface Elem {
        int compareTo (Elem k) ;
        void settInnOrdnet (Elem k);
    }

    private abstract class AbstrNode {
        T obj ;
        AbstrNode neste;
        AbstrNode(T t) {
            obj = t;
            neste = null;
        }
        abstract int compareTo (AbstrNode k);
        abstract void settInnOrdnet (AbstrNode k);
    }

    private class ListeHode extends AbstrNode { 
        ListeHode(T t){
            super(t);
        }
        int compareTo(AbstrNode node) {
            return -9;
        }
        void settInnOrdnet (AbstrNode ny) {
            if (neste.compareTo(ny) >= 0) {
                ny.neste = neste;
                neste = ny;
                if (ny.neste = lHale) {
                    lHale.forrige = ny;
                }
                antall++;
            }
            else {
                neste.settInnOrdnet(ny);
            }
        }
    }

    private class ListeHale extends AbstrNode { 
        AbstrNode forrige;
        ListeHale(T t, AbstrNode lhode){
            super(t);
            forrige = hode;
        }
        int compareTo(AbstrNode node) {
            return 9;
        }
        void settInnOrdnet (AbstrNode k) {
            System.out.println("LISTEHALE");
        }
    }

    private class Node extends AbstrNode {
        
        Node (T t) { // t peker til objekt av type Comparable<T>
            super(t);
        }
        int compareTo (AbstrNode k) {
            return obj.compareTo (k.obj);
        }
        void settInnOrdnet (AbstrNode ny) {
            if (neste.compareTo(ny) < 0) {
                neste.settInnOrdnet(ny);
            }
            else {
                ny.neste = neste;
                neste = ny;
                if (ny.neste == lHale) {
                    lHale.forrige = ny;
                }
                antall++;
            }
        }

        
    }

    public int antall () {
        return antall;
    }

    // denne metoden skal ikke endres
    public void settInnOrdnet (T nyComparable){
        Node nyNode = new Node ( nyComparable ) ;
        lhode.settInnOrdnet(nyNode);
    }

    public void settInnBak (T nyComparable) {
        Node nyNode = new Node (nyComparable);
        lHale.forrige.neste = nyNode;
        lHale.forrige = nyNode;
        nyNode.neste = lHale;
        antall++;
    }

    public AbstrNode taUtForan() throws Exception { 
        if (antall > 0) {
            AbstrNode ut = lhode.neste;
            lhode.neste = ut.neste;
            antall--;
            return ut.obj;
        }
        else {
            throw new Exception ("Kall på taUtForan i tom Liste");
        }
        
        
    }

    public boolean tom () { 
        return antall == 0;
    }
}