Linked List c/ Python
Implementação de estrutura de dados e algoritmos
O que é uma Linked List?
Em português é geralmente traduzido como “lista ligada” ou “lista encadeada”. Linked List é uma estrutura de dados, um conjunto de nós (node) ligados um ao outro, formando uma sequência.
“A linked list is a data structure consisting of a group of nodes which together represent a sequence.” — Wikipedia
Vamos ver um exemplo visual:
O “Head” (topo, inicio, cabeça da Linked List) referencia o primeiro nó: o valor 54, que referencia o 26, que referencia o 93 e assim por diante. Até chegar no último, o 31 (end), que não referencia nenhum outro nó.
Uma parte básica da implementação de uma linked list é o nó (chamaremos de node). Um objeto node necessita armazenar dois tipo de informação: um valor e a referência do próximo node.
→ Representação gráfica de um node
Implementação da classe Node
Enfim, vamos ao código! Iremos implementar a classe Node, parte importante da Linked List.
Bom, temos em mente que o objeto Node tem duas partes principais: um valor e a referência.
Então iniciamos nossa implementação com o método init, para instanciar nosso objeto Node. Ao criar um objeto Node, teremos inicializado e atribuído um valor para o objeto. Além desse valor, o objeto possui a referência do próximo objeto (chamaremos de next), porém, é inicializado como None.
Uma observação importante é que o valor None representa que, de fato, não existe um próximo objeto Node.
Vamos instanciar um objeto…
...e representá-lo graficamente:
A implementação da classe Node segue abaixo:
Basicamente implementei métodos getters e setters do valor data e a referência next do objeto Node. Vamos criar um objeto e utilizar esses novos métodos:
Implementação da Linked List
Bom, vamos lembrar da definição de uma Linked List: “A linked list is a data structure consisting of a group of nodes which together represent a sequence.”. Ou seja, ela é uma estrutura de dados construída através de agrupamento de nós (nodes).
Ao criar uma linked list, o objeto possui um atributo head, que terá, inicialmente, o valor None, quando a linked list estiver vazia. Ou apontará para o próximo node, caso não estiver vazia.
Vamos ver o método init para instanciar um objeto linked list:
…criar um objeto:
…e ver a representação gráfica dele:
Ao instanciar, o objeto linked list está vazio, logo o head tem o valor None.
Para sabermos se a linked list está vazia, apenas precisamos verificar se o “head == None”. Vamos implementar esse método (is_empty)
Bom, agora que podemos criar um objeto linked list e verificar se está vazio, precisamos implementar o método add para inserir elementos em nossa linked list.
Basicamente, a implementação do método add é adicionar um node com o valor especificado (nesse caso foram 77, 17…) no inícia da linked list. Vamos ver um representação gráfica ao adicionar esses elementos na linked list.
Podemos observar que o primeiro node (77) adicionado está no final da linked list, pois todos que foram adicionados depois desse primeiro, entraram no início da linked list.
Chega de blá blá blá, vamos à implementação!
Vamos entender o que está acontecendo! São dois passos principais:
- um novo objeto node é criado com o valor especificado, e atribui a referência do head como o próximo node.
- o primeiro elemento da linked list passa a ser o node recém criado (atribui o objeto node no head).
Veremos a ilustração:
Essa ilustração representa quando estávamos adicionando o valor 26 na linked list. O primeiro passo é criar o node com o valor 26 e apontar o next para o head (no caso, era o node com valor 93). O segundo passo é fazer o head apontar para o primeiro node, que é o recém adicionado.
Agora vamos implementar o método size. Basicamente esse método retornará a quantidade de nodes que há na linked list.
Então o que o código está fazendo?
A implementação do método size tem um loop que irá iterar até que a linked list chegue no seu final (quando current for igual a None). A cada iteração, acrescenta +1 no contador. No final ele terá a quantidade de nodes da linked list.
Agora vamos ao método seach. Esse método irá procurar o item especificado e retornar um valor booleano (true ou false).
O que o código está fazendo?
Basicamente o método search tem um loop que irá iterar até o final da linked list OU até achar o item especificado. Se o item do node atual (current) for igual ao item especificado (ou seja, o item foi achado), ele atribui o valor True para a variável found, sai do loop, e retorna que achou o item especificado (True). Caso não for igual, ele passa para o próximo node.
Agora o último método da linked list: o remove. Ele terá, nos argumentos, o item especificado para ser removido da linked list.
O método remove requer de 3 passos importantes:
- Atravessar a linked list a procura do item especificado. Basicamente esse passo é similar ao método search. Atravessa a linked list até que ache o item.
- A cada iteração, se não achar o item especificado, move o previous e o current para os, respectivos, próximos nodes.
- O next previous será o next do current. Ou seja, estamos removendo o node current, que possui o item especificado.
Vamos ver o “passo 2”, movendo o previous e o current, graficamente:
…e o “passo 3”: remover, de fato, o node com o item especificado
