This content originally appeared on DEV Community and was authored by Cinthia Queiroz
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
}
func (list *LinkedList) add(newValue string) {
newNode := Node{value: newValue}
if list.Head == nil {
list.Head = &newNode
return
}
currentNode := list.Head
for currentNode.Next != nil {
currentNode = currentNode.Next
}
currentNode.Next = &newNode
}
func main() {
list := &LinkedList{}
list.add("Boyhood")
list.add("donnie darko")
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
This content originally appeared on DEV Community and was authored by Cinthia Queiroz
Cinthia Queiroz | Sciencx (2023-05-15T16:50:24+00:00) Array e lista encadeada - Entenda a diferença. Retrieved from https://www.scien.cx/2023/05/15/array-e-lista-encadeada-entenda-a-diferenca/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.