lde_01102020_fimaula

# Lista Duplamente Encadeada com uso de Sentinelas

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

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

class LDE:
    def __init__(self):
        self.header = Dnodo()   # <<< Sentinela Cabeça
        self.trailer = Dnodo()  # <<< Sentinela Cauda
        self.tam = 0            # qtde de itens na lista

    def is_empty(self):
        if self.header.proximo is None and self.trailer.anterior is None:
            return True
        return False

    def __inserir(self, novo):
        self.header.proximo = novo    # header -> novo
        novo.anterior = self.header   # header <- novo
        novo.proximo = self.trailer   # novo -> trailer
        self.trailer.anterior = novo  # novo <- trailer

    def inserirInicio(self, novo):
        self.tam += 1
        if self.is_empty():
            self.__inserir(novo)
        else:
            primeiro = self.header.proximo # variavel auxiliar
            self.header.proximo = novo     # header -> novo
            novo.anterior = self.header    # novo -> header
            novo.proximo = primeiro        # novo -> primeiro
            primeiro.anterior = novo       # primeiro <- novo

    def inserirFim(self, novo):
        self.tam += 1
        if self.is_empty():
            self.__inserir(novo)
        else:
            ultimo = self.trailer.anterior
            ultimo.proximo = novo          # ->
            novo.anterior = ultimo         # <-
            novo.proximo = self.trailer    # ->
            self.trailer.anterior = novo   # <-


    def removerInicio(self):
        if self.is_empty():
            print('Lista Vazia!')
            return
        else:
            # lista possui + de 1 item
            removido = self.header.proximo
            if removido.proximo == self.trailer: # se existir apenas 1 item na lista
                self.header.proximo = None
                self.trailer.anterior = None
            else:
                self.header.proximo = removido.proximo
                removido.proximo.anterior = self.header
                removido.proximo = None
                removido.anterior = None

        self.tam -= 1
        return removido

    def removerFim(self):
        if self.is_empty():
            print('Lista Vazia!')
            return
        else:
            # lista possui + de 1 item
            removido = self.trailer.anterior
            if removido.anterior == self.header: # se existir apenas 1 item na lista
                self.header.proximo = None
                self.trailer.anterior = None
            else:
                self.trailer.anterior = removido.anterior
                removido.anterior.proximo = self.trailer
                removido.proximo = None
                removido.anterior = None

        self.tam -= 1
        return removido

    def imprimir(self, reverso=False):
        if self.is_empty():
            print('Lista Vazia')
            return

        if not reverso:
            item = self.header.proximo # devolve o 1o da lista
            while item.proximo is not None:
                print(item)
                item = item.proximo
        else:
            item = self.trailer.anterior # devolve o ultimo da lista
            while item.anterior is not None:
                print(item)
                item = item.anterior

    def buscar(self, alvo): # retorna a 1a ocorrencia | alvo eh o valor que o usuario busca
        if self.is_empty():
            print('Lista Vazia')
            return

        item = self.header.proximo # devolve o 1o da lista
        while item.proximo is not None:
            if item.dado == alvo:
                return item

            item = item.proximo

    def get(self, posicao):
        if self.is_empty():
            print('Lista Vazia')
            return

        if posicao < 0 or posicao >= self.tam:
            raise IndexError('Posicao Inexistente')

        if posicao <= (self.tam // 2):
            pos_atual = 0

            item = self.header.proximo # devolve o 1o da lista
            while item.proximo is not None:
                if pos_atual == posicao:
                    return item

                item = item.proximo
                pos_atual += 1
        else:
            pos_atual = self.tam - 1

            item = self.trailer.anterior # devolve o ultimo da lista
            while item.anterior is not None:
                if pos_atual == posicao:
                    return item

                item = item.anterior
                pos_atual -= 1

    def removerAntes(self, alvo):
        # header <-> [] <-> [] <-> trailer

        nodo_atual = self.buscar(alvo)
        nodo_anterior = nodo_atual.anterior

        if (nodo_anterior != self.header):
            aux = nodo_anterior.anterior
            aux.proximo = nodo_atual
            nodo_atual.anterior = aux

            nodo_anterior.anterior = None
            nodo_anterior.proximo = None

        self.tam -= 1

    def removerApos(self, alvo):
        pass

    def substituir(self, alvo, valor):
        pass

    def buscarTodos(self, alvo): # retorna uma list com resultados
        lista_todos = []
        ##
        ## sua logica aqui
        ##
        return lista_todos

    def primeiro(self):
        if self.is_empty():
            print('Lista Vazia')
            return
        else:
            return self.header.proximo

    def ultimo(self):
        if self.is_empty():
            print('Lista Vazia')
            return
        else:
            return self.trailer.anterior

    def __len__(self):
        return self.tam

## TESTES ##

lista = LDE()
lista.inserirInicio(Dnodo('abc'))
lista.inserirInicio(Dnodo(9999))
lista.inserirInicio(Dnodo('xyz'))
lista.inserirFim(Dnodo(9999))
lista.removerInicio()
lista.imprimir()

achou = lista.buscar(9999)
if not achou:
    print("Nao encontrado")
else:
    print("Encontrou: {}".format(achou))