Out4Mind O seu portal multi-temático
Neste artigo vou exemplificar a implementação de uma lista duplamente ligada usando classes template em C++.
Pré-requisitos: Para melhor entender este artigo, deverá já ter algumas noções de listas em C++ e de classes template.
– Para uma introdução às listas em C++ e listas ligadas simples, consulte primeiro o artigo “Listas ligadas simples em C++“.
– Para uma introdução às listas duplamente ligadas em C++, consulte o artigo “Listas duplamente ligadas em C++“.
– Se precisar de rever alguma questão sobre o uso de classes template em C++, veja primeiro este artigo introdutório: “Classe template em C++“.
As classes para gestão de listas e semelhantes já existem na biblioteca STL (Standard Template Library) do C++. Porém, para estudantes ou curiosos, é importante perceber o mecanismo destas classes. Para tal, saber implementá-las é um bom caminho para melhor compreender esta matéria.
Vamos ver uma implementação simples que, apesar de não ser igual à das implementações da STL, irá permitir compreender o funcionamento destas listas em classes template e, até mesmo, poderá usar estas classes nos seus projectos. É importante ter em atenção que, como se trata de classes template, podemos ter qualquer tipo de dados nos nós. Por isso, a implementação não pode ser tão directa como nos exemplos que vimos anteriormente e irá exigir algum código adicional para usarmos os métodos destas classes.
Iremos ter 3 classes:
- Classe “NoDuplo” – Esta classe irá definir um nó duplamente ligado
- Classe “ListaDupla” – Esta classe fará a gestão de uma lista duplamente ligada
- Classe “Iterador” – Esta classe permitirá iterar os vários nós da lista em ambos os sentidos
Mais uma vez, vou ignorar os “include” e outras instruções. No fim, poderá descarregar o código completo e comentado.
Vamos então começar por ver o código da classe “NoDuplo” que, por ser uma classe template, estará implementada num ficheiro “.h“:
template <class T>
class NoDuplo {
public:
NoDuplo(const T &e = T(), NoDuplo *s = NULL, NoDuplo *a = NULL) : elemento(e), seguinte(s), anterior(a) {}
~NoDuplo() {}
T elemento;
NoDuplo *seguinte;
NoDuplo *anterior;
};
Na linha 4, declaramos um construtor que, por omissão, irá construir um nó duplo com um elemento do tipo T (genérico), um apontador para o nó seguinte a NULL e um apontador para o nó anterior igualmente a NULL. Poderemos passar, no construtor, um dado elemento existente e os respectivos apontadores “seguinte” e “anterior”. Na linha 6, temos declarado um elemento do tipo T (genérico) e nas linhas 7 e 8 teremos os apontadores para os nós seguinte e anterior, respectivamente.
Antes de passarmos à lista, vejamos primeiro o iterador:
template <class T>
class Iterador {
private:
NoDuplo<T> *noActual;
public:
Iterador(NoDuplo<T> *no = NULL) : noActual(no) {}
~Iterador() {
if (noActual==NULL) {
noActual = NULL;
}
}
NoDuplo<T> *noSeguinte() {
if (noActual==NULL) {
return NULL;
}
noActual = noActual->seguinte;
return noActual;
}
NoDuplo<T> *noAnterior() {
if (noActual==NULL) {
return NULL;
}
noActual = noActual->anterior;
return noActual;
}
};
Na linha 4, temos um membro privado que será um apontador para o nó actual do iterador. Na linha 6, temos um construtor que deverá receber um dos nós da lista, ficando a NULL se não for passado nenhum nó (mas isso fará com que o iterador não possa fazer nenhuma iteração). Na linha 12, declaramos o método “noSeguinte” que irá retornar NULL se já passámos da última posição. Caso contrário, avança para o nó seguinte e devolve esse nó. De forma semelhante, na linha 19, temos o método “noAnterior” que também irá devolver NULL se já passámos da primeira posição (para trás). Caso contrário, recua para o nó anterior e devolve esse nó.
Quanto ao código da classe “ListaDupla“, no ficheiro “ListaDupla.h”, por ser um pouco extenso, vou reparti-lo, indicando os métodos que ficarão disponíveis.
Comecemos pelos membros privados para a cabeça e para a cauda:
template <class T>
class ListaDupla {
private:
NoDuplo<T> *cabeca;
NoDuplo<T> *cauda;
Repare que, tanto a cabeça como a cauda, serão do tipo “NoDuplo” para um tipo genérico “T”.
Quanto ao construtor e destrutor:
public:
ListaDupla() {
cabeca = new NoDuplo<T>();
cauda = new NoDuplo<T>();
}
~ListaDupla() {
limpar();
delete cabeca;
delete cauda;
}
Repare que, no construtor (linha 2), estamos a declarar a cabeça e a cauda como nós! Isto quer dizer que o primeiro elemento da lista será apontado por “cabeca->seguinte” e o último elemento da lista por “cauda->anterior“. Repare também que estamos a usar o construtor de “NoDuplo” vazio e, como tal, iremos ter estes apontadores a NULL (a lista estará vazia).
No destrutor (linha 6), devemos limpar a lista para libertar todos os nós existentes da memória, e libertar também a cabeça e a cauda.
Vejamos os restantes métodos da classe, um a um:
– vazia()
bool vazia() { return (cabeca->seguinte == NULL); }
Este método retorna “true” se a lista estiver vazia. Simplesmente, devolve o resultado da comparação “cabeca->seguinte == NULL”, que, ao ser verdade, indica que a lista está vazia.
– inserePrimeiro(T)
void inserePrimeiro(T &e) {
if (vazia()) {
NoDuplo<T> *novoNo = new NoDuplo<T>(e);
cabeca->seguinte = novoNo;
cauda->anterior = novoNo;
}
else {
NoDuplo<T> *primeiroActual = cabeca->seguinte;
NoDuplo<T> *novoNo = new NoDuplo<T>(e, primeiroActual);
primeiroActual->anterior = novoNo;
cabeca->seguinte = novoNo;
}
}
Este método insere o elemento, passado como parâmetro, à cabeça da lista. Repare que devemos testar se a lista está vazia (linha 2) e, caso esteja, criamos um novo nó onde passamos, no construtor, apenas o elemento a inserir (linha 3), pois sabemos que, por omissão, os apontadores “seguinte” e “anterior” ficarão a NULL e é o que nos interessa para definir um primeiro elemento para a lista. Em seguida, na linha 4, alteramos o apontador “seguinte” da cabeça que irá apontar para o novo nó, que será o primeiro da lista e, na linha 5, alteramos o apontador “anterior” da cauda para este mesmo novo nó, pois também será o último.
Caso a lista não esteja vazia, no bloco “else” da linha 7, vamos buscar o apontador para o primeiro nó actual da lista (linha 8) e declaramos um apontador para o novo nó, passando o novo elemento e o apontador para o primeiro nó actual, que irá passar a ser o segundo (linha 9). Repare que, ao não passarmos um apontador para o nó anterior, este ficará NULL e é o que precisamos pois estamos a inserir um novo primeiro nó (inserção à cabeça). Em seguida, devemos alterar o apontador “anterior” no primeiro nó actual, para que este aponte para o novo primeiro nó (linha 10). Finalmente, na linha 11, o apontador “seguinte” da cabeça passará a apontar para o novo nó, que passará então a ser o novo primeiro nó da lista.
– InsereUltimo(T)
void insereUltimo(T &e) {
if (vazia()) {
NoDuplo<T> *novoNo = new NoDuplo<T>(e);
cabeca->seguinte = novoNo;
cauda->anterior = novoNo;
}
else {
NoDuplo<T> *ultimoActual = cauda->anterior;
NoDuplo<T> *novoNo = new NoDuplo<T>(e, NULL, ultimoActual);
ultimoActual->seguinte = novoNo;
cauda->anterior = novoNo;
}
}
De forma análoga ao método anterior, este método insere o elemento, passado como parâmetro, à cauda da lista. Repare que, mais uma vez, na linha 2 testamos se a lista está vazia e, caso esteja, aplicamos o mesmo código que vimos no método “inserePrimeiro”, pois estamos a introduzir um primeiro elemento na lista.
Caso a lista não esteja vazia, no bloco “else” da linha 7, vamos agora buscar o apontador para o último nó actual da lista (linha 8) e voltamos a declarar um apontador para o novo nó (linha 9). Desta vez, passamos o elemento, passamos NULL para o apontador “seguinte” deste nó, pois irá ser um novo último nó (inserção à cauda), e passamos, para o apontador “anterior”, o último nó actual, que passará a ser o penúltimo nó. Desta vez, na linha 10, alteramos o apontador “seguinte” do último nó actual para o novo nó, para que este aponte para o novo último nó. Finalmente, na linha 11, o apontador “anterior” da cauda passará a apontar para este novo último nó.
– insereAntesDe(NoDuplo<T> *, T)
bool insereAntesDe(NoDuplo<T> *ref, T &e) {
if (vazia()) {
return false;
}
NoDuplo<T> *procuraRef = cabeca->seguinte;
while (procuraRef!=NULL) {
if (procuraRef==ref) {
break;
}
procuraRef = procuraRef->seguinte;
}
if (procuraRef==NULL) {
return false;
}
else {
NoDuplo<T> *antesRef = procuraRef->anterior;
NoDuplo<T> *novoNo = new NoDuplo<T>(e, procuraRef, antesRef);
if (antesRef==NULL) {
cabeca->seguinte = novoNo;
}
else {
antesRef->seguinte = novoNo;
}
procuraRef->anterior = novoNo;
return true;
}
}
Neste método, pretendemos inserir um novo elemento antes de um nó “ref”, que será um apontador para um nó de “referência” para o procurarmos na lista. Este método irá retornar “true” se o elemento for inserido com sucesso, ou “false” se o nó de referência não existir na lista ou se esta estiver vazia. Mas, supostamente, se temos um nó da lista, esta não deverá estar vazia, mas, por cautela e porque poderíamos definir um nó qualquer, devemos testar se a lista está vazia (linha 2) e procurar se este nó existe.
Para tal, na linha 5, iniciamos um apontador para procurar o tal nó de “referência” e, na linha 6, iniciamos um ciclo para o procurar. Se esse nó de “referência” for encontrado, saímos do ciclo com a instrução “break” da linha 8. Porém, o ciclo pode chegar ao fim sem ter encontrado o nó de referência. Para tal, testamos na linha 12, se o apontador usado na procura é NULL. Caso seja, indica que o nó de referência não foi encontrado e retorna “false“.
Caso contrário, entramos no bloco “else” da linha 15. Note que, neste momento, temos no apontador “procuraRef”, o mesmo apontador do nó de “referência” e que é o nó que sucede a posição onde queremos inserir o novo nó. Precisamos, agora, de definir um apontador para o nó que antecede o nó de referência (linha 16), que ficará antes do novo nó que queremos inserir.
Agora, na linha 17, e porque estamos a fazer uma possível inserção a meio da lista, declaramos o apontador para o novo nó com o novo elemento, o apontador para o nó de referência (que será o que irá suceder ao novo nó) para o apontador “seguinte” e o nó “antesRef” (que será o nó que irá anteceder o novo nó) para o apontador “anterior“. Uma observação importante! Se o nó “referência” for o primeiro nó, estaremos a fazer uma inserção à cabeça da lista e o apontador “antesRef” será NULL! Neste caso, quando declarámos o novo nó, o apontador “anterior” deste ficará automaticamente a NULL! Mas devemos testar este caso, na linha 18, e fazer uma inserção à cabeça, alterando o apontador “seguinte” desta para o novo nó (linha 19). Caso não seja o primeiro nó, o apontador “antesRef” estará realmente a apontar para o nó que irá anteceder o novo nó, e deveremos alterar o seu apontador “seguinte” para o novo nó. Finalmente, na linha 24, alteramos o apontador “anterior” do nó de referência para o novo nó e retornamos “true” pois o nó foi inserido e temos a integridade da lista garantida!
– inserirDepoisDe(NoDuplo<T> *, T)
bool insereDepoisDe(NoDuplo<T> *ref, T &e) {
if (vazia()) {
return false;
}
NoDuplo<T> *procuraRef = cabeca->seguinte;
while (procuraRef!=NULL) {
if (procuraRef==ref) {
break;
}
procuraRef = procuraRef->seguinte;
}
if (procuraRef==NULL) {
return false;
}
else {
NoDuplo<T> *depoisRef = procuraRef->seguinte;
NoDuplo<T> *novoNo = new NoDuplo<T>(e, depoisRef, procuraRef);
if (depoisRef==NULL) {
cauda->anterior = novoNo;
}
else {
depoisRef->anterior = novoNo;
}
procuraRef->seguinte = novoNo;
return true;
}
}
Neste método, a principal diferença é que pretendemos inserir o novo nó depois do nó de “referência”. Não vou entrar em detalhes para este caso pois é praticamente igual ao caso anterior. A diferença está nos apontadores que, neste caso, o nó “referência” será o nó que irá anteceder o novo nó e a declaração de um nó “depoisRef” (linha 16) que será o nó que irá suceder ao novo nó. Porque podemos estar no fim da lista, na linha 18 também testamos se este nó “depoisRef” é NULL e fazemos uma inserção à cauda.
Para mais informações, veja os comentários do código fonte completo, cujo link para download está no final deste artigo.
– remove(NoDuplo<T> *)
bool remove(NoDuplo<T> *r) {
if (vazia()) {
return false;;
}
NoDuplo<T> *remover = cauda->anterior;
while (remover!=NULL) {
if (remover==r) {
break;
}
remover = remover->anterior;
}
if (remover==NULL) {
return false;
}
else {
NoDuplo<T> *depoisRemover = remover->seguinte;
NoDuplo<T> *antesRemover = remover->anterior;
if (depoisRemover==NULL) {
cauda->anterior = antesRemover;
}
else {
depoisRemover->anterior = antesRemover;
}
if (antesRemover==NULL) {
cabeca->seguinte = depoisRemover;
}
else {
antesRemover->seguinte = depoisRemover;
}
delete remover;
return true;
}
}
Este método permite eliminar um determinado nó passado como parâmetro. A remoção do nó pode ser feita tanto à cabeça, como à cauda, ou a meio da lista. O método irá retornar “true” se o nó foi eliminado com sucesso ou “false” se a lista estiver vazia ou o nó não foi encontrado. Mais uma vez, é suposto que o nó exista, mas como podemos declarar um nó qualquer, devemos testar se a lista está vazia (linha 2) e procurar se o nó existe no ciclo “while” da linha 6. Para fazer a pesquisa, na linha 5, declaramos um apontador “remover” para procurar o nó a partir da cabeça. Se o nó for encontrado, a instrução “break” da linha 8 irá interromper o ciclo.
Após o ciclo terminar, na linha 12, verificamos se o nó “remover”, usado na pesquisa, é NULL. Se o for, quer dizer que o nó a eliminar não foi encontrado na lista e devolvemos “false“. Caso tenha sido encontrado, entramos no bloco “else” da linha 15.
Agora, declaramos 2 apontadores! Na linha 16, declaramos um apontador para o nó que está depois do nó que queremos remover (“depoisRemover”) e, na linha 17, um apontador para o nó que está antes do nó que queremos remover (“antesRemover”).
Porém, não sabemos em que parte da lista estamos e podemos estar a fazer uma remoção à cabeça ou à cauda. Para verificar isso, na linha 18, testamos se o apontador “depoisRemover” é NULL. Se assim for, estamos a remover o último nó da lista e estamos a fazer uma remoção à cauda! Como tal, deveremos alterar o apontador “anterior” da cauda para o nó que antecede o nó que queremos remover. Caso não seja o último nó, alteramos o apontador “anterior” de “depoisRemover” para o nó que antecede o nó que queremos remover. Agora, na linha 24, teremos que testar se estamos no primeiro nó da lista, se o apontador “antesRemover” for NULL. Se assim o for, estamos a fazer uma remoção à cabeça e temos que alterar o apontador “seguinte” desta para o nó “depoisRemover”. Se não for o primeiro nó, então alteramos o apontador “seguinte” do nó “antesRemover” para o nó “depoisRemover”.
Note ainda que, se ambos os apontadores “depoisRemover” e “antesRemover” estiverem a NULL, estamos a remover o único elemento da lista! Neste caso, ficaremos com ambos os apontadores “seguinte” da cabeça e “anterior” da cauda a NULL, indicando que a lista ficará vazia!
Finalmente, temos tudo pronto para libertar o nó que queremos remover da memória com a instrução “delete” da linha 30 e retornamos “true“.
– limpar()
void limpar() {
int contador = 0;
while (cauda->anterior!=NULL) {
NoDuplo<T> *remove = cauda->anterior;
cauda->anterior = remove->anterior;
delete remove;
contador++;
}
std::cout << "Libertados da memória " << contador << " nós" << std::endl;
}
Este método é muito simples e destina-se a libertar todos os nós da lista. Este método é chamado no destrutor da lista mas também pode ser chamado pelo programa, caso se pretenda limpar a lista. Como nos exemplos anteriores vimos este processo a partir da cabeça, neste exemplo vou fazer a remoção dos nós a partir da cauda (linha 3). Neste ciclo, declaramos um apontador “remove” para o último nó da lista (linha 4) e movemos a cauda para o seu nó anterior (linha 5). Finalmente, apagamos o nó a remover na linha 6. Este ciclo termina após apagar o último elemento, quando o apontador “anterior” da cauda ficar a NULL.
Por regra, as classes não escrevem nada no ecrã. Mas para o leitor ter a noção dos nós que foram libertados, foi implementado um contador e o seu valor é mostrado no fim do método, indicando quantos nós foram libertados da memória.
– obtemIteradorCabeca()
Iterador<T> *obtemIteradorCabeca() {
Iterador<T> *i = new Iterador<T>(cabeca);
return i;
}
Este método limita-se a retornar um apontador para um iterador iniciado à cabeça da lista.
– obtemIteradorCauda()
Iterador<T> *obtemIteradorCauda() {
Iterador<T> *i = new Iterador<T>(cauda);
return i;
}
Este método limita-se a retornar um apontador para um iterador iniciado à cauda da lista.
E chegámos ao fim das nossas classes que vão suportar a nossa lista duplamente ligada com classes template.
Na segunda parte deste artigo, iremos ver exemplos de utilização destas classes.
– Lista duplamente ligada com classes template (Parte II)
Este artigo foi escrito de acordo com a antiga grafia.
Código fonte (UTF-8 ; OS X / UNIX):
