Estrutura de dados vinculada

Em ciência da computação, uma estrutura de dados vinculada ou  estrutura de dados ligada é uma estrutura de dados que consiste em um conjunto de registros de dados (nós) ligados entre si e organizados por referências (links ou ponteiros). A ligação entre dados também pode ser chamada de conector.

Estruturas de dados vinculadas incluem listas ligadas, árvores de pesquisa, árvores de expressão, e muitas outras estruturas amplamente utilizadas. Elas são os blocos de construção para muitos algoritmos eficientes, tais como ordenação topológica e o Disjoint.

Tipos comuns de estruturas de dados vinculadas

Listas ligadas

Ver artigo principal: Lista ligada

Uma lista ligada é uma coleção de estruturas (nós) ordenadas não por sua localização física na memória, mas por ligações lógicas que são armazenados como parte dessas estruturas. Não é necessário que essas ligações sejam armazenadas em um local adjacente. Cada estrutura tem um campo de dados e um campo de endereço. O campo de endereço contém o endereço de seu sucessor.

Listas ligadas podem ser simplesmente ligadas ou duplamente ligadas bem como podem ser lineares ou circulares.

Propriedades básicas

• Objetos, chamados de nós, estão ligados em uma seqüência linear.
• Uma referência para o primeiro nó da lista é mantida sempre. Esse nó é chamado de 'cabeça' ou simplesmente head'.

Uma lista ligada com três nós contendo dois campos: um valor inteiro, e uma referência para o próximo nó

Uma lista ligada com um único nó.

Exemplo em Java

Este é um exemplo de uma classe para um Nó que armazena números inteiros em uma implementação em Java de uma lista ligada:

public class IntNode {
     public int value;
     public IntNode link;
     public IntNode(int v) { value = v; }
}

Árvores de busca

Ver artigo principal: Árvore de busca

Uma árvore de busca é uma estrutura de dados em cujos nós de valores podem ser armazenados na forma de um conjunto ordenado, de tal forma, que ao percorrer a árvore de uma dada maneira, os nós são visitados na ordem crescente dos seus valores armazenados.

Propriedades básicas

• Objetos, chamados de nós, são armazenados em um conjunto ordenado.
•  A travessia em-ordem fornece uma ordem crescente de leitura dos dados na árvore.

Vantagens e desvantagens

Listas ligadas e arrays

Comparando com arrays, estruturas de dados ligadas permitem mais flexibilidade na organização de dados e na alocação de espaço. Em arrays, o tamanho do array deve ser especificado de forma precisa no início, o que pode ser um potencial desperdício de memória. Uma estrutura de dados ligada é criada dinamicamente e nunca precisa ser maior do que geralmente o programador necessita. Ela também dispensa a necessidade de supor quanto espaço deve ser alocado antes de utilizá-la. Isto é um recurso chave para evitar o desperdício de memória.

Em um array, os elementos devem estar em uma área de memória contígua. Em uma estrutura de dados ligada, a referência para cada nó dá as informações necessárias para localizar sempre o próximo. Os nós de uma estrutura de dados ligada podem também serem movidos individualmente para diferentes locais, sem afetar as conexões lógicas entre eles, ao contrário dos arrays. Com o devido cuidado, um processo pode adicionar ou excluir nós em uma parte da estrutura enquanto outros processos estão trabalhando em outras partes.

Por outro lado, o acesso a qualquer nó em uma estrutura de dados ligada requer percorrer a cadeia de referências que estão nela armazenados. Se a estrutura tem n nós, e cada nó contém, no máximo, b referências, haverá alguns nós que não poderão ser alcançados em menos que log_b n passos. Para muitas estruturas, o acesso a alguns nós podem exigir pior caso em até n−1 passos. Em contrapartida, arrays permitim o acesso a qualquer elemento com um número de operações constante , independente do número de elementos.

Genericamente, a implementação destas estrutura de dados se dá através de estruturas de dados dinâmicas. A memória pode ser utilizada de forma mais eficiente ao utilizar uma estrutura de dados ligada. Pois a memória é alocada de acordo com a necessidade e quando não é mais necessária, a liberação é feita.

Ver também

• Lista de estruturas de dados
• Middleware