Olá novamente! Antecipando o início do curso Python Developer, preparamos para você um pequeno material autoral em listas vinculadas no Python.
Python é uma linguagem muito conveniente e multifacetada, mas, por padrão, não possui uma estrutura de dados como uma lista vinculada ou LinkedList. Hoje vou compartilhar minhas melhores práticas sobre esse tópico e falar um pouco sobre o que é essa estrutura de dados. Este artigo será de interesse para quem primeiro se deparar com o tópico de listas vinculadas e quiser entender como elas funcionam do ponto de vista algorítmico.
O que é uma LinkedList?
Uma LinkedList ou lista vinculada é uma estrutura de dados. Uma lista vinculada fornece a capacidade de criar uma fila bidirecional a partir de qualquer elemento. Cada elemento dessa lista é considerado um nó. De fato, um nó tem seu valor, bem como dois links para os nós anteriores e subsequentes. Ou seja, a lista é "vinculada" por nós que ajudam a subir ou descer a lista. Devido a esses recursos estruturais, você pode organizar uma pilha, fila ou fila dupla a partir de uma lista vinculada.
Vamos visualizar definições secas. Agora temos gatos que estão sentados em caixas. E em cada caixa diz o que está em ordem e o que deveria representar.
O que faremos com uma lista vinculada:- Verifique se este ou aquele elemento está contido nele;
- Adicione nós ao final;
- Obter o valor de um nó por índice;
- Excluir nós.
De fato, existem muito mais opções para trabalhar com eles, mas continuaremos a implementar essas etapas básicas. Tendo entendido por que princípio eles são construídos, você mesmo pode implementar facilmente seus próprios métodos.
Você terá que começar criando duas classes:
class Box: def __init__ (self,cat = None): self.cat = cat self.nextcat = None class LinkedList: def __init__(self): self.head = None
No caso geral, temos um nó que tem algum valor interno - um gato e um link para o próximo nó. Ou seja, na classe Box, respectivamente, há um gato e um link para a próxima caixa. Como qualquer lista, o coerente também tem um começo, a saber, cabeça. Como não há nada lá inicialmente, o elemento inicial é definido como Nenhum.
O item está na lista
Vamos começar com um simples. Para verificar se existe algum gato em particular em uma das caixas localizadas em série, você precisa percorrer a lista inteira, verificando o valor existente com os valores do elemento na lista.
def contains (self, cat): lastbox = self.head while (lastbox): if cat == lastbox.cat: return True else: lastbox = lastbox.nextcat return False
Adicionar nó ao final da lista
Primeiro você precisa criar uma nova caixa e já colocar um novo gato nela. Depois disso, é necessário verificar, a partir do início da lista vinculada, se existe um link para o próximo no nó atual e se houver, em seguida, vá para ele, caso contrário, o nó é o último, portanto, é necessário criar um link para o próximo nó e colocar a mesma nova caixa nele. que criamos.
def addToEnd(self, newcat): newbox = Box(newcat) if self.head is None: self.head = newbox return lastbox = self.head while (lastbox.nextcat): lastbox = lastbox.nextcat lastbox.nextcat = newbox
Obter um nó por índice
Queremos obter um nó de caixa pelo índice catIndex, mas como os nós não são fornecidos com esse índice, precisamos criar algum tipo de substituição, ou seja, uma variável que atuará como índice. Essa variável é boxIndex. Percorremos toda a lista e verificamos o "número de série" do nó e, se ele corresponder ao índice desejado, produzimos o resultado.
def get(self, catIndex): lastbox = self.head boxIndex = 0 while boxIndex <= catIndex: if boxIndex == catIndex: return lastbox.cat boxIndex = boxIndex + 1 lastbox = lastbox.nextcat
Excluir nó
Aqui consideramos a remoção de um elemento não por índice, mas por valor, a fim de introduzir pelo menos alguma variedade.
A pesquisa começa no cabeçalho da lista, ou seja, da primeira caixa em uma linha e continua até que as caixas acabem, ou seja, até o cabeçalho se tornar Nenhum. Verificamos se o valor armazenado no nó atual corresponde ao que queremos excluir. Se não, então apenas seguimos em frente. No entanto, se corresponder, excluí-lo e "vincular novamente" os links, ou seja, excluiremos a caixa N-ésima, enquanto a caixa N-1 agora se refere à caixa N + 1.
def removeBox(self,rmcat): headcat = self.head if headcat is not None: if headcat.cat==rmcat: self.head = headcat.nextcat headcat = None return while headcat is not None: if headcat.cat==rmcat: break lastcat = headcat headcat = headcat.nextcat if headcat == None: return lastcat.nextcat = headcat.nextcat headcat = None
Só isso, obrigado por ler o material! De fato, a estrutura LinkedList não é complicada e é importante entender como funciona por dentro. Obviamente, no Python, ele poderia ter sido implementado em expressões lambda, ocuparia muito menos espaço, mas aqui pretendi explicar sua estrutura e o princípio de sua operação no Python o mais detalhado possível, em vez de buscar otimização.
O código fonte pode ser
encontrado aqui .