public class SortertLenkeliste<T extends Comparable<T>> {

    Node start;
    Node slutt;

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

        public Node(T x) {
            innhold = x;
        }
    }

    public void settInn(T x) {
        Node ny = new Node(x);
        if (erTom()) {
            start = new Node(x);
        } else if (x.compareTo(start.innhold) < 0) {
            ny.neste = start;
            start.forrige = ny;
            start = ny;
        } else {
            Node p = start;
            while (p.neste != null) {
                if (x.compareTo(p.neste.innhold) >= 0) {
                    p = p.neste;
                } else {
                    ny.neste = p.neste;
                    p.neste = ny;
                    ny.forrige = p;
                    ny.neste.forrige = ny;
                    return;
                }
            }
            if (x.compareTo(p.innhold) >= 0) {
                p.neste = ny;
                ny.forrige = p;
            } else {
                ny.neste = p;
                p.forrige = ny;
            }

        }
    }

    public int stoerrelse() {
        int i = 0;

        Node p = start;

        while (p.neste != null) {
            p = p.neste;
            i++;
        }
        i++;
        return i;
    }

    // public T hent(int pos) {
    //
    // }
    //
    // public T pop(int pos) {
    //
    // }

    public boolean erTom() {
        return start == null;
    }

    public void skrivUtAldere() {
        Node p = start;
        while (p.neste != null) {
            System.out.println(p.innhold);
            p = p.neste;
        }
        System.out.print(p.innhold);
    }
}