5 min read

Implementando Linked List

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