Título: Lista Encadeada
Linguagem: C/C++
S.O.: DOS/Windows
Autor(es): Wenderson Teixeira

Lista Encadeada

Pelo menos uma vez por semana eu recebo um e-mail de alguém perguntando alguma coisa sobre listas encadeadas, e muitas vezes é alguém pedindo para eu fazer o trabalho de escola dele, pois bem, agora chega, resolvi fazer um artigo sobre Lista Encadeadas, por que eu já não aguento mais dar sempre a mesma explicação, e ficar fazendo exemplinhos sobre esse assunto, por isso, se forem me mandar mais um e-mail perguntando sobre isso, por favor certifiquem-se de o assunto não está sendo explicado aqui.



FAQ sobre Listas


O que é uma Lista Encadeada?
Uma Lista Encadeada é uma forma especial de se agrupar dados, onde cada item possui uma referência para o próximo item, como se fosse uma corrente com cada item sendo um dos elos.



Que tipo de dados eu posso guardar em uma Lista Encadeada?
Se a lista for bem implementada, pode-se guardar praticamente qualquer tipo de dado, números inteiros, números em ponto flutuante, cadeias de caracteres, estruturas e até mesmo objetos.



Posso ter múltiplos tipos de dados em uma mesmo lista?
Sim, depende apenas de como a lista for implementada. Se a lista for implementada de forma genérica, onde o dado propriamente dito não fica na lista e sim apenas um ponteiro para o dado em si é mantido, pode-se ter diferentes tipos de dados.



Qual a diferença entre Listas Encadeadas e Listas Comuns?
As Listas Comuns, também chamadas de Vetores ou Matrizes, normalmente são alocadas de forma que se saiba a quantidade máxima de elementos que serão armazenados, e os itens não possuem uma referência para o próximo, pois a lista pode ser percorrida utilizando-se um índice, valor inteiro.
Já as Listas Encadeadas são criadas de forma a armazenar um número indeterminado de itens, pois a cada item inserido a lista cresce para poder suportar o novo item, e uma referência à ele é criada, fazendo-se com que o último item da lista o aponte, seu acesso é feito através de ponteiros e não índices.



Se as Listas Encadeadas são tão boas, porque então se usa Matrizes?
Por diversos motivos, por exemplo, a alocação de Matrizes é mais rápida, pois ocorre apenas uma vez, já nas Lista Encadeadas, a cada elemento inserido, é feita uma alocação, um outro motivo, é que é muito mais fácil gerenciar Matrizes do que Listas Encadeadas, pois este último é um tipo de dado mais complexo.



Como sei qual o início e o final da lista?
Normalmente, mantem-se um ponteiro para o início da lista, pois esta costuma-se ser a única forma de saber o início, já o final pode ser descoberto, percorrendo-se toda a lista até se encontrar um NULL.



Como faço para saber quantos itens tem a lista?
Basta percorrer a lista do começo ao fim, contando os elementos, ou então manter um contador de itens.



Posso ter uma Lista Encadeada guardando dados estáticos?
Sim, pode, mas não tem muito sentido, já que a maior característica da lista é a possibilidade de se fazer tudo dinamicamente.



Implementação


Para exemplificar tudo o que foi dito, vamos implementar uma série de rotinas para o gerenciamento de um Lista Encadeada genérica, e logo em seguida vamos implementar um programa de exemplo que utilize estas rotinas.



Definindo os tipo e cabeçalhos de função:

#ifndef _LINKLIST_H 
#define _LINKLIST_H 

#define false 0
#define true 1

#define UP 0
#define DOWN 1

typedef int bool;

// Defnindo o tipo TList: 

typedef struct tagList
{
  void *Data;
  struct tagList *Next;
} TList;

TList *Add(TList *root, void *item);
TList *Find(TList *root, void *item, bool (*IsEqual)(void *, void *));
void BubbleSort(TList *root, int order, int (*Compare)(void *, void *));
TList *Remove(TList *root, void *item, bool (*IsEqual)(void *, void *),
             void (*Delete)(void*));

#endif 

#include <alloc.h> 
#include "linklist.h" 

// Criando a função Add: 
TList *Add(TList *root, void *item)
{
  TList *iter = root;
  if(iter)
  {
    while(iter->Next)
      iter = iter->Next;
    iter->Next = (TList *)malloc(sizeof(TList));
    iter = iter->Next;
  }
  else
    iter = (TList *)malloc(sizeof(TList));
  iter->Data = item;
  iter->Next = NULL;
  return root ? root : iter;
}


// Criando a função Find:
TList *Find(TList *root, void *item, bool (*IsEqual)(void *, void *))
{
  TList *iter = root;
  while(iter ? !IsEqual(iter->Data, item) : false)
    iter = iter->Next;
  return iter;
}


// Criando a função BubbleSort: 
void BubbleSort(TList *root, int order, int (*Compare)(void *, void *))
{
  TList *begin;
  begin = root;
  while(begin && begin->Next)
  {
    TList *iter = begin->Next;
    while(iter)
    {
      int result = Compare(begin->Data, iter->Data);
      bool bCanSwap = (order == UP) ?
                         (result > 0? true : false) : 
                         (result > 0? false : true);

      if(bCanSwap)
      {
        void *swap = begin->Data;
        begin->Data = iter->Data;
        iter->Data = swap;
      }

      iter = iter->Next;
    }

  begin = begin->Next;
  }
}


// Criando a função Remove: 
TList *Remove(TList *root, void *item, bool (*IsEqual)(void *, void *),
             void (*Delete)(void *))
{
  TList *iter1 = root, *iter2 = NULL;
  while(iter1)
  {
    if(IsEqual(iter1->Data, item))
    {
      if(iter2)
      {
        iter2->Next = iter1->Next;
        iter2 = root;
      }
      else
        iter2 = iter1->Next;

      Delete(iter1->Data);
      free(iter1);

      return iter2;
    }

    iter2 = iter1;
    iter1 = iter1->Next;
  }

  return root;
}

Uma observação muito importante, as funções IsEqual, Compare e Delete são dependentes do tipo de dado, por isso, aqui elas são passada como um ponteiros de função para as funções Find, BubbleSort e Remove. A finalidade de Find é comparar dois itens, passados como ponteiros void, e retornar true caso sejam iguais, e false caso sejam diferentes. A finalidade de Compare é comparar dois itens, passados como ponteiros void, e retornar -1 caso o primeiro seja maior, 1 caso o segundo seja maior e 0 caso ambos sejam do iguais. A finalidade de Delete é apagar o item passado como ponteiro void.
Agora que já temos as rotinas principais, vamos criar um exemplo e fazer as rotinas auxilizares mencionadas acima.
Para criar uma lista deve-se saber qual tipo de dado utilizar, vamos criar uma lista simples e utilizar para isso, cadeias de caracter (char *), devemos então criar funções para manipulação das strings, como são chamadas as cadeias de caracter em C/C++.
As rotinas aqui criadas serão basicamente uma máscara para outras já existentes, apenas para facilitar o nosso trabalho posterior:

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 
#include <alloc.h> 
#include <string.h> 
#include <conio.h> 
#include "linklist.h" 


bool IsEqual(void *i1, void *i2)
{
  return stricmp(i1, i2) == 0;
}

int Compare(void *i1, void *i2)
{
  return stricmp(i1, i2); 
} 

void Delete(void *item) 
{ 
  free(item); 
} 

TList *FindItem(TList *root, void *item) 
{ 
  return Find(root, item, IsEqual); 
} 

void SortList(TList *root, int order) 
{ 
  BubbleSort(root, order, Compare); 
} 

TList *RemoveItem(TList *root, char *item) 
{ 
  return Remove(root, item, IsEqual, Delete); 
} 

void DisplayList(TList *root) 
{ 
  TList *iter = root; 
  while(iter) 
  { 
    printf(" %s", iter->Data); 
    iter = iter->Next; 
  } 
} 

const char *names[] = { 
   "Pera", "Manga", "Maça", 
   "Uva", "Laranja", "Goiaba", 
   "Abacaxi", "Morango", "Cajú", 
   "Melão", "Banana", NULL 
    }; 

///// Main Program /////////// 
int main() 
{ 
  TList *root = NULL, *pItem; 
  int c = 0, count; 

  // Adiciona itens com valores aleatorios na lista 
  randomize(); 
  for(count = 0; names[count]; count++) 
  { 
    char *item = (char *)malloc(sizeof(char) * 30); 
    strcpy(item, names[count]); 
    root = Add(root, item); 
  } 

  // Mostra lista preenchida 
  printf("\nNormal:\n");

  DisplayList(root); 

  // Ordena lista em ordem crescente 
  printf("\nOrdenada Crescente:\n"); 
  SortList(root, UP); 
  DisplayList(root); 

  // Ordena lista em ordem decrescente 
  printf("\nOrdenada Decrescente:\n"); 
  SortList(root, DOWN); 
  DisplayList(root); 

  c = random(count); 
  pItem = FindItem(root, names[c]); 
  if(pItem) 
    printf("\nItem %s encontrado\n", pItem->Data); 
  else 
    printf("\nItem %s nao encontrado\n", names[c]); 

  pItem = FindItem(root, "Abacate"); 
  if(pItem) 
    printf("\nItem %s encontrado\n", "Abacate"); 
  else 
    printf("\nItem %s nao encontrado\n", "Abacate"); 

  getch(); 

  // Apaga toda a lista 
  while(root) 
  { 
    printf("\nApagando Item %s\n", root->Data); 
    root = RemoveItem(root, root->Data); 
    DisplayList(root); 
  } 

  return 0; 
} 

Vemos com isso que a implementação de uma lista de nomes é muito simples, quando já se tem as funções implementadas de forma genérica e bem definidas, o tipo de dado utilizado pode ser então facilmente substituído por outro tipo mais complexo, como por exemplo estruturas, utilizando-se das mesmas funções de busca e ordenação, pode-se também alterar a forma como o dado será visualizado, por exemplo se tivéssemos uma lista de nome e telefone, bastaria implementar uma rotina ComparePhone que testa o telefone para ordenar por telefone e outra CompareName que testa o nome, para se ordenar por nome, poupando-se assim horas de trabalho de implementação e testes nos métodos de ordenação, futuramente pretendo fazer um artigo abordando apenas a utilização de ponteiros de função.