Uma estrutura de dados é uma maneira de armazenar e relacionar conjuntos de informações de forma organizada e, na maioria das vezes, sequencial. Estas estruturas são muito importantes quando precisamos armazenar um conjunto de dados para ser utilizado em um determinado software.
Na computação, há diversos tipos de estruturas de dados que podem ser utilizadas para diferentes fins. Neste artigo, veremos o que é e como funciona uma das principais, as listas.
Curso
Python - Estrutura de dados - Parte 1
Conhecer o curso
O que é uma lista?
As listas são estruturas de dados muito utilizadas. Elas armazenam os dados em um formato de lista (dado o nome).
Basicamente, uma lista é, na verdade, um conjunto de estruturas chamadas “nós”. Um nó é uma estrutura que armazena a informação a ser gerenciada por uma lista.
Na computação, existem dois tipos de lista: as listas ligadas e as listas duplamente ligadas.
Cada um dos nós de uma lista ligada, além de conhecer o valor que está sendo armazenado em seu interior, também conhece o elemento posterior a ele: por isso ela é chamada de “lista ligada”, pois os nós são amarrados com essa indicação de qual é o próximo nó.
Como funciona uma lista ligada?
Imagine uma lista ligada com o nome de funcionários de uma empresa. No começo, ela pode se apresentar da seguinte maneira (já que ela está vazia):
Quando adicionamos o primeiro nome à nossa lista, nós adicionamos um novo nó a essa lista. Esse nó não sabe quem será o próximo nó, já que nossa lista por hora só possui um único nó. Além disso, nossa lista precisa saber onde ela começa e onde ela termina, por isso, o nó inicial e o nó final também são indicados em uma lista ligada. Após adicionar nosso primeiro nome, nós podemos representar nossa lista da seguinte maneira:
Como temos um único nó, ele é indicado como o primeiro nó e como o último nó, além de não ter indicação do próximo nó (que ainda não existe).
No momento em que adicionamos um novo nome, nós podemos representar nossa lista com a ilustração abaixo:
Veja que, para adicionarmos um novo nó a uma lista ligada, fizemos basicamente as seguintes operações:
- Apontamos como sendo o último nó da lista o novo nó, já que ele foi o último a ser adicionado;
- Pegamos quem era anteriormente o último nó e indicamos que o próximo nó dele será este último nó adicionado.
Curso
Java - Estrutura de dados - Parte 1
Conhecer o curso
Como funciona uma lista duplamente ligada?
As listas duplamente ligadas constituem uma variação das listas ligadas. Por isso, elas apresentam praticamente o mesmo comportamento das listas ligadas.
A grande diferença das listas duplamente ligadas para as listas ligadas é que elas são bidirecionais. Vimos que, naturalmente, não conseguimos “andar para trás” em listas ligadas, pois os nós de uma lista ligada sabem somente quem é o próximo elemento. Nas listas duplamente ligadas, os nós sabem quem é o próximo elemento e também quem é o elemento anterior, o que permite a navegação reversa.
Para essa indicação, os nós também passam a apontar quem é o nó anterior.
Podemos representar uma lista duplamente ligada com dois nós na ilustração abaixo:
Podemos concluir que…
As listas são uma das principais estruturas de dados. Muito utilizada em diversos tipos de soluções, estas estruturas garantem a organização sequencial dos dados. Neste artigo vimos o que é e como funcionam as listas e no próximo veremos o que é e como funcionam as pilhas.
Até lá! ;)
