import java.util.Iterator;

public class AListe <K, V> implements Iterable<K> {

    protected Node forste = null, siste = null;
    protected int storrelse = 0;

    protected class Node {
        protected K nokkel = null;
        protected V verdi = null;
        protected Node neste, forrige;

        public Node(K nokkel, V verdi) {
            this.nokkel = nokkel;
            this.verdi = verdi;
        }
    }

    public int hentStorrelse() {
        return storrelse;
    }

    public void leggTil(K nokkel, V verdi) { // legger til på slutten av lista
        Node ny = new Node(nokkel, verdi);

        if (hentStorrelse() == 0) {
            forste = siste = ny;
            storrelse++;
            return;
        }

        Node peker = forste;

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

        if (peker == null) { // slutten av lista
            siste.neste = ny;
            ny.forrige = siste;
            siste = ny;
            storrelse++;
            return;
        }

        peker.verdi = verdi;
    }

    @Override
    public String toString() {
        String ut = "";

        Node peker = forste;

        while (peker != null) {
            ut += "Nokkel: " + peker.nokkel.toString() + " - Verdi: " +
                  peker.verdi.toString() + "\n";
                  
            peker = peker.neste;
        }

        return ut;
    }

    public V hent(K nokkel) {
        Node peker = forste;

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

        if (peker != null) {
            return peker.verdi;
        }

        return null;
    }

    public V hentPaaIndeks(int indeks) {
        if (storrelse == 0 || indeks < 0 || indeks > storrelse) return null;

        Node peker = forste;
        for (int i = 0; i < indeks; i++) {
            peker = peker.neste;
        }
        return peker.verdi;
    }


    public V fjern(K nokkel) {
        V retur = null;

        if (hentStorrelse() == 0) return retur;

        Node peker = forste;
        if (hentStorrelse() == 1 && peker.nokkel.equals(nokkel)) {
            retur = peker.verdi;
            //forste = siste = null;
            forste = null;
            siste = null;
            storrelse--;
            return retur;
        }

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

        // Fant noe vi skal fjerne
        if (peker != null) {
            storrelse--;

            retur = peker.verdi;

            // Oppdatere referanser
            if (peker == forste) {
                forste = forste.neste;
                forste.forrige = null;
            } else {
                peker.forrige.neste = peker.neste;

                if (peker == siste) {
                    siste = siste.forrige;
                }

                else {
                    peker.neste.forrige = peker.forrige;
                }
            }
        }
        return retur;
    }

    @Override
    public Iterator<K> iterator() {
        return new AListeIterator();
    }

    private class AListeIterator implements Iterator<K> {
        Node peker = forste;

        @Override
        public boolean hasNext() {
            return peker != null;
        }

        @Override
        public K next() {
            K nokkel = peker.nokkel;
            peker = peker.neste;
            return nokkel;
        }
    }

}