Implementando Linked List
Em meados de 2017, publiquei um artigo sobre lista encadeada, ou Linked List para os mais íntimos, esse artigo é uma atualização/refatoração. Esse é um tópico abordado em cursos e graduações e realmente ajuda a imaginar como seria a vida de um desenvolvedor se as listas não fossem implementadas no core de uma linguagem de alto nível.
Linked List
É uma coleção linear de itens de dados que não recebem uma ordem linear para sua alocação física na memória.
Definições
Singly Linked List é implementação, onde cada elemento possui um vínculo para o próximo elemento. Desta forma, é possível percorrer os elementos de forma unidirecional, ou seja, em uma única direção.
Double Linked List é uma variação do Linked List onde cada elemento tem um vínculo anterior e seguinte, portanto, é bidirecional.
Conceito
Linked List serve como base para implementar outras estruturas de dados, como Lista, Dicionário, Fila e Pilha.
Uma vantagem de uma Linked List é que cada elemento ocupa um espaço de memória, de modo que os elementos podem ser adicionados ou removidos sem a necessidade de mover ou realocar o disco.
Teste de algoritmo
Nos dois cenários propostos, os itens 1 e 5 são excluídos em uma lista de itens contendo valores iniciais [1, 3, 5, 7, 11].
Singly Linked List
Formato: Atual → Próximo
Quando inserimos um item na lista, o nó adicionado é vinculado como próximo no nó item anterior, sendo assim podemos percorrer do inicio ao fim, porém sem a possibilidade de retorno.
As propriedades head e tail definem o início e o fim da lista, para que seja possível percorrer do início ou ir direto ao fim da lista.
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def to_output(self):
return "{:0>2}->{:0>2}".format(self.value, self.next.value if self.next else 0)
class SinglyLinkedList:
def __init__(self):
self.__head = None
self.__tail = None
def add(self, value):
node = Node(value)
if not self.__head:
self.__head = self.__tail = node
else:
self.__tail.next = node
self.__tail = node
return node
def remove(self, value):
current = self.__head
previous = None
while current:
if current.value == value:
if previous:
previous.next = current.next
if current == self.__tail:
self.__tail = previous
else:
self.__head = current.next
if current == self.__tail:
self.__tail = None
break
previous = current
current = current.next
def list(self):
current = self.__head
if not current:
print("List is empty")
return
while current:
print(current.to_output())
current = current.next
my_list = SinglyLinkedList()
my_list.add(1)
my_list.add(3)
my_list.add(5)
my_list.add(7)
my_list.add(11)
my_list.list()
print("Removing...")
my_list.remove(5)
my_list.remove(1)
my_list.list()
Resultado:
01->03
03->05
05->07
07->11
11->00
Removing...
03->07
07->11
11->00
Doubly Linked List
Formato: Anterior <- Atual -> Próximo
Seguindo o mesmo conceito do Singly Linked List, ao inserir na lista, também é feito um vinculo entre o nó atual e adicionalmente ao nó anterior, a propriedade next do nó anterior é vinculada ao nó atual e a propriedade prev do nó atual é vinculada ao nó anterior.
class Node:
def __init__(self, value, prev_node=None, next_node=None):
self.value = value
self.prev = prev_node
self.next = next_node
def __str__(self):
return "{:0>2}<-{:0>2}->{:0>2}".format(
self.prev.value if self.prev else 0,
self.value,
self.next.value if self.next else 0,
)
class DoublyLinkedList:
def __init__(self):
self.__head = None
self.__tail = None
def add(self, value):
node = Node(value)
if not self.__head:
self.__head = self.__tail = node
else:
node.prev = self.__tail
self.__tail.next = node
self.__tail = node
return node
def remove(self, value):
current = self.__head
while current:
if current.value == value:
if current.prev:
current.prev.next = current.next
else:
self.__head = current.next
if current.next:
current.next.prev = current.prev
else:
self.__tail = current.prev
break
current = current.next
def __str__(self):
elements = []
current = self.__head
while current:
elements.append(str(current))
current = current.next
return "\n".join(elements)
my_list = DoublyLinkedList()
my_list.add(1)
my_list.add(3)
my_list.add(5)
my_list.add(7)
my_list.add(11)
print(my_list)
print("Removing...")
my_list.remove(5)
my_list.remove(1)
print(my_list)
Resultado:
00<-01->03
01<-03->05
03<-05->07
05<-07->11
07<-11->00
Removing...
00<-03->07
03<-07->11
07<-11->00
Variação
Circular Linked List
É uma variação da Doubly Linked List, onde há uma referência dos cursores head/tail para o primeiro e ao último elemento, criando um loop para que a iteração nunca pare.
Prós
- A estrutura de dados é dinâmica e cresce alocando e liberando memória em tempo de execução sem definir um tamanho inicial;
- Operações de inserção, exclusão e manipulação são fáceis de executar em qualquer local da lista;
- Facilita a implementação de pilhas e filas;
- É possível inverter uma lista bidirecional;
Contras
- Devido à forma como os ponteiros são armazenados, eles consomem mais memória do que os arrays;
- Os nós são sempre acessados na ordem de criação, portanto devem ser lidos desde o início;
- Os nós são armazenados de forma inconsistente em locais diferentes de memória, aumentando significativamente o tempo de acesso a itens individuais;
Finalizando
Como você pode ver, Linked List aplica-se a uma variedade de estruturas de tipo de dados usadas com certa frequência. A vinculação entre os nós só é possível porque as referências são armazenadas, não os valores. Ao contrário do que é encontrado em algumas linguagens e frameworks, Linked List não é...
Até a próxima, mantenha seu 🧠 kernel atualizado. Deus abençoe 🕊️.
Time for feedback!