import java.util.Objects;

public class RekursivLinkedList<T> {

    // Node-klassen
    private static class Node<T> {

        // Beholder for innhold
        T data;
        // Peker til neste node
        Node<T> neste;

        // Konstrukt?r for nodene
        Node(T data) {
            this.data = data;
            this.neste = null;
        }
    }

    // F?rste element (hode)
    private Node<T> f?rste;

    // Konstrukt?r for listen
    public RekursivLinkedList() {
        this.f?rste = null;
    }

    // Metode for ? legge til
    public void leggTil(T data) {
        if (f?rste == null) {
            f?rste = new Node<>(data);
        } else {
            leggTilRekursivt(f?rste, data);
        }
    }

    // Rekursivt
    private void leggTilRekursivt(Node<T> peker, T data) {
        if (peker.neste == null) {
            peker.neste = new Node<>(data);
        } else {
            leggTilRekursivt(peker.neste, data);
        }
    }

    // Metode for ? finne element
    public boolean finn(T data) {
        return finnRekursivt(f?rste, data);
    }

    // Rekursivt
    private boolean finnRekursivt(Node<T> peker, T data) {
        if (peker == null) {
            return false;
        }
        if (Objects.equals(peker.data, data)) {
            return true;
        }
        return finnRekursivt(peker.neste, data);
    }

    // fjerne
    public void fjern(T data) {
        this.f?rste = fjernRekursivt(this.f?rste, data);
    }

    private Node<T> fjernRekursivt(Node<T> peker, T data) {
        // base
        if (peker == null) {
            return null;
        }

        // er lik
        if (Objects.equals(peker.data, data)) {
            return peker.neste;
        }

        peker.neste = fjernRekursivt(peker.neste, data);

        return peker;
    }

    @Override
    public String toString() {
        if (f?rste == null) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        toStringRekursivt(f?rste, sb);
        sb.append("]");
        return sb.toString();
    }

    private void toStringRekursivt(Node<T> peker, StringBuilder sb) {
        sb.append(peker.data);

        // base
        if (peker.neste == null) {
            sb.append(" -> null");
        } else {
            sb.append(" -> ");
            toStringRekursivt(peker.neste, sb);
        }
    }

    // equals
    public boolean erLik(T objekt) {
        if (this == objekt) {
            return true;
        }
        if (objekt == null || getClass() != objekt.getClass()) {
            return false;
        }
        // cast
        RekursivLinkedList<?> annet = (RekursivLinkedList<?>) objekt;
        return noderErLikRekursivt(this.f?rste, annet.f?rste);
    }

    // Rekursivt
    private boolean noderErLikRekursivt(Node<T> node1, Node<?> node2) {
        // base 1 - begge er null
        if (node1 == null && node2 == null) {
            return true;
        }
        // base 2 - en er null andre ikke
        if (node1 == null || node2 == null) {
            return false;
        }
        // Recursive step: Compare the next pair of nodes
        return noderErLikRekursivt(node1.neste, node2.neste);
    }

    public static void main(String[] args) {
        RekursivLinkedList<Integer> intList = new RekursivLinkedList<>();
        intList.leggTil(10);
        intList.leggTil(20);
        intList.leggTil(30);
        intList.leggTil(40);
        System.out.println("Integer Liste: " + intList);

        System.out.println("Finnes 20? " + intList.finn(20));
        System.out.println("Finnes 50? " + intList.finn(50));

        intList.fjern(30);
        System.out.println("Fjernet 30: " + intList);
        intList.fjern(10);
        System.out.println("Fjernet 10: " + intList);
        intList.fjern(55);
        System.out.println("Fjernet 55: " + intList);
        intList.fjern(40);
        System.out.println("Fjernet 40: " + intList);
        intList.fjern(20);
        System.out.println("Fjernet 20: " + intList);

        System.out.println("\n--------------------\n");

        RekursivLinkedList<String> stringList = new RekursivLinkedList<>();
        stringList.leggTil("Eple");
        stringList.leggTil("Banan");
        stringList.leggTil("Jordb?r");
        System.out.println("String Liste: " + stringList);

        System.out.println("Finnes Banan? " + stringList.finn("Banan"));
        System.out.println("Finnes Drue? " + stringList.finn("Drue"));

        stringList.fjern("Banan");
        System.out.println("Fjernet Banan: " + stringList);
    }
}