Listas Encadeadas

Voltar para DAS5102 Fundamentos da Estrutura da Informação

C O N T E Ú D O     I N C O M P L E T O

Acessar: http://das.ufsc.br/~abdala/DAS5102/TEO_ListasEncadeadas.pdf

Listas Encadeadas (Linked Lists) =

As listas ou listas encadeadas são a estrutura de dados mais simples concebível excetuando-se naturalmente os arrays. Listas encadeadas nada mais são que uma seqüência de células ligadas ou encadeadas umas as outras. As células de uma lista encadeada são compostas de dois elementos cada. O primeiro elemento é o dado efetivo a ser armazenado e o segundo compraz uma referência para o próximo elemento da lista. A figura abaixo apresenta um modelo esquemático da célula de uma lista encadeada assim como a sua estrutura de dados.

FIGURA 1

Quando lidamos com arrays, devemos saber de antemão ou em tempo de compilação qual o tamanho ou quantidade de bytes a ser alocados para o array. Como foi visto em sala de aulas via exemplos, existem muitas situações em programação onde a quantidade exata de memória a ser alocada não é conhecida na criação do programa devendo ser definida durante sua execução. Para estes casos pode-se alocar a memória necessária via alocação dinâmica de memória. No entanto ainda existem outros casos em que mais memória deve ser alocada para armazenar os dados do programa a medida que o programa vai sendo utilizado. Este é um dos casos em que a utilização de listas ligadas é mais indicada do que a utilização de arrays estáticos ou dinâmicos. Outra vantagem das listas ligadas é que não existe nenhuma restrição indicando que as células que as compõem devem estar alocadas sequencialmente na memória tal como ocorre com arrays ou memória alocada dinamicamente via malloc. Em verdade, cada célula pode existir em diferentes regiões a memória.

FIGURA 2

Figura 2 – representação gráfica de uma lista ligada

A lista ligada é composta, como foi dito anteriormente, por células de informação. Cada célula contém um item de dado e um ponteiro para a próxima célula da lista. O final da lista é marcado pela última célula da lista apontando para o ponteiro nulo (NULL).

Uma lista ligada vazia nada mais é que um ponteiro apontando para NULL.

Por fim, pode-se imaginar que o requisito imposto de um ponteiro apontando para o próximo elemento de cada elemento da lista seja um uso desnecessário de memória. No entanto vale lembrar que em geral as itens armazenados em uma lista encadeada são muito maiores que os tipos atômicos de dados, tornando assim a proporção entre memória de dados e ponteiros relativamente negligenciável.

Listas com e sem cabeçalho

Listas ligadas podem ser organizadas de duas maneiras distintas.

Lista com cabeçalho

O conteúdo da primeira célula não importa, marca apenas o início da lista. A primeira célula está sempre no mesmo lugar na memória, mesmo que a lista fique vazia. Digamos que LISTA é o endereço da primeira célula. Então LISTA->prox == NULL se e somente se a lista está vazia. Para criar uma lista vazia, basta dizer

1celula c, *lista;
2c.prox = NULL;
3lista = &c;

ou

1celula *lista;
2lista = malloc (sizeof (celula));
3lista->prox = NULL;

Lista sem cabeçalho: O conteúdo da primeira célula é tão relevante quanto o das demais. Nesse caso, a lista está vazia se o endereço de sua primeira célula é NULL. Para criar uma lista vazia basta fazer

1celula *lista;
2lista = NULL;

Itens podem ser inseridos em qualquer ponto da lista ligada:

• Início;
• Meio;
• Fim;

Inserção no Início da lista

Na inserção de elementos no início da lista deve-se observar se a mesma possui ou não um cabeçalho. Para o caso em que a lista possua cabeçalho, deve-se proceder da seguinte forma:

1. Criar a nova célula a ser inserida;
2. Apontar o ponteiro prox da célula sendo inserida para a primeira célula da lista original (new_cel->prox = head->prox);
3. Apontar o ponteiro prox do cabeçalho para a célula a ser inserida head->prox = new_cel->prox.

FIGURA 3

Figura 2 Inserção no início de uma lista sem cabeçalho

<syntaxhighlight lang=c line> void insereInicio (celula *head, celula *cel) {

   cel->prox = head->prox;
   head->prox = cel->prox;

}

Roteiro

Objetivos

• Revisar os conceitos de listas encadeadas vistos em sala de aula;
• Treinar métodos de inserção, remoção e pesquisa em listas encadeadas.

Exercício

Crie uma TAD que implemente uma lista encadeada com as seguintes características:

• A lista deve ser capaz de acomodar strings(o campo dado da struct deve ser char*);
• A lista deve possuir uma célula de cabeçalho;
• Escreva uma função para inserir células no início da lista;
• Escreva uma função para inserir células no fim da lista;
• Escreva uma função para inserir células em uma posição qualquer da lista (posição especificada como um parâmetro, tal como na quinta posição a partir da início);
• Escreva três funções de remoção (inicio, fim e posição arbitrária);
• Escreva uma função que receba uma string como parâmetro e retorne uma lista encadeada onde cada célula da lista deve acomodar uma das palavras especificadas na string (use espaços como separador entre palavras);
• Escreva uma função que percorra todas as células da lista listando seus conteúdos e respectivos tamanhos de cada string;
• Escreva uma função que receba uma lista encadeada como parâmetro e retorne outra lista encadeada com todas as strings contidas na lista em ordem inversa.