Listas encadeadas utilizando Python
Implementação prática de uma estrutura de dados bastante utilizada em programação.
Definição
É uma estrutra de dados, um conjunto de nós ligados um ao outro, formando uma sequência. Ela permite armazenar um número de elementos limitado apenas pela memória disponível.
Onde são utilizadas
Elas podem ser utilizadas para implementar Filas ou Pilhas, bem como gráficos. Podem ser utilizadas para tarefas mais complexas, como o gerenciamento do ciclo de vida de um aplicativo do sistema operacional.
Vantagens
“A inserção ou remoção de um elemento na lista não implica a mudança de lugar de outros elementos;
Não é necessário definir, no momento da criação da lista, o número máximo de elementos que esta poderá ter. Ou seja, é possível alocar memória “dinamicamente”, apenas para o número de nós necessários” — wikipédia
Desvantagens
“A manipulação torna-se mais “perigosa” uma vez que, se o encadeamento (ligação) entre elementos da lista for mal feito, toda a lista pode ser perdida;
Para aceder ao elemento na posição n da lista, deve-se percorrer todos os elementos (n — 1) anteriores.” — Wikipédia
Implementação em Python
Cada nó da lista encadeada armazena dois valores: o dado em si e o endereço do próximo nó.
Para trabalhamos com a lista precisamos definir o ínicio e o fim, sendo representado respectivamente por head e None. Definido esses pontos, a estrutura da nossa lista ficaria como na imagem a seguir:
Vamos a implementação!!
Primeiro iremos definir a Classe Node, onde o objeto nó será definido. Essa classe recebe como argumento um dado que será armazenado no objeto. No momento da instanciação do objeto, a informação a respeito do próximo nó será None.
Agora vamos implementar a Classe que definirá a nossa lista encadeada. Essa classe tem como atributo o head que recebe por padrão o valor None. Assim que o primeiro nó for adicionado, o head apontará para ele.
Criaremos os métodos de inserção de nós. Para isso vamos levar em consideração três situações: no início da lista, fim e depois de algum nó existente.
Início da lista
Linha 14: O novo nó é instanciado, passando como parâmetro o dado desejado.
Linha 15: É passado o endereço do proxímo nó ou None se for o caso.
Linha 16: O head aponta para o novo nó.
Fim da lista
Linha 19: O novo nó é instanciado.
Linha 22: Verifica se a lista está vazia, se estiver repete os passos da linha 15 e 16.
Caso a lista não esteja vazia, é realizado um loop até encontrar o último elemento da lista. Encontrado o último elemento, o novo nó é inserido.
Depois de algum nó existente
É realizado um loop while que percorerá toda a lista, caso o nó alvo seja encontrado, o novo nó será inserido após ele, se não for, imprimi uma mensagem de que o nó alvo não foi encontrado.
Removendo um nó
O código verifica se o nó a ser removido é o primeiro da lista, se for, o head passa a apontar para o próximo nó. Caso contrário, é feita uma busca ao longo da lista sempre armazenando o nó anterior. Se o nó for encontrado, o nó anterior passará a apontar para o sucessor do nó a ser removido. A imagem abaixo ilustra a ação do método.
Imprimindo a lista encadeada
Para que possamos imprimir a lista criada, o método especial __str__ foi implementado. O método é chamado toda vez que imprimimos um objeto da classe, no caso, nossa lista encadeada. Ele basicamente cria uma lista vazia, adiciona os nós na sequência, e retorna seus dados como uma string.
Exemplo de uso
O código abaixo exemplifica o uso da lista encadeada, tomando como dados uma lista de atividades e adicionando cada elmento de acordo com a ordem de prioriade.
Saída:
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — -
Saída:
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — -
Saída:
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Saída:
Código completo
Aqui está o código completo descrito no artigo. O mesmo pode ser baixado no repositório disponibilizado no Github.
Então é isso, espero que tenha sido útil esta implementação simples em Python. Minha intenção é escrever com frequência sobre algoritmos e estruturas de dados utilizando Python, a medida que avanço nos meus estudos.
Deixe sua opinião! Críticas e sugestões são bem-vindas.