Share
brasil flag logo python logo
William Sena
William Sena
5 5 min read

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.

Michael Scott implorando para que isso não aconteça.

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.

Pokémon Slowpoke em loop

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 é...

Magic

Até a próxima, mantenha seu 🧠 kernel atualizado. Deus abençoe 🕊️.

Referências

Back to home page