listas encadeadas

LISTAS ENCADEADAS OU
NÃO- SEQÜENCIAIS

Estrutura de Dados

Listas Lineares
• Como visto anteriormente, as operações básicas para o “nosso” TAD Lista Linear são:
–
–
–
–
–

FLVazia
Vazia
Retira
Insere
Imprime

• A implementação através de arrays possui a grande desvantagem de ter que prever a quantidade máxima de elementos da lista antes de sua utilização efetiva
Estrutura de Dados

Implementação de Listas com
Ponteiros

• Os elementos (nós ou células) da lista são registros com um dos componentes destinado a guardar o endereço do seu sucessor

x0

x1

x2

...

xn

NULL

• Desta forma, cada item da lista é encadeado com o seguinte através de uma variável do tipo Ponteiro
• Os nós da lista estão dispostos de maneira aleatória na memória (posições não obrigatoriamente contíguas) e são interligados por ponteiros: por isso é também chamada de lista não-seqüencial
Estrutura de Dados

A Lista Encadeada
• Assim, cada nó (ou célula) deve conter um item da lista e um “campo extra” para um apontador para o nó seguinte
• A alocação dinâmica de memória é a técnica utilizada: as posições de memória são alocadas
(desalocadas) quando são necessárias
(desnecessárias)
• Como visto, C faz a gerência de memória através das declarações malloc e free
• Existem outras implementações: simplesmente ou duplamente encadeadas e listas encadeadas circulares; com ou sem nós sentinela
Estrutura de Dados

Vantagens e Desvantagens
• Desvantagens
1. Acesso indireto aos elementos
2. Tempo variável para acessar os elementos (depende da posição do elemento)
3. Gasto de memória maior pela necessidade de um novo campo para o ponteiro

• Vantagens
1. A inserção e remoção de elementos podem ser feitas sem deslocar os itens seguintes da lista
2. Não há necessidade de previsão do número de elementos da lista; o espaço necessário é alocado em tempo de execução
3. Facilita o gerenciamento de várias listas (fusão, divisão,...)