Estrutura de dados

Uma estrutura de dados conhecida como uma tabela hash.

Na ciência da computação, uma estrutura de dados é um formato de organização, gerenciamento e armazenamento de dados que geralmente é escolhido para acesso eficiente aos dados. Mais precisamente, uma estrutura de dados é uma coleção de valores de dados, as relações entre eles e as funções ou operações que podem ser aplicadas aos dados, ou seja, é uma estrutura algébrica sobre dados.

Uso

As estruturas de dados servem como base para tipos de dados abstratos (ADT). O ADT define a forma lógica do tipo de dados. A estrutura de dados implementa a forma física do tipo de dados.

Diferentes tipos de estruturas de dados são adequados para diferentes tipos de aplicativos e alguns são altamente especializados para tarefas específicas. Por exemplo, bancos de dados relacionais geralmente usam índices de árvore B para recuperação de dados, enquanto implementações de compilador geralmente usam tabelas de hash para procurar identificadores.

As estruturas de dados fornecem um meio de gerenciar grandes quantidades de dados de forma eficiente para usos como grandes bancos de dados e serviços de indexação da Internet. Normalmente, estruturas de dados eficientes são a chave para projetar algoritmos eficientes. Alguns métodos formais de design e linguagens de programação enfatizam estruturas de dados, em vez de algoritmos, como o principal fator de organização no design de software. As estruturas de dados podem ser usadas para organizar o armazenamento e a recuperação de informações armazenadas na memória principal e na memória secundária.

Implementação

As estruturas de dados são geralmente baseadas na capacidade de um computador buscar e armazenar dados em qualquer lugar em sua memória, especificado por um ponteiro - uma cadeia de bits, representando um endereço de memória, que pode ser armazenado na memória e manipulado por o programa. Assim, as estruturas de dados de matriz e registro são baseadas na computação dos endereços de itens de dados com operações aritméticas, enquanto as estruturas de dados vinculadas são baseadas no armazenamento de endereços de itens de dados dentro da própria estrutura.

A implementação de uma estrutura de dados geralmente requer escrever um conjunto de procedimentos que criam e manipulam instâncias dessa estrutura. A eficiência de uma estrutura de dados não pode ser analisada separadamente dessas operações. Esta observação motiva o conceito teórico de um tipo abstrato de dados, uma estrutura de dados que é definida indiretamente pelas operações que podem ser realizadas sobre ela e as propriedades matemáticas dessas operações (incluindo seu custo de espaço e tempo).

Exemplos

A hierarquia padrão da linguagem de programação Python 3.

Existem vários tipos de estruturas de dados, geralmente construídas sobre tipos de dados primitivos mais simples. Exemplos bem conhecidos são:

• Um array é um número de elementos em uma ordem específica, tipicamente todo o mesmo tipo (dependendo da linguagem, elementos individuais podem ser forçados a ser o mesmo tipo, ou podem ser de quase qualquer tipo). Elementos são acessados usando um índice inteiro para especificar qual elemento é necessário. Implementações típicas alocam palavras de memória contíguas para os elementos de arrays (mas isso nem sempre é uma necessidade). Os raios podem ser de comprimento fixo ou redimensionáveis.
• A lista vinculada (também chamado) lista) é uma coleção linear de elementos de dados de qualquer tipo, chamados nós, onde cada nó tem um valor, e aponta para o próximo nó na lista vinculada. A principal vantagem de uma lista vinculada sobre um array é que os valores podem sempre ser inseridos e removidos de forma eficiente sem mudar o resto da lista. Certas outras operações, como acesso aleatório a um determinado elemento, são, no entanto, mais lentas em listas do que em arrays.
• Um registro (também chamado tupla ou Estranho) é uma estrutura de dados agregada. Um registro é um valor que contém outros valores, tipicamente em número fixo e sequência e tipicamente indexado por nomes. Os elementos dos registros são geralmente chamados campos ou membros. No contexto da programação orientada a objetos, os registros são conhecidos como estruturas de dados antigas simples para distingui-los de objetos.
• Tabelas de Hash, gráficos e árvores binárias.

Suporte a idiomas

A maioria das linguagens assembly e algumas linguagens de baixo nível, como BCPL (Basic Combined Programming Language), carecem de suporte embutido para estruturas de dados. Por outro lado, muitas linguagens de programação de alto nível e algumas linguagens de montagem de nível superior, como MASM, têm sintaxe especial ou outro suporte integrado para determinadas estruturas de dados, como registros e matrizes. Por exemplo, as linguagens C (um descendente direto de BCPL) e Pascal suportam structs e registros, respectivamente, além de vetores (matrizes unidimensionais) e matrizes multidimensionais.

A maioria das linguagens de programação apresenta algum tipo de mecanismo de biblioteca que permite que implementações de estrutura de dados sejam reutilizadas por diferentes programas. As linguagens modernas geralmente vêm com bibliotecas padrão que implementam as estruturas de dados mais comuns. Exemplos são a C++ Standard Template Library, o Java Collections Framework e o Microsoft.NET Framework.

Linguagens modernas geralmente também suportam programação modular, a separação entre a interface de um módulo de biblioteca e sua implementação. Alguns fornecem tipos de dados opacos que permitem aos clientes ocultar detalhes de implementação. Linguagens de programação orientadas a objetos, como C++, Java e Smalltalk, normalmente usam classes para essa finalidade.

Muitas estruturas de dados conhecidas têm versões simultâneas que permitem que vários threads de computação acessem uma única instância concreta de uma estrutura de dados simultaneamente.