5 principais estruturas de dados

O que são estruturas de dados?

Uma estrutura de dados é uma solução para organizar informações, permitindo tanto o armazenamento quanto a recuperação de itens. Elas podem ser classificadas como abstratas ou concretas.

• Estruturas de dados abstratas são conceitos ou modelos que descrevem como os dados podem ser organizados e manipulados.

• Estruturas de dados concretas são as implementações reais dessas abstrações, que determinam a eficiência e a forma de armazenamento e manipulação dos dados.

Estruturas de dados básicas

Existem diversas estruturas de dados, cada uma com um propósito específico e ideal para diferentes cenários de implementação. Neste post, vou apresentar cinco delas: Arrays, Listas Encadeadas (Linked Lists), Filas, Pilhas e Tabelas Hash.

Arrays

Um array é uma estrutura de dados linear que armazena e organiza elementos em posições sequenciais. Ao declarar um array, é necessário especificar o número de elementos que ele armazenará, pois o array aloca um bloco contínuo de memória para armazenar esses dados.

Dessa forma, é possivel recuperar um elemento pelo seu índice numérico, que indica a posição do elemento dentro do array. Os índices geralmente começam em zero, o que significa que o primeiro elemento está no índice 0, o segundo no índice 1, e assim por diante.

Quando usar:

• Se você precisa de acesso rápido aos elementos por índice (tempo constante O(1)).
• Quando o tamanho dos dados é conhecido e fixo ou não mudará com frequência.
• Para armazenar uma coleção de elementos homogêneos (como inteiros, strings).

Vantagens:

• Acesso direto aos elementos e eficiente em termos de memória se o tamanho for fixo.

Desvantagens:

• Redimensionar arrays dinâmicos pode ser custoso. Operações de inserção e remoção no início ou no meio do array são lentas (O(n)).

Aplique o seu conhecimento!

Listas Encadeadas (Linked Lists)

Uma lista encadeada armazena uma sequência de elementos, onde cada elemento é um nó que contém dois componentes principais: seu dado (informação que o nó armazena) e um ponteiro (referência ao próximo nó na lista. Se for o último nó, essa referência será nula, indicando o final da lista.).

O primeiro elemento da lista encadeada é chamado de cabeça e a lista é acessada começando por este nó.

Além do tipo de lista encadeada explicada acima, existe a lista duplamente encadeada, nela além da o ponteiro que aponta para o nó seguinte, existe também a referência ao nó anterior.

Quando usar:

• Quando o tamanho dos dados é dinâmico e você precisa de uma estrutura que possa crescer ou diminuir com frequência.
• Se as inserções e remoções no início ou no meio da lista são comuns.

Vantagens:

• Inserção e remoção são eficientes (O(1)) nas extremidades.

Desvantagens:

• Acesso aos elementos é mais lento (O(n)) em comparação com arrays, pois você precisa percorrer os nós.

Aplique o seu conhecimento!

Filas

A ideia dessa estrutura de dados é bem intuitiva. Ela segue o princípio FIFO (First In, First Out), ou seja, o primeiro elemento inserido na fila será o primeiro a ser removido, como em uma fila de supermercado.

Nela, o acesso aos elementos é restrito as duas extremidades, você só pode acessar o elemento da frente (a cabeça) para remoção ou no final (a cauda) para inserção.

Quando usar:

• Quando você precisa processar os dados em ordem de chegada.
• Ideal para sistemas de espera, processamento de tarefas assíncronas ou buffer de dados.

Vantagens:

• Operações de inserção e remoção são rápidas (O(1)) nas extremidades.

Desvantagens:

• Acesso direto aos elementos intermediários é raro e custoso (O(n)).

Aplique o seu conhecimento!

Pilhas

Uma pilha tem o comportamento semelhante a uma pilha de pratos: o último prato que você coloca no topo é o primeiro que você retira. Essa estrutura de dados linear pode seguir os princípios LIFO (Last In First Out) ou FILO (First In Last Out).

Nela o acesso aos dados também é restrito, você só pode acessar os elementos através de uma das duas extremidades (cabeça ou calda), a depender do princípio aplicado (LIFO ou FILO). Na pilha são executadas três operações básicas:

• Push: Inserir um elemento no topo da pilha.
• Pop: Remover e retornar o elemento do topo da pilha.
• Peek (ou Top): Verificar o elemento no topo da pilha sem o remover.

Quando usar:

• Para problemas onde a ordem inversa dos elementos importa.
• Usado em algoritmos de recursão, backtracking, gerenciamento de chamadas de função (call stack).

Vantagens:

• Inserções e remoções no topo da pilha são rápidas (O(1)).

Desvantagens:

• Sem acesso direto a elementos que não estão no topo.

Aplique o seu conhecimento!

Tabelas Hash

Nessa estrutura de dados, para cada elemento é associado uma chave. Seu funcionamento se baseia em uma função hash, que é responsável por transformar uma chave em um índice, indicando a posição na tabela onde o valor associado àquela chave será armazenado. Entretanto, a função hash pode gerar o mesmo índice para diferentes chaves, causando uma colisão. É possível tratar essa situação com duas abordagens comuns, o encadeamento e o endereçamento aberto. No encadeamento, cada posição da tabela contém uma lista de pares chave-valor, e se uma colisão ocorrer, o novo par é adicionado a essa lista. No endereçamento aberto, a tabela procura a próxima posição livre para armazenar o novo par, seguindo uma sequência predefinida.

Quando usar:

• Se você precisa de acesso rápido a elementos por chave (tempo médio O(1) para buscas, inserções e deleções).
• Ideal para armazenamento de grandes conjuntos de dados quando o acesso por chave é frequente, como dicionários ou caches.

Vantagens:

• Busca extremamente eficiente quando a função hash é bem definida.

Desvantagens:

• Colisões na tabela hash podem aumentar o tempo de operação. - Pode consumir mais memória devido ao overhead de armazenamento da função hash.

Aplique o seu conhecimento!