sexta-feira, novembro 09, 2007

Listas Ligadas - Parte 5

Listas Ligadas

As listas ligadas são uma alternativa às listas sequenciais. Como os elementos não estão em posições sequenciais é necessário acrescentar aos elementos informações que permitam percorrer a lista sequencialmente. Desta forma os elementos são ligados uns aos outros.

Obs.: A forma mais comum de fazer as ligações é através de ponteiros. Entretanto, nada impede de implementar uma lista ligada sobre um vetor alocado estaticamente, usando como link o índice do elemento.

Listas Ligadas Simples

Na sua forma mais simples, uma lista ligada é implementada através de:
  • Um ponteiro para o primeiro elemento da lista
  • Um ponteiro em cada elemento da lista apontando para o próximo elemento
Um valor especial (em C, tipicamente NULL e mais raramente –1) é utilizado para indicar o fim da lista.

As listas ligadas são normalmente representadas graficamente como retângulos (os elementos ou nós), interligados através de setas:

A direção da seta neste diagrama é importante, a origem da seta é um ponteiro que armazena o endereço do elemento na outra ponta. Portanto, é possível percorrer o link apenas no sentido da seta.

O símbolo no final da seta que sai do item 3 (símbolo de aterramento em circuitos elétricos) indica o fim da lista. Em outras palavras, o ponteiro possui o valor especial de fim de lista.

Uma lista vazia é simplesmente

A inserção de um novo item consiste apenas em alterar ponteiros:

Idem para a remoção de um item:

O código abaixo mostra uma implementação simples de lista ligada em C:
// estrutura de um elemento (nó) da lista
typedef struct no_lista
{
int valor; // dado do elemento
struct no_lista *prox; // ponteiro para o elemento seguinte
} NO;

// variavel que aponta para o início da lista
NO *inicio;

// Inicia a lista
void IniciaLista ()
{
inicio = NULL;
}

// Insere um valor na lista na posição pos
int Insere (int pos, int valor)
{
NO *pno, *p;
NO **pant;
int i;

// procura o ponto a inserir
for (i = 0, pant = &inicio, p = inicio;
(i < pos) && (p != NULL); i++)
{
pant = &p->prox;
p = p->prox;
}
if (i != pos)
return FALSE; // posicao invalida
// Insere
pno = malloc (sizeof (NO));
if (pno == NULL)
return FALSE; // faltou memoria
pno->valor = valor;
pno->prox = p;
*pant = pno;
return TRUE; // sucesso
}

// Remove elemento na posição pos
int Remove (int pos)
{
NO *p;
NO **pant;
int i;

// procura o elemento a remover
for (i = 0, pant = &inicio, p = inicio;
(i < pos) && (p != NULL); i++)
{
pant = &p->prox;
p = p->prox;
}
if ((i != pos) || (p == NULL))
return FALSE; // posicao invalida

// Remove
*pant = p->prox;
free (p);
return TRUE; // sucesso
}

// Soma os elementos da lista
int Soma ()
{
int total;
NO *p;

for (p = inicio, total = 0; p != NULL; p = p->prox)
total += p->valor;
return total;
}
As rotinas de inserção e remoção utilizam um ponteiro (pant) para guardar o endereço da variável que contém o endereço do nó atual. Isto dispensa tratar de forma diferente o caso em que o ponteiro a ser atualizado é o ponteiro para o inicio da lista. Uma forma de melhorar a legibilidade, desperdiçando um pouco de memória, é usar um nó para guardar o ponteiro de início:
NO inicio; // inicio.prox aponta para o primeiro elemento

// Insere um valor na lista na posição pos
int Insere (int pos, int valor)
{
NO *pno, *p;
NO *pant;
int i;

// procura o ponto a inserir
for (i = 0, pant = &inicio, p = inicio.prox;
(i < pos) && (p != NULL); i++)
{
pant = p;
p = p->prox;
}
if (i != pos)
return FALSE; // posicao invalida

// Insere
pno = malloc (sizeof (NO));
if (pno == NULL)
return FALSE; // faltou memoria
pno->valor = valor;
pno->prox = p;
pant->prox = pno;
return TRUE; // sucesso
}
Comparando uma lista sequencial a uma lista ligada, temos:
  • A lista ligada consome memória adicional para os links;
  • É fácil e rápido inserir e remover elementos, pois basta alterar ponteiros;
  • O acesso a um elemento qualquer da lista (acesso randômico) é mais trabalhoso e lento na lista ligada, pois é preciso percorrer os links;
  • O acesso sequencial para frente tem velocidade bastante semelhante;
  • É fácil quebrar e juntar listas, pois basta alterar ponteiros;
  • A estrutura de links da lista ligada leva facilmente a estruturas mais complexas, como uma lista onde os elementos são listas.
Portanto uma lista ligada é apropriada quando são esperadas várias inserções e/ou remoções e o acesso é essencialmente sequencial. Um exemplo é quando se deseja manter ordenada uma lista que sofre seguidas inserções e é pesquisada por busca sequencial.

No próximo post vamos ver as listas duplamente ligadas.

Um comentário:

Filipe disse...

Valeu cara, me salvou na prova de Estruturas de Dados I

XD