Array e lista encadeada - Entenda a diferença
Tags: coding, go, programming, beginners
Published: 2023-05-15 16:50:24

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.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mqpliy432uc0s6nnjs6b.png)

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!


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ekf9jqdcqhax8jizeu48.png)

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.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g4dqpgao1dzs8tityvvp.png)


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](https://www.youtube.com/@loianegroner)
> 

> **Entendendo Algoritmos: Um Guia Ilustrado Para Programadores e Outros Curiosos -** [Aditya Y. Bhargava](https://www.amazon.com.br/s/ref=dp_byline_sr_book_1?ie=UTF8&field-author=Aditya+Y.+Bhargava&text=Aditya+Y.+Bhargava&sort=relevancerank&search-alias=stripbooks)
> 

> ****Data Structures in Golang - Linked List (1/2) -**** [Junmin Lee](https://www.youtube.com/@JunminLee)Junmin Lee
>