import java.util.Iterator;

public class LenkeListe<T extends Comparable<T>> implements Iterable<T> {

    Node start;
    int stoerrelse;

    public Iterator<T> iterator() {
        return new LenkeListeIterator();
    }

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

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

        public T next() {
            T data = denne.innhold;
            denne = denne.neste;
            return data;
        }
    }

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

        private Node(T innhold) {
            this.innhold = innhold;
        }
    }

    public void leggTil(T innhold) {
        stoerrelse++;
        if (start == null) {
            start = new Node(innhold);
        } else {
            Node p = start;
            while (p.neste != null) {
                p = p.neste;
            }
            p.neste = new Node(innhold);
            p.neste.forrige = p;
        }

    }

    public void leggTilSortert(T innhold) {
        stoerrelse++;
        if (start == null) {
            leggTil(innhold);
        } else {
            Node p = start;
            while (p.innhold.compareTo(innhold) < 0) {
                if (p.neste != null) {
                    p = p.neste;
                } else {
                    p.neste = new Node(innhold);
                    p.neste.forrige = p;
                    return;
                }
            }
            Node ny = new Node(innhold);
            if (p == start) {
                ny.neste = start;
                start.forrige = ny;
                return;
            } 
            ny.neste = p;
            ny.forrige = p.forrige;
            ny.forrige.neste = ny;
            ny.neste.forrige = ny;
            
        }
    }

    public T hent(int pos) {
        sjekkGyldigPos(pos);
        Node p = start;
        int teller = 0;
        while (teller != pos && p.neste != null) {
            p = p.neste;
            teller++;
        }
        return p.innhold;
    }

    public T fjern(int pos) {
        sjekkGyldigPos(pos);
        Node p = start;
        int teller = 0;
        while (teller != pos && p.neste != null) {
            p = p.neste;
            teller++;
        }
        if (p == start) {
            T innhold = start.innhold;
            start = start.neste;
            return innhold;
        } else if (pos == stoerrelse - 1) {
            T innhold = p.innhold;
            p.forrige.neste = null;
            return innhold;
        }
        T innhold = p.innhold;
        p.forrige.neste = p.neste;
        p.neste.forrige = p.forrige;
        stoerrelse--;
        return innhold;

    }

    public void sjekkGyldigPos(int pos) {
        if (pos < 0 || pos >= stoerrelse) {
            System.out.println("UGYLDIG LISTEINDEKS");
            System.exit(1);
        }
    }

    public int stoerrelse() {
        return stoerrelse;
    }

    @Override
    public String toString() {
        String s = "";
        if (start != null) {
            Node p = start;
            s += p.innhold + " | ";
            while (p.neste != null) {
                p = p.neste;
                s += p.innhold + " | ";
            }
        }
        return s;
    }
}