public class LinkedList
{
    protected LinkedListElement first;
    protected LinkedListElement last;

    LinkedList()
    {
        makenull();
    }

    //Funkcija makenull inicializira seznam
    public void makenull()
    {
        //drzimo se implementacije iz knjige:
        //po dogovoru je na zacetku glava seznama (header)
        first = new LinkedListElement(null, null);
        last = null;
    }

    //Funkcija addLast doda nov element na konec seznama
    public void addLast(Object obj)
    {
        //najprej naredimo nov element
        LinkedListElement el = new LinkedListElement(obj);
        //ustrezno ga povezemo s koncem verige obstojecih elementov
        if(last == null) {
            first.next = el;
            last = first;
        } else {
            last.next.next = el;
            last = last.next;
        }
        //po potrebi posodobimo kazalca "first" in "last"
    }

    //Funkcija write izpise elemente seznama
    public void write()
    {
        //zacnemo pri elementu za glavo seznama
        //sprehodimo se po elementih do konca seznama
        //in izpisemo vrednost vsakega elementa
        LinkedListElement el;
        el = first.next;
        while(el != null) {
            System.out.print(el.element + ", ");
            el = el.next;
        }
        System.out.println();

        //za kontrolo lahko izpisemo tudi vrednosti kazalcev "first" in "last"
    }

    //Funkcija addFirst doda nov element na prvo mesto v seznamu (takoj za glavo seznama)
    void addFirst(Object obj)
    {
        //najprej naredimo nov element
        LinkedListElement el = new LinkedListElement(obj);
        //ustrezno ga povezemo z glavo seznama
        if(last == null) {
            first.next = el;
            last = first;
        } else {
            el.next = first.next;
            first.next = el;
        }
        //po potrebi posodobimo kazalca "first" in "last"
    }

    //Funkcija length() vrne dolzino seznama (pri tem ne uposteva glave seznama)
    int length()
    {
        int stevec = 0;
        LinkedListElement el = first.next;  // prvi dejanski element (od headerja prvi naslednji)
        while(el != null) {
            stevec++;
            el = el.next;
        }
        return stevec;
    }

    //Funkcija lengthRek() klice rekurzivno funkcijo za izracun dolzine seznama
    int lengthRek()
    {
        // pomagajte si z dodatno funkcijo int lengthRek(LinkedListElement el), ki izracuna
        // dolzino seznama za opazovanim elementom ter pristeje 1
        return lengthRek(first.next);
    }

    int lengthRek(LinkedListElement el)
    {
        if(el == null) {
            return 0;
        } else {
            return lengthRek(el.next)+1;
        }
    }

    //Funkcija insertNth vstavi element na n-to mesto v seznamu
    //(prvi element seznama, ki se nahaja takoj za glavo seznama, je na indeksu 0)

    boolean insertNth(Object obj, int n)
    {
        //zacnemo pri glavi seznama
        LinkedListElement el = new LinkedListElement(obj);
        //LinkedListElement iterate = first.next;   // da gledas dejansko od prvega elementa naprej
        LinkedListElement iterate = first;
        if(n==0) {
            this.addFirst(el.element);
            return true;
        } else if (n == this.length()) {
            this.addLast(el.element);
            return true;
        } else if (this.length() < n) {
            //System.out.println("Dodajanje na izbrano mesto ni mogoce.");
            return false;
        } else {
            for(int i=0; i<n; i++) {
                iterate = iterate.next;
            }
            el.next = iterate.next;
            iterate.next = el;
            if(this.length()-1 == n) {
                this.last = el;
            }
            return true;
        }

        //sprehodimo se po elementih dokler ne pridemo do zeljenega mesta

        // ce je polozaj veljaven
        //   naredimo nov element
        //   ustrezno ga povezemo v verigo elementov
        //   po potrebi posodobimo kazalec "last"
        //   vrnemo true
        // sicer
        //   vrnemo false
    }

    boolean deleteLast()
    {
        if(this.length() == 0) return false;
        if(this.length() == 1)
        {
            first.next = null;
            last = null;
            return true;
        }
        LinkedListElement elm = first;
        while(elm.next.next.next != null) {
            elm = elm.next;
        }
        elm.next.next = null;
        last = elm;
        return true;
    }

    //Funkcija deleteNth izbrise element na n-tem mestu v seznamu
    //(prvi element seznama, ki se nahaja takoj za glavo seznama, je na indeksu 0)
    boolean deleteNth(int n)
    {
        //zacnemo pri glavi seznama
        if(this.length() <= n) {
            return false;
        }
        if(this.length() == n + 1) {
            this.deleteLast();
            return true;
        }
        /*
        if(this.length() == n + 2) {
            LinkedListElement el = first;
            for(int i=0; i<n-1; i++) {
                el = el.next;
            }
            last = el;
            el.next = el.next.next;
            return true;
        }
        */
        //sprehodimo se po elementih dokler ne pridemo do zeljenega mesta
        LinkedListElement el = first;
        for(int i=0; i<n-1; i++) {
            el = el.next;
        }
        if(this.length() == n + 2) {
            last = el;
        }
        el.next = el.next.next;
        return true;
        // ce je polozaj veljaven
        //   ustrezno prevezemo elemente seznama tako, da ciljni element izlocimo iz verige
        //   po potrebi posodobimo kazalec "last"
        //   vrnemo true
        // sicer
        //   vrnemo false
    }

    //Funkcija reverse obrne vrstni red elementov v seznamu (pri tem ignorira glavo seznama)
    void reverse()
    {
        //ne pozabimo na posodobitev kazalca "last"!
        LinkedList temp = new LinkedList();
        LinkedListElement prejeti = first.next;
        for(int i=0; i<this.length(); i++) {
            temp.addFirst(prejeti.element);
            prejeti = prejeti.next;
            if(i == 2) {
                //last = prejeti;
            }
        }
        first = temp.first;
        last = temp.last;
    }

    //Funkcija reverseRek klice rekurzivno funkcijo, ki obrne vrstni red elementov v seznamu
    void reverseRek()
    {
        // pomagajte si z dodatno funkcijo void reverseRek(LinkedListElement el), ki
        // obrne del seznama za opazovanim elementom, nato ta element doda na konec (obrnjenega) seznama
    }

    //Funkcija removeDuplicates odstrani ponavljajoce se elemente v seznamu
    void removeDuplicates()
    {
        //ne pozabimo na posodobitev kazalca "last"!
        LinkedList temp = new LinkedList();
        LinkedListElement el = first.next;
        for(int i=0; i<this.length(); i++) {
            if(temp.elementObstaja(el.element)) {
                // ne dodas elementa v nov seznam, gres naprej
            } else {
                temp.addLast(el.element);
                el = el.next;
            }
        }
        first = temp.first;
        last = temp.last;
    }

    boolean elementObstaja(Object obj) {
        LinkedListElement trenutni = first;
        for(int i=0; i<this.length(); i++) {
            if(obj == trenutni.element) {
                return true;
            }
            else {
                trenutni = trenutni.next;
            }
        }
        return false;
    }
}