Lista Ligadas - Parte 4

Neste post vamos examinar as Listas Lineares, com destaque para as Pilhas e Filas.
Listas Lineares

Definição

Listas Lineares são listas que apresentam somente uma relação de adjacência. Em uma lista linear existe um primeiro elemento e um último elemento, todos os demais elementos possuem um elemento anterior e um elemento seguinte.

Operações Básicas

As operações básicas que vamos examinar são:

• Inserir um elemento em uma lista
• Remover um elemento de uma lista
• Percorrer os elementos de uma lista

Listas Lineares Especializadas

Existem dois tipos especializados de listas lineares que são encontrados com freqüência:

• Uma pilha é uma lista onde todas as inserções e remoções são sempre feitas na mesma ponta. Desta forma, o item removido é sempre o que foi inserido mais recentemente. Por isso, as pilhas são à vezes chamadas de LIFO (last in first out, último a entrar primeiro a sair). Você pode visualizar este tipo de lista como uma pilha de caixas:

• Uma fila é uma lista onde todas as inserções são sempre feitas em uma ponta e as remoções são sempre feitas na outra ponta. Desta forma, o item removido é sempre o que foi inserido a mais tempo. Por isso, as filas são à vezes chamadas de FIFO (first in first out, primeiro a entrar primeiro a sair). Você pode visualizar este tipo de lista como uma fila de pessoas:

Alocação Seqüencial

A maneira mais simples e óbvia de implementar uma lista é mantendo os elementos seqüencialmente na memória. Podemos fazer isto tanto usando um vetor alocado estaticamente como uma área alocada dinamicamente.

Um exemplo de alocação sequencial estática para uma lista genérica:

int lista [10];  // área para guardar a lista
   //    lista pode ter até 10 elementos
int tamlista;  // número de elementos atualmente na lista

// inicia lista
void IniciaLista ()
{
 tamlista = 0; // lista está vazia
}

// Insere um elemento na lista na posição pos
// (as posições são numeradas de 0 a tamlista-1)
int Insere (int pos, int elemento)
{
 int i;

 if (tamlista == (sizeof(lista)/sizeof(int)))
   return FALSE; // lista cheia
 if ((pos <> tamlista))
   return FALSE; // posicao invalida
 if (pos == tamlista)
 {
   // inserir no final
   lista[tamlista++] = elemento;
 }
 else
 {
   // inserção no meio, mover os elementos seguintes
   for (i = tamlista; i > pos; i--)
     lista [i] = lista [i-1];
   lista[pos] = elemento;
   tamlista++;
 }
 return TRUE;
}

A rotina de inserção acima mostra uma desvantagem da alocação sequencial: é preciso mover os elementos na memória quando é feita uma inserção ou remoção.

Obs: no caso de filas e pilhas, onde as inserções e remoções são feitas nos extremos, é possível evitar a movimentação dos elementos.

Por outro lado, o acesso aleatório as elementos é muito simples. A rotina abaixo calcula a soma de todos os elementos da lista:

int Soma ()
{
 int i, total;
 for (i = total = 0; i < tamlista; i++)
   total += lista[i];
 return total;
}

No próximo post vamos examinar as Listas Ligadas Simples.