Listas Ligadas - Parte 7

Com este post vamos encerrar esta passada rápida sobre as listas ligadas, falando sobre a implementação na linguagem C++.

Listas Ligadas em C++

O código apresentado anteriormente pode, é claro, ser utilizado diretamente em um programa C++. Entretanto, é mais elegante criar uma classe que encapsule as estruturas e rotinas. Por exemplo, o destrutor da classe pode percorrer a lista liberando a memória alocada para os nós. As situações de erro, indicadas através de um retorno FALSE nas rotinas anteriores, podem ser sinalizadas através de exceções.

Uma desvantagem do código apresentado anteriormente é que ele é específico para um determinado tipo de elemento (nos exemplos a lista armazenava sempre inteiros). Se precisarmos, por exemplo, de uma lista para inteiros e uma lista para números de ponto flutuante, será preciso duplicar a maior parte do código e das estruturas de dados.

Uma solução, que pode também ser usada em C, é armazenar no nó um ponteiro para a informação ao invés da própria informação. Se este ponteiro for do tipo void *, ele poderá apontar para qualquer tipo de informação. Isto permite, inclusive, guardar em uma lista elementos de tipo diferente. A desvantagem desta solução é que ela é pouco robusta quanto ao controle dos tipos. Além disso, a alocação e liberação das áreas que contém as informações precisa ser feita por uma camada externa à de controle da lista (já que a lista desconhece o formato e tamanho da área de informações).

A linguagem C++ possui um recurso justamente para os casos em que se deseja definir uma função ou classe de forma independente dos tipos dos dados a serem manipulados: os templates.

Um template é uma espécie de macro cujo parâmetro é um tipo ou uma classe. Por exemplo, vamos definir um template de uma função para somar dois números:

template  T Soma (T a, T b)
{
return a+b;
}

Podemos usar este template com qualquer classe que suporte o operador +, o C++ verificará se os parâmetros são do mesmo tipo:

int a,b,c;
double x,y,z;

c = Soma (a,b); // soma dois inteiros
z = Soma (x,y); // soma dois doubles
z = Soma (a,y); // erro, tipos diferentes

Podemos usar templates também na definição de classes:

template  class NO
{
T  valor; // dado do elemento
NO *prox; // ponteiro para o elemento seguinte

// ...
};

Portanto podemos criar um template capaz de criar uma classe de lista para cada tipo que precisarmos.

Melhor ainda, isto já foi feito. O Visual C++ possui dois templates para criação de listas duplamente ligadas:

• CList, que faz parte da MFC; e
• list, que faz parte da STL (Standard Template Library).

Referências

• The Art of Computer Programming, Volume 1 Fundamental Algorithms – Donald E. Knuth
• An Introduction To Data Structures With Applications – Jean-Paul Tremblay & Paul G. Sorenson
• The C Programming Language – Brian W. Kernighan & Dennis M. Ritchie.