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ógicaDonald Knuth, The Art of Computer Programming e o Disjoint.Bernard A. Galler and Michael J. Fischer.

Tipos comuns de estruturas de dados vinculadas

Listas ligadas

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'''.http://www.cs.toronto.edu/~hojjat/148s07/lectures/week5/07linked.pdf Ficheiro:Singly-linked-list.svg Uma lista ligada com três nós contendo dois campos: um valor inteiro, e uma referência para o próximo nó centro|miniaturadaimagem|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

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 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.

Ver também Lista de estruturas de dados Middleware

Referências

Categoria:Estruturas de dados Categoria:Tipos abstratos de dados