lse_final_2022

class Nodo:
    def __init__(self, dado):
        self.dado = dado
        self.proximo = None

    def __str__(self):
        return str(self.dado)

# ##############################
# Lista Simplesmente Encadeada
# [NODO] => [NODO] => None
class LSE:
    def __init__(self):
        self.head = None # cabeca | inicio
        self.tail = None # cauda  | fim
        self.tam = 0     # quantidade de elementos

    def is_empty(self): # retorna se a lista esta vazia
        if self.tam == 0 or self.head is None or self.tail is None:
            return True
        return False

    def inserir_fim(self, novo): # similar ao append da List
        self.tam += 1
        if self.is_empty():
            # lista vazia
            self.head = novo
            self.tail = novo
        else:
            # ja possui itens
            ## o tail atual deve apontar para o novo
            ## o tail sera atribuido para o novo
            self.tail.proximo = novo
            self.tail = novo

    def inserir_inicio(self, novo): # similar ao insert(0,item) da List
        if self.head is None and self.tail is None:
            # lista vazia
            self.head = novo
            self.tail = novo
        else:
            novo.proximo = self.head
            self.head = novo

        self.tam += 1

    def remover_inicio(self):
        if self.is_empty():
            print('Lista Vazia!')
            return

        self.tam -= 1 # diminui o contador de itens

        ## quando temos apenas 1 item
        if (self.head == self.tail):
            removido = self.head
            self.head = None
            self.tail = None

        # lista possui + de 1 item
        else:
            removido = self.head
            self.head = self.head.proximo
            removido.proximo = None

        return removido

    def remover_fim(self):
        if self.is_empty():
            print('Lista Vazia!')
            return

        ## precisamos descobrir quem eh o penultimo da lista!!
        removido = None
        item = self.head
        while (item != None):
            # quando tem apenas 1 item
            if (item == self.tail and item == self.head):
                self.head = None
                self.tail = None
                self.tam -= 1
                return item

            # quando tem mais de 1
            if (item.proximo != None and item.proximo == self.tail):
                removido = self.tail
                self.tail = item
                item.proximo = None
                self.tam -= 1
                return removido

            item = item.proximo

    def buscar(self, valor):
        if self.is_empty():
            print('Lista Vazia')
            return

        item = self.head
        while (item != None):
            if item.dado == valor:
                return item

            item = item.proximo

    def imprimir(self):
        if (self.head is None and self.tail is None):
            print('Lista Vazia')
            return

        item = self.head
        while (item != None):
            print(item)
            item = item.proximo

    def imprimir_lado(self):
        saida = ''
        item = self.head
        while (item != None):
            if item == self.head:
                saida += '[' + str(item) + ']'
            else:
                saida += ' => ' + '[' + str(item) + ']'
            item = item.proximo
        print(saida)

## TESTES ##

lista = LSE()
lista.inserir_fim( Nodo("ABC") )
lista.inserir_fim( Nodo("DEF") )
#lista.inserir_inicio( Nodo("123") )
#lista.remover_fim()
#lista.remover_inicio()

if lista.buscar("ABC") is not None:
    print("Achou")

lista.imprimir_lado()