ESTRUTURA DE DADOS

INSTITUTO FEDERAL DE EDUCAÇÃO, CIÊNCIA E TECNOLOGIA DO PIAUÍ - IFPI
CAMPUS: TERESINA ZONA SUL
CURSO: I LINCENCIATURA PLENA EM INFORMATICA - PARFOR
DISCIPLINA: ESTRUTURA DE DADOS
PROFESSOR: JEFERSON

Listas Encadeadas

LUSEILDES DA SILVA LIAL

THE, 2014

Listas Encadeadas
Principais conceitos;
Exemplos em Java:
Qual a vantagem e desvantagem do uso listas sobre vetor;
Como implementar uma lista circular;

Definição: Numa lista encadeada, para cada novo elemento inserido na estrutura, alocamos um espaço de memória para armazená-lo. Desta forma, o espaço total de memória gasto pela estrutura é proporcional ao número de elementos nela armazenado. No entanto, não podemos garantir que os elementos armazenados na lista ocuparão um espaço de memória contíguo, portanto não temos acesso direto aos elementos da lista. Para que seja possível percorrer todos os elementos da lista, devemos explicitamente guardar o encadeamento dos elementos, o que é feito armazenando-se, junto com a informação de cada elemento, um ponteiro para o próximo elemento da lista. A Figura que ilustra o arranjo da memória de uma lista encadeada.

A estrutura consiste numa seqüência encadeada de elementos, em geral chamados de nós da lista. A lista é representada por um ponteiro para o primeiro elemento (ou nó). Do primeiro elemento, podemos alcançar o segundo seguindo o encadeamento, e assim por diante. O último elemento da lista aponta para NULL, sinalizando que não existe um próximo elemento.

Uma lista encadeada é uma estrutura dinâmica que pode ser utilizada para armazenar um conjunto de dados Junto a cada elemento deve-se armazenar o endereço para o próximo elemento (elementos encadeados)
Elemento + ponteiro = nó da lista Diferentemente de vetores, elementos geralmente não são armazenados em espaços contíguos de memória Caso não exista próximo elemento, o ponteiro para o próximo elemento é NULL. Para cada novo elemento