O que é uma estrutura de dados?

As estruturas de dados combinam tipos de dados primitivos, como números, caracteres, booleanos e inteiros em um formato coesivo. Juntos, cada um desses tipos de dados primitivos possui apenas um valor único. Quando combinados em uma estrutura de dados, permitem operações com os dados de nível superior, como classificação, pesquisa, inserção e exclusão.

Por exemplo, considere uma equipe de vendas que deseja acompanhar os números diários de vendas. Em vez de fazer o registro de cada ponto de dados separadamente, a equipe poderia armazenar esses dados em um tipo de estrutura de dados chamada "matriz". (Para obter mais informações, consulte "Tipos de estruturas de dados").

No Python, a matriz pode ter esta aparência:

daily_sales = [500, 800, 600, 1200, 950]

O uso de uma matriz permite que a equipe mantenha todos esses dados juntos, recupere facilmente pontos de dados quando necessário e execute funções em elementos individuais e em toda a matriz.

Os programadores de computador dependem de estruturas de dados para criar aplicações eficazes. Nos campos da ciência da computação e ciência de dados, as estruturas de dados são essenciais para sistemas operacionais, bancos de dados, sites, gráficos, análise de dados, blockchain, aplicações de aprendizado de máquina (ML) e muito mais.

Como as estruturas de dados são fundamentais para escrever um código eficaz, elas geralmente estão entre as primeiras lições ensinadas aos iniciantes em programação. Elas também são um assunto comum em perguntas de entrevistas para candidatos a vagas de emprego em programação de computadores.

As estruturas de dados são importantes porque facilitam o processamento de conjuntos grandes e complexos de informações pelos computadores. Ao organizar logicamente os elementos de dados, as estruturas de dados aumentam a eficiência do código de computador e tornam o código mais simples de entender.

Os programadores usam estruturas de dados para melhorar a velocidade e a força dos algoritmos, que são conjuntos de instruções para concluir uma tarefa de computação. Na programação de computadores, essa combinação é conhecida como "DSA" para "estruturas e algoritmos de dados." A DSA ajuda os programadores a lidar com os desafios gêmeos da complexidade do tempo e da complexidade do espaço.

Complexidade de tempo é uma medida de quanto tempo um algoritmo leva para completar uma tarefa com base na quantidade de entrada. Complexidade de espaço é uma medida de quanta memória o algoritmo usa com base na quantidade de entrada.

Usando a métrica matemática notação Big O, os programadores podem medir a complexidade do espaço e do tempo. Eles podem então determinar quais estruturas de dados e algoritmos fornecem o tempo de execução mais rápido e mais eficiência de espaço para uma tarefa específica.

As estruturas de dados também desempenham um papel importante na programação dinâmica, uma técnica para resolver rapidamente problemas complexos.

A programação dinâmica usa recursão para separar um problema em componentes menores. Em seguida, o programa encontra soluções para esses componentes e remonta as subsoluções em uma solução completa para o problema original.

As estruturas de dados permitem a programação dinâmica, dando ao programa uma maneira de armazenar e recuperar cada subsolução e mantendo os elementos de dados organizados logicamente durante o processo.

Por exemplo, os valores calculados podem ser mantidos em uma matriz. Em vez de recalcular esses valores quando for a hora de formular a solução completa, o programa pode recuperá-los da matriz.

Com esses recursos, os programadores economizam tempo e resolvem problemas com mais eficiência.

As estruturas de dados são divididas em duas categorias: lineares e não lineares.

Em uma estrutura de dados linear, os dados são organizados em uma linha, com cada elemento de dados colocado um após o outro em sequência. Essa disposição simplifica percorrer e acessar os elementos em ordem.

Estruturas de dados lineares são consideradas diretas e simples de implementar. As estruturas de dados comuns nessa categoria incluem matrizes, listas vinculadas e filas.

Em uma estrutura de dados não linear, a lógica organizacional é algo diferente de uma disposição linear e sequencial. Por exemplo, os pontos de dados podem ser ordenados hierarquicamente ou conectados em uma rede.

Como não estão conectados uns aos outros em uma única linha, os elementos em uma estrutura não linear não podem ser percorridos e acessados em uma única execução, como acontece em uma estrutura de dados linear. Exemplos de estruturas de dados não lineares incluem árvores e gráficos.

Existem vários tipos de estruturas de dados que os programadores podem usar, dependendo dos sistemas que estão criando e do que precisam fazer com os dados. As estruturas de dados comuns incluem:

• Matrizes
• Filas
• Stacks
  
• Listas vinculadas
• Árvores
• Gráficos
• Hash 

As matrizes são um dos tipos de estruturas de dados mais básicos e amplamente utilizados. Elas armazenam itens de dados de um tipo semelhante em locais de memória adjacentes. Essa estrutura permite que itens do mesmo tipo sejam facilmente localizados e acessados.

Usos: os usos comuns das matrizes incluem a classificação, o armazenamento, a pesquisa e o acesso a dados. As matrizes também podem ser usadas como base para implementar outras estruturas de dados, como filas e stacks.

Exemplo: uma matriz das pontuações médias de satisfação do cliente de uma central de atendimento a cada dia pode ter esta aparência:

average_customer_score = [4, 3.5, 3.7, 4.1, 3.4, 4.9]

Uma estrutura de dados de fila executa operações de dados em uma ordem predeterminada chamada "FIFO" ("primeiro a entrar, primeiro a sair"). Isso significa que o primeiro item de dados a ser adicionado será o primeiro a ser removido. Os programadores geralmente usam essa estrutura de dados para criar filas de prioridade, que são semelhantes às listas de espera.

Usos: as estruturas de dados de fila podem ser usadas para determinar a próxima música em uma lista de reprodução, o próximo usuário a ter acesso a uma impressora compartilhada ou a próxima chamada a ser atendida em uma central de atendimento.

Exemplo: clientes esperando para falar com um representante de central de atendimento podem ser colocados em uma fila como esta:

queue = [customer 1, customer 2, customer 3]

Quando um representante está disponível, ele se conecta automaticamente ao primeiro cliente na fila, que é removido da lista. Agora, a fila fica assim:

queue = [customer 2, customer 3]

Semelhante às filas, uma estrutura de dados de stack executa operações de dados em uma ordem predeterminada. No entanto, em vez de FIFO, as stacks usam o formato "LIFO", que significa "último a entrar, primeiro a sair". O último item de dados a ser adicionado será o primeiro a ser removido.

Usos: stacks podem ser usadas para ajudar a garantir a abertura e o fechamento corretos de colchetes ou tags em códigos de computador, rastrear o histórico recente do navegador ou desfazer operações recentes em uma aplicação.

Exemplo: muitos aplicativos usam stacks para acompanhar as ações do usuário, para que elas possam ser desfeitas com facilidade. Por exemplo, um editor de texto pode manter uma stack assim:

recent_actions = [typing ‘.’, space, typing ‘T’]

Quando o usuário pressiona o botão "desfazer", a ação mais recente na stack — "digitar 'T'" é desfeita. Agora, a stack fica assim:

recent_actions = [typing ‘.’, space]

As listas vinculadas armazenam itens de dados em uma ordem linear, com cada item conectado ao próximo item na lista. Essa estrutura facilita a inserção de novos itens ou a exclusão de itens existentes sem a necessidade de deslocar toda a coleção de dados.

Usos: as listas vinculadas são frequentemente usadas para inserções e exclusões frequentes em cenários, como históricos de navegadores da web, listas de reprodução de players de mídia e desfazer ou refazer operações em aplicações.

Exemplo: uma versão simplificada de uma lista vinculada de vídeos em um player de mídia pode ter a seguinte aparência:

Video 1 – Video 2 – Video 3

Cada objeto na lista aponta para o próximo; portanto, quando o Vídeo 1 terminar, ele direcionará o player de mídia para iniciar o Vídeo 2. 

Uma estrutura de dados em árvore, às vezes chamada de árvore de prefixos, é útil para estabelecer relações hierárquicas entre elementos de dados. Um único nó principal fica no topo da estrutura em árvore, com subnós secundários ramificando-se em níveis subsequentes abaixo dele.

Diferentes classes de árvores, como árvores de pesquisa binária, árvores AVL e árvores B, têm propriedades diferentes e são compatíveis com funções diferentes. Por exemplo, em uma árvore de pesquisa binária, cada nó tem no máximo dois filhos. Essa estrutura ajuda na compatibilidade com pesquisas rápidas de conjuntos de dados. 

Usos: as árvores são frequentemente usadas para representar hierarquias em mapas organizacionais, sistemas de arquivos, sistemas de nomes de domínio, indexação de banco de dados e árvores de decisão em aplicações de aprendizado de máquina.

Exemplo:

Uma estrutura de dados de gráfico organiza as relações entre diferentes objetos usando vértices e edges. Os vértices são pontos de dados "representados" por pontos, e edges são linhas que conectam os vértices.

Por exemplo, em um mapa, as cidades seriam vértices, e as estradas que as conectam seriam edges. No Facebook, os usuários seriam vértices, e as amizades que os conectam seriam edges.

Usos: as estruturas de dados gráficas são frequentemente usadas com algoritmos de pesquisa que buscam dados em redes complexas de relacionamentos. Exemplos comuns são pesquisas em largura, que pesquisam dados nível por nível, e pesquisas em profundidade, que detalham vários níveis de dados para encontrar informações.

Exemplo:

Uma estrutura de dados de hash, às vezes chamada de "tabela de hash" ou "mapa de hash", usa uma função de hash para armazenar valores de dados. A função de hash cria um hash, que é uma chave digital exclusiva que corresponde à localização de um valor de dados específico na memória.

A tabela de hash contém um índice pesquisável de cada par de valores de hash e dados, o que facilita e agiliza o acesso, a adição e a remoção de dados da tabela.

Usos: estruturas de dados de hash podem ajudar a recuperar rapidamente dados de listas telefônicas, dicionários e diretórios de pessoal. Podem também ser usados para indexar bancos de dados, armazenar senhas e equilibrar a carga de sistemas de TI.

Exemplo: uma versão simplificada de uma tabela de hash que organiza a lista de contatos de um smartphone pode ter a seguinte aparência:

A função de hash mapeia cada chave para o índice apropriado. Assim, quando um usuário insere uma chave (o nome de um contato), a tabela de hash retorna o valor associado ao mesmo índice (o número do contato).

As estruturas de dados são críticas no projeto de aplicações de software porque implementam as formas concretas de tipos de dados abstratos.

Um tipo de dados abstrato é um modelo matemático que classifica como um tipo de dados se comporta e as operações que podem ser executadas sobre ele. Por exemplo, o tipo de dado abstrato de uma fila define o comportamento da fila (seguindo o princípio do FIFO). A estrutura de dados da fila fornece uma maneira de formatar dados em uma fila, de modo que um programa de computador aplique o princípio FIFO a esses dados.

Muitas linguagens de programação, como Python, Java e JavaScript, incluem estruturas de dados integradas para ajudar os desenvolvedores a trabalhar com mais eficiência.

Os casos de uso comuns para estruturas de dados em programas de computador incluem:

• Armazenamento e organização de dados
• Indexação
• Troca de dados
• Pesquisa
• Escalabilidade

As estruturas de dados podem armazenar dados de forma lógica e eficiente com altos níveis de persistência de dados, para que os dados permaneçam facilmente acessíveis a partir de bancos de dados e de outras aplicações. As estruturas de dados também podem fornecer uma organização lógica para grandes quantidades de dados, para que eles possam ser classificados, ordenados e processados com mais facilidade.

Por exemplo, um site pode usar listas vinculadas para armazenar registros de atividades do usuário. As listas podem registrar os eventos em ordem cronológica, e os links entre os eventos podem ajudar a criar uma imagem completa do que o usuário faz em cada sessão.  

As estruturas de dados podem indexar informações mapeando valores de dados para itens de dados correspondentes em um banco de dados, facilitando a localização e o acesso a esses registros de dados.

Por exemplo, um site de comércio eletrônico pode usar uma tabela de hash para indexar produtos em categorias. Quando um usuário deseja visualizar apenas uma categoria, o site pode usar o valor de hash para recuperar rapidamente todos os produtos relacionados, em vez de pesquisar no banco de dados de cada produto.

As estruturas de dados organizam os dados para que possam ser facilmente compartilhados entre aplicações. Por exemplo, muitos aplicativos usam filas para gerenciar e enviar pacotes por protocolos como TCP/IP. As filas ajudam a garantir que os pacotes sejam enviados e recebidos na ordem em que são criados. 

Ao organizar os dados de modo que sejam mais simples de entender pelas aplicações e pelos usuários finais, as estruturas de dados facilitam a pesquisa e a localização de dados.

Por exemplo, estruturas de dados gráficas podem facilitar para os usuários encontrarem pessoas que conhecem em sites de redes sociais. As estruturas de dados dos gráficos registram as relações entre os vértices ou os nós. Algoritmos de busca podem seguir conexões de nó a nó para localizar usuários relacionados com eficiência.

As estruturas de dados apoiam a escalabilidade do sistema, ajudando os programas de computador a processar grandes conjuntos de dados, resolver problemas complexos e usar os recursos de forma mais eficiente.

Por exemplo, tanto as tabelas de hash quanto as estruturas de árvore podem facilitar a localização de informações relevantes em grandes conjuntos de dados. Em vez de inspecionar cada elemento, os sistemas só precisam usar a chave certa ou seguir o caminho certo na árvore. Isso ajuda a manter o alto desempenho, pois o sistema não precisa usar muitos recursos para pesquisar em grandes quantidades de dados.