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.