Lista Ligada
Referência : Ribeiro, P. (2012), WikiCiências, 3(06):0627
Autor: Pedro Ribeiro
Editor: Fernando M. A. Silva
Uma lista ligada é uma estrutura de dados que representa uma sequência de valores do mesmo tipo. É uma das estruturas de dados mais simples e mais utilizadas.
Um elemento de uma lista ligada é tipicamente constituído por dois campos, um contendo um valor do elemento dessa posição e outro contendo uma referência (ou ligação) para o próximo elemento da lista. Esta forma de organização é exemplificada na figura seguinte, que ilustra uma lista ligada representando uma sequência de quatro números inteiros.
Conceitos
Cada elemento da lista pode também ser chamado de nó. Todos os elementos têm os mesmos campos, que são usualmente dois:
- Valor (ou Item, ou Contentor): contém os dados referentes a esse elemento da lista. Por exemplo, nas imagens desta entrada os dados são números inteiros. Num outro caso, o tipo dos dados guardados poderia ser diferente.
- Próximo: uma referência (ou ligação ou apontador) para o próximo elemento da lista.
Ao primeiro elemento da lista costuma chamar-se a cabeça. Uma referência à lista ligada pode ser portanto uma referência à sua cabeça. Ao último elemento costuma chamar-se cauda. O próximo da cauda é tipicamente uma referência nula, indicando a inexistência de um elemento seguinte.
Existem algumas variantes possíveis no conceito de listas ligadas. Por exemplo, é possível que a cauda aponte novamente para a cabeça da lista, naquilo que se denomina de lista circular, tal como é exemplificado na figura seguinte.
É também possível que cada elemento da lista contenha mais um campo chamado de anterior que aponta para o elemento anterior. Neste caso temos aquilo que se denomina de lista duplamente ligada, tal como é exemplificado na figura seguinte.
Aplicações
Uma lista ligada pode ser usada como a implementação de vários tipos abstratos de dados, tais como filas, pilhas ou dicionários.
Por comparação com um vetor, outra da estruturas de dados mais usadas, uma lista ligada apresenta várias diferenças. Pela positiva, a inserção e remoção de elementos não implica uma reorganização de todos os dados da estrutura, uma vez que os elementos não precisam de ficar armazenados em posições consecutivas da memória. Pela negativa, uma lista ligada não permite o acesso direto a um elemento de qualquer posição, sendo necessário percorrer a própria lista para aceder ao elemento desejado.
Criada em 08 de Maio de 2012
Revista em 29 de Maio de 2012
Aceite pelo editor em 02 de Junho de 2012
