public class Lenkeliste {
    private Node start;

    public void leggTil(String data) {
        Node ny = new Node(data);

        if (start == null) {
            start = ny;
        } else {
            leggTilRekursivt(start, ny);
        }
    }

    private void leggTilRekursivt(Node naavaerendeNode, Node ny) {
        if (naavaerendeNode.neste == null) { // er på slutten
            naavaerendeNode.neste = ny;
        } else {
            leggTilRekursivt(naavaerendeNode.neste, ny);
        }
    }

    public int finnForekomster(String ord) {
        return finnForekomsterRekursivt(start, ord, 0);
    }

    private int finnForekomsterRekursivt(Node naavaerendeNode, String ord, int antallForekomster) {
        if (naavaerendeNode == null) {
            return antallForekomster;
        }

        if (naavaerendeNode.data.equals(ord)) {
            return finnForekomsterRekursivt(naavaerendeNode.neste, ord, antallForekomster + 1);
        }
        return finnForekomsterRekursivt(naavaerendeNode.neste, ord, antallForekomster);
    }

    public int stoerrelse() {
        return stoerrelseRekursivt(start);
    }

    private int stoerrelseRekursivt(Node naavarendeNode) {
        if (naavarendeNode == null) {
            return 0;
        }
        return 1 + stoerrelseRekursivt(naavarendeNode.neste);
    }

    @Override
    public String toString() {
        return hentUtskriftRekursivt(start, "");
    }

    private String hentUtskriftRekursivt(Node naavaereNode, String utskrift) {
        if (naavaereNode == null) {
            return utskrift;
        } 
        return hentUtskriftRekursivt(naavaereNode.neste, utskrift + naavaereNode.data + "\n");
    }

    private class Node {
        String data;
        Node neste;

        public Node(String dat) {
            data = dat;
        }
    }
}