class Prioritetskoe<E extends Comparable<E>> {
    // Dette er bare en gjennomgan av prioritetskøen. Dette er ganske likt som det dere gjorde i oblig3.
    // Dette var mest for å illusterer at vi kan bruke et interface til å begrense hvilke elementer vi kan sette inn i 
    // beholderen. 

    Node foerste = null;
    class Node {
        E data;
        Node neste;
        public Node(E x) {
            data = x;
        }
    }

    public void settInn(E x) {
        // Fra tegningen min fant jeg tre tilfeller jeg må ta hensyn til når jeg skal sette inn nye elementer. 
        
        // 1. Når lista er tom:
        if (foerste == null) {
            foerste = new Node(x);
            return;
        }

        Node nyNode = new Node(x);
        
        // 2. Når det nye elementet er mindre enn det første elementet i lista:
    
        if (x.compareTo(foerste.data) <= 0) {
            // x.compareTo(y) -> returnerer typisk (x - y)
            nyNode.neste = foerste;
            foerste = nyNode;
            return;
        }

        // 3. Når noden må plasseres en eller annen plass inne i lista (kan være sist). 
        Node neste = foerste;
        Node forrige = null;

        // Finner den første noden hvor x < neste.data, eller den siste node. 
        while (x.compareTo(neste.data) > 0 && neste != null) {
            forrige = neste;
            neste = neste.neste;
        }
        // Siden neste nå enten peker på null, eller på en node som er større enn x, trenger jeg å mellomlagre noden som kom før,
        // siden den nye noden må plasseres mellom forrige og neste pekerene.
        forrige.neste = nyNode;
        // Siden jeg alltid skal plassere noden etter forrige, er det uvesentlig om neste peker på null, så jeg kan trygt sette
        // nyNode sin neste til å peke på den.
        nyNode.neste = neste;
    }
}