// Dobbellenket liste, med en peker til f?rste objekt

public class SparegrisGenerisk<E> {
    private int antall = 0;
    private Seddel foerst = null;

    private class Seddel {
        Seddel neste, forrige = null;
        private E verdi;

        public Seddel(E v) {
            verdi = v;
        }

        public E hentVerdi() {
            return verdi;
        }
    }

    public int hentAntall() {
        return antall;
    }

    // Legger til f?rst i lenkelista
    public void leggTilFoerst(E verdi) {
        Seddel ny = new Seddel(verdi);

        // Invariant: Lenkelista er tom
        if (antall == 0) {
            foerst = ny;
            antall++;
            return;
        }

        // Invariant: Lenkelista er ikke tom

        foerst.forrige = ny;
        ny.neste = foerst;
        foerst = ny;

        antall++;
    }

    public void leggTilSist(E verdi) {
        Seddel ny = new Seddel(verdi);

        // Invariant: Lenkelista er tom
        if (antall == 0) {
            foerst = ny;
            antall++;
            return;
        }

        // Invariant: Lenkelista er ikke tom
        Seddel peker = foerst;

        while (peker.neste != null) {
            peker = peker.neste;
        }

        peker.neste = ny;
        ny.forrige = peker;

        antall++;
    }

    public E fjernFoerst() {
        // IV: Lenkelista er tom

        if (antall == 0) {
            System.out.println("Ingen sedler");
            return null;
        }


        // IV: Lenkelista har ett element
        if (antall == 1) {
            Seddel midlertidig = foerst;
            foerst = null;
            antall--;
            return midlertidig.hentVerdi();
        }

        // IV: Ellers

        E verdi = foerst.hentVerdi();
        foerst = foerst.neste;
        foerst.forrige = null;
        antall--;
        return verdi;
    }

    public E fjernSist() {

        // IV: Lenkelista er tom
        if (antall == 0) {
            System.out.println("Ingen sedler");
            return null;
        }


        // IV: Lenkelista har ett element
        if (antall == 1) {
            Seddel midlertidig = foerst;
            foerst = null;
            antall--;
            return midlertidig.hentVerdi();
        }
        
        Seddel peker = foerst;

        while (peker.neste != null) {
            peker = peker.neste;
        }

        E verdi = peker.hentVerdi();
        peker = peker.forrige;
        peker.neste = null;
        antall--;
        return verdi;
    }

    public E hentFoerst() {
        if (foerst != null) {
            return foerst.hentVerdi();
        }

        return null;
    }

    public E hentSist() {
        if (foerst == null) {
            return null;
        }

        if (antall == 1) {
            return foerst.hentVerdi();
        }

        Seddel peker = foerst;

        while (peker.neste != null) {
            peker = peker.neste;
        }

        return peker.hentVerdi();
    }

    @Override
    public String toString() {
        Seddel peker = foerst;
        String sum = "";

        while (peker != null) {
            sum += peker.hentVerdi();
            peker = peker.neste;
        }

        return "Sum: " + sum;
    }
}