Array e lista encadeada - Entenda a diferença

#coding #go #programming #beginners

Criar, ler e deletar coleções de dados é algo que esta presente no dia a dia do programador e é muito comum nos usarmos sempre o famoso array, mas será que essa estrutura de dados é a melhor para todos os casos? Será que o array é essa bala de prata que tratamos como se fosse ?
Antes de respondermos essas questões, precisamos entender como um array de fato funciona.
Ok, uma informação que temos geralmente, é que um tamanho de um array é fixo e a memória alocada estaticamente, o que isso quer dizer? Quando criamos um array com um tamanho 5 é como se a gente estivesse falado "Oi, separa 5 lugares pra mim por favor?", mais ou menos como reservar 5 lugares em um restaurante. Vamos imaginar então um array que armazene os filmes preferidos de um usuário.
Quando salvamos dados em um array, é importante lembrar que cada valor que incluímos é armazenado em um espaço na memória. No exemplo a seguir, cada caixinha (coluna) representa um espaço na memória.

Implementação:

func main() {
 movies := [4]string{"boyhood", "donnie darko", "clube da luta", "clube dos cinco"}
 fmt.Println(movies)
}

Só que o que acontece se precisarmos incluir um novo filme nesse array ? Não podemos simplesmente adicionar esse novo filme em uma caixinha do lado, pois no momento de criar o array nos só alocamos 4 espaços e pode ser que o espaço do lado ja esteja sendo usado por outro recurso.
Então o que é necessário fazer nesse caso, seria achar 5 espaços vazios juntos e mover todo o array, junto com esse elemento, para os novos espaços alocados. Em outras palavras criar um novo array e mover tudo pra lá. O problema é que toda vez que um novo item for adicionado, o mesmo processo deve ser repetido e isso pode se tornar muito custoso e trabalhoso.

Implementação:

func main() {
 movies := [4]string{"boyhood", "donnie darko", "clube da luta", "clube dos cinco"}

 var newMovies [5]string

 for i := 0; i < len(movies); i++ {
  newMovies[i] = movies[i]
 }

 newMovies[4] = "her"

 fmt.Print(newMovies)

}

Então se o nosso array precisa ser constantemente modificado, inserindo e/ou deletando elementos, o array não é a melhor estrutura para ser utilizada.
Sei que quando falamos de implementação em codigo, muitas linguagens tem implementações de listas utilizando arrays, com funções de adicionar e remover itens que resolvem a questão a cima, mas é importante ressaltar que ao utilizar essas implementaçãoes ainda estamos utilizando arrays e isso não faz com que o codigo seja menos custoso pois o mesmo processo necessario para adicionar novos itens em um array continua sendo feito, a diferença é que não somos nos que implementamos esse processo.
Vamos então falar das listas encadeadas, como essa estrutura poderia resolver nosso problema?
Em uma lista encadeada, o tamanho dela não é fixo e a memória utilizada é alocada em tempo de execução, não precisamos que os elementos salvos em uma lista estejam juntos, um do lado do outro. Mas e se no momento que um novo item for adicionado o espaço ao lado do ultimo item inserido estiver sendo utilizado, o que eu faço ? Insere no próximo espaço disponível!

E como sabemos que o próximo item da lista de filmes não esta do lado ? e sim la na caixinha 8, por exemplo ? Listas encadeadas, possuem uma coisa que chamamos de ponteiro, cada caixinha, além de guarda seu conteúdo, também irá guardar a informação do endereço de memória do próximo elemento da lista, ou seja um ponteiro para o próximo elemento.

Nesse caso, nos sabemos que um um lista terminou, quando algum elemento não aponta para um próximo.
Então, eu devo usar listas encadeadas para tudo ? A resposta é não, lista encadeadas
são ótimas quando precisamos inserir e/ou deletar um elemento de uma lista por exemplo, mas vamos dizer que precisamos navegar em uma lista, achar elementos como o ultimo elemento ou o elemento do meio de uma lista. Com uma lista encadeada isso se torna mais difícil , pois por não sabermos o tamanho exato, para achar o elemento do meio pro exemplo, precisaremos percorrer toda a lista para saber seu tamanho e encontrar o meio, ou achar o ultimo elemento, precisaremos percorrer até achar um elemento que não aponte para o próximo , sendo assim, percorrer toda a lista até achar o que queremos.
Implementação de uma lista encadeada em Go.

type Node struct {
    value string
    Next  *Node
   }

   type LinkedList struct {
    Head *Node
    Tail *Node
   }

   func (list *LinkedList) add(newValue string) {
    newNode := Node{value: newValue}
    if list.Head == nil {
     list.Head = &newNode
     list.Tail = &newNode
     return
    }


    currentNode := list.Tail
    currentNode.Next = &newNode
    list.Tail = &newNode
   }


   func main() {
    list := &LinkedList{}
    list.add("Boyhood")
    list.add("donnie darko")
    list.add("Curtindo a vida adoidado")

    printList(list)
   }

   func printList(list *LinkedList) {
    currentNode := list.Head
    for currentNode != nil {
     fmt.Printf(currentNode.value)
     currentNode = currentNode.Next
    }
    fmt.Println()
   }

É importante aprender novas estruturas e entender bem as que já usamos para cada vez melhoramos nosso código e usar aquilo que mais irá trazer benefícios para o nosso código , com o avanço da tecnologia, das maquinas, a diferença de custo entre essas duas estruturas diminuiu, e uma nova discussão surgiu sobre o real custo beneficio na hora de escolher entre uma dessas estruturas, mas isso são cenas para um próximo capitulo.

Referências e recomendações

Estrutura de Dados com Java | Lista Encadeada | Introduçao - Loiane Groner

Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos - Aditya Y. Bhargava

*Data Structures in Golang - Linked List (1/2) -* Junmin LeeJunmin Lee