# klasse som skal holde på verdiene i lenkelisten
class Node:
    def __init__(self, verdi):
        self.verdi = verdi
        self.neste = None


class Lenkeliste:
    def __init__(self):
        self.forste = None
        self.lengde = 0

    # legger til en node først i lenkelisten
    def leggTil(self, node):
        if self.lengde > 0:  # sparer på lista dersom den finnes
            node.neste = self.forste

        self.forste = node  # oppdaterer førstepekeren
        self.lengde += 1

    # fjerner den første noden fra lenkelisten
    def fjern(self):
        if self.lengde > 0:
            self.forste = self.forste.neste
            self.lengde -= 1
        else:
            print("Kan ikke fjerne fra en tom lenkeliste!")

    def skrivUt(self):
        """
        For å skrive ut innholdet i en lenkeliste er vi nødt til å iterere gjennom lenkelisten.
        Dette kan vi gjøre ved å starte på den første noden, deretter følge neste-pekerene
        helt til vi møter en node som ikke finnes (har verdien None).
        """

        '''
        # enkel utskrift på formen: 1 2 3
        node = self.forste
        while node is not None:
            print(node.verdi)
            node = node.neste
        '''

        # mer "fancy" utskrift på formen: [1 -> 2 -> 3]
        node = self.forste
        print("[", end="")
        while node is not None:
            print(node.verdi, end="")
            node = node.neste
            if node is not None:
                print(" -> ", end="")
        print("]")

    ### UTFORDRINGER
    def leggTilBakerst(self, ny_node):
        # må iterere gjennom lista til jeg finner det siste elementet
        # deretter kan jeg legge til en node

        node = self.forste
        while node.neste is not None:  # itererer til node sin neste ikke finnes
            node = node.neste

        # node burde nå være den siste noden
        node.neste = ny_node
        self.lengde += 1

    def fjernBakerst(self):
        node = self.forste

        if self.lengde == 0:
            print('Kan ikke fjerne fra en tom liste!')
        else:
            if self.lengde == 1:  # kun ett element i lista
                self.forste = None

            elif self.lengde > 1:  # minst to elementer i lista, finn nest siste element
                while node.neste.neste is not None:
                    node = node.neste
                node.neste = None

            self.lengde -= 1

    def leggTilPaaIndeks(self, ny_node, indeks):
        # indeks er gyldig dersom den er mellom 0 og lengden
        if 0 <= indeks <= self.lengde:
            if indeks == 0:  # vil legge til først
                ny_node.neste = self.forste
                self.forste = ny_node
            else:
                # itererer med to pekere, en for gjeldende node og en for noden før
                # vil legge til mellom disse nodene
                node = self.forste
                forrige = None

                for i in range(indeks):
                    forrige = node
                    node = node.neste

                forrige.neste = ny_node
                ny_node.neste = node
        else:
            print('Kan ikke legge til på indeks', indeks)

    def fjernPaaIndeks(self, indeks):
        # indeks er gyldig dersom den er mellom 0 og lengden - 1
        if self.lengde == 0:
            print('Kan ikke fjerne fra en tom liste!')

        elif 0 <= indeks < self.lengde:
            if indeks == 0:  # vil fjerne første element
                self.forste = self.forste.neste
            else:
                node = self.forste.neste
                forrige = self.forste

                for i in range(1, indeks):
                    forrige = node
                    node = node.neste

                forrige.neste = node.neste

        else:
            print('Kan ikke fjerne fra indeks', indeks)


def hovedprogram():
    lenkeliste = Lenkeliste()

    lenkeliste.leggTil(Node(1))
    lenkeliste.leggTil(Node(2))
    lenkeliste.leggTil(Node(3))
    lenkeliste.leggTil(Node(4))
    lenkeliste.skrivUt()  # forventer 4 -> 3 -> 2 -> 1

    lenkeliste.fjern()
    lenkeliste.skrivUt()  # forventer 3 -> 2 -> 1

    lenkeliste.leggTilBakerst(Node(5))
    lenkeliste.skrivUt()  # forventer 3 -> 2 -> 1 -> 5

    lenkeliste.fjernBakerst()
    lenkeliste.skrivUt()  # forventer 3 -> 2 -> 1

    lenkeliste.leggTilPaaIndeks(Node(5), 2)
    lenkeliste.skrivUt()  # forventer 3 -> 2 -> 5 -> 1

    lenkeliste.fjernPaaIndeks(1)
    lenkeliste.skrivUt()  # forventer 3 -> 5 -> 1


hovedprogram()