Estrutura de dados vinculada
 | As referências deste artigo necessitam de formatação. (Agosto de 2020) |
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[1] e o Disjoint.[2]
Tipos comuns de estruturas de dados vinculadas
[editar | editar código-fonte]Listas ligadas
[editar | editar código-fonte]
Ver artigo principal: Lista ligadaUma 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'.[3]
Uma lista ligada com três nós contendo dois campos: um valor inteiro, e uma referência para o próximo nó
Exemplo em Java
[editar | editar código-fonte]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
[editar | editar código-fonte]Ver artigo principal: Árvore de buscaUma á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
[editar | editar código-fonte]Listas ligadas e arrays
[editar | editar código-fonte]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 logb 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.