Home > Tecnologia > Informática > Programação > C++ > Listas duplamente ligadas em C++ (Parte I)

Listas duplamente ligadas em C++ (Parte I)

No artigo “Listas ligadas simples em C++ (Parte I)” fiz uma introdução às listas em C++ e falei de listas ligadas simples. Agora, vou falar de outro tipo de listas, as listas duplamente ligadas.

A principal diferença entre as listas ligadas simples, que apenas têm um apontador para o nó seguinte, tornando apenas possível iterar valores num sentido, é que as listas duplamente ligadas têm, para cada , dois apontadores. Um apontador para o nó seguinte e outro apontador para o nó anterior. Desta forma, a partir de um dado nó, podemos aceder tanto ao nó seguinte como ao nó anterior, sendo assim possível iterar uma lista duplamente ligada nos dois sentidos. Outra diferença é que, enquanto numa lista ligada simples, temos apenas o apontador para a “cabeça” da lista, numa lista duplamente ligada, temos também um apontador para a “cauda” da lista.

Imagine que, numa lista ligada simples, está num determinado nó e precisa de aceder ao nó anterior. A única forma de o fazer é voltar a varrer toda a lista, desde a cabeça, até ao nó pretendido. Com uma lista duplamente ligada, bastará usar o apontador para o nó anterior, o que é uma enorme vantagem.

Mas nem tudo é tão perfeito e estas listas têm um custo, pois para cada nó, teremos mais uns tantos bytes (4 bytes numa máquina de 32 bits ou 8 bytes numa máquina de 64 bits), o que se traduz num maior consumo de memória.

Vejamos a figura seguinte para nos ajudar a entender o conceito das listas duplamente ligadas.

Listas duplamente ligadas

Nesta figura, temos uma lista com 3 elementos. Nas caixas vermelhas, temos a cabeça, que aponta para o primeiro nó, e, em cada nó, um apontador para o nó seguinte, sendo que o último estará a apontar para NULL (fim da lista), simbolizado pela barra (“/”). Nas caixas verdes, temos a cauda, que aponta para o último nó, e, em cada nó, um apontador para o nó anterior, sendo que o primeiro estará a apontar para NULL (início da lista), também simbolizado pela barra (“/”).

Para começar, vamos simplesmente criar uma “struct” para definir o nosso nó, que iremos chamar de “NoDuplo” e irá conter um valor inteiro:

struct NoDuplo {
    int valor;
    NoDuplo* seguinte;
    NoDuplo* anterior;
};

Temos então declarada uma variável “valor”, do tipo inteiro, e dois apontadores: “seguinte” e “anterior”.

Agora, declaremos os apontadores a usar no nosso “main”:

    NoDuplo* no;
    NoDuplo* cabeca = NULL;
    NoDuplo* cauda = NULL;

Em que, o apontador “no” será um apontador que iremos usar nas nossas operações com a lista, o apontador “cabeca” irá apontar para o primeiro nó e o apontador “cauda” irá apontar para o último nó.

No artigo sobre listas ligadas simples, vimos como listar todos os valores desde o início da lista. Para já, vou agora exemplificar como poderemos listar todos os valores desde o fim da lista (por ordem inversa):

    if (cauda==NULL) {
        cout << "A lista está vazia!" << endl;
    }
    else {
        no = cauda;
        while (no!=NULL) {
            cout << "Valor: " << no->valor << endl;
            no = no->anterior;
        }
    }

Neste exemplo, verificamos se a lista está vazia verificando se a cauda é “NULL” (linha 1). Repare que, tanto podemos testar a cabeça como a cauda, pois sempre que uma lista estiver vazia, ambos estes apontadores estarão a apontar para “NULL”. Já agora, se tivermos apenas um nó, este será apontado tanto pela cabeça como pela cauda.

Havendo valores, começamos então pela cauda (linha 5) e fazemos um ciclo até que seja encontrado o início da lista (linha 6), em que o apontador “anterior” estará a apontar para NULL. E como estamos a ler a lista do fim para o início, teremos que andar para trás através do nó anterior (linha 8).



Vejamos agora, como inserir nós numa lista duplamente ligada:

Inserção à cabeça

Listas duplamente ligadas

Na figura acima, estamos a inserir um nó, com o valor 4220, à cabeça da lista. Este processo é de todo semelhante à introdução à cabeça numa lista ligada simples. Contudo, é necessário termos em atenção a questão do apontador para o nó anterior! Na figura mais acima, vimos que o primeiro nó era o de valor 1234. Então, será necessário copiar o apontador da cabeça para o nó seguinte no novo nó, com o valor 4220, para que este aponte para o “1234”, e alterar a cabeça para este novo nó. Mas como é uma lista duplamente ligada, ainda teremos que aceder ao nó “1234”, que agora será o segundo nó, e alterar o apontador “anterior“, que apontava para NULL, para o novo nó. Já o novo nó, deverá ficar com o apontador “anterior” com NULL (indicando, neste caso, o início da lista).

Vamos ver como efectuar esta operação em C++, testando primeiro se a lista está vazia (se tal for, será a introdução de um primeiro nó):

    no = (NoDuplo*) malloc(sizeof(NoDuplo));
    no->valor=4220;
    no->anterior = NULL;
    if (cabeca==NULL) {
        no->seguinte = NULL;
        cauda = no;
    }
    else {
        cabeca->anterior = no;
        no->seguinte = cabeca;
    }
    cabeca = no;

Para qualquer dos casos, o novo nó deverá ter o seu apontador “anterior” a NULL, pois estamos no início da lista. Agora repare que, na linha 4, estamos a testar se a cabeça está a NULL – o que indica que a lista está vazia – e, neste caso, o apontador do nó seguinte do novo nó deverá ser NULL, pois este será o primeiro e último (linha 5) e, como tal, a cauda deverá também apontar para este novo nó (linha 6).

Se a lista não estiver vazia, e seguindo o exemplo da lista representada na figura, o nó “1234”, que passará a ser o segundo, mas que ainda está apontado pela cabeça, deverá ficar com o apontador do nó “anterior” a apontar para o novo nó (linha 9) e, de igual modo à lista ligada simples, copia-se o apontador da cabeça para o apontador do nó “seguinte” do novo nó (linha 10).

Finalmente, na linha 12, a cabeça passará a apontar para o novo nó.

Inserção à cauda

Listas duplamente ligadas

No caso da inserção à cauda, as coisas tornam-se mais simples que na lista ligada simples, onde tínhamos que varrer toda a lista à procura do último nó. Como estamos perante uma lista duplamente ligada, temos o apontador “cauda” a apontar para o último nó. Na figura vimos, então, que estamos a inserir o nó, com o valor 4220, à cauda. De forma inversa à inserção à cabeça, teremos que copiar o apontador da cauda para o nó anterior ao novo nó “4220”, de forma a que esta aponta agora para o nó “2154”, e alterar a cauda para que passe a apontar para o novo nó. Mais uma vez, e porque se trata de uma lista duplamente ligada, teremos que alterar o apontador do nó seguinte do nó “2154”, que ficará a ser o penúltimo nó, para o novo nó. Já o novo nó, deverá ficar com o apontador do nó seguinte a NULL, pois estamos no fim da lista.

Vejamos o aspecto do código em C++:

    no = (NoDuplo*) malloc(sizeof(NoDuplo));
    no->valor=4220;
    no->seguinte = NULL;
    if (cauda==NULL) {
        no->anterior = NULL;
        cabeca = no;
    }
    else {
        cauda->seguinte = no;
        no->anterior = cauda;
    }
    cauda = no;

Para ambos os casos, o apontador “seguinte” do novo nó será sempre NULL, pois estamos no fim da lista (linha 3). Na linha 4, testamos também se a lista está vazia (relembro que podemos testar tanto com a cabeça como com a cauda), e se estiver, o apontador “anterior” do novo nó deverá ser NULL, pois este será o último e o primeiro (linha 5) e, como tal, a cabeça deverá também apontar para este novo nó (linha 6).

Se a lista não estiver vazia, e voltando a seguir o exemplo da figura, o nó “2154”, que passará a ser o penúltimo, mas ainda está a ser apontado pela cauda, deverá ficar com o apontador do nó “seguinte” a apontar para o novo nó (linha 9) e copia-se o apontador da cauda para o apontador do nó “anterior” do novo nó (linha 10).

Finalmente, na linha 12, a cauda passará a apontar para o novo nó.

Inserção a meio da lista

Listas duplamente ligadas

Quanto à inserção a meio da lista, imagine a situação representada na figura acima, em que pretendemos inserir o novo nó, com o valor 4220, entre o primeiro nó (“1234”) e o segundo nó (“790”). Tal como tínhamos na lista ligada simples, podemos aceder ao nó que antecede a posição onde queremos introduzir o novo nó ou, se fizermos a pesquisa a partir do fim, teremos que aceder ao nó que sucede essa posição. Eu irei manter o caso de fazermos a pesquisa a partir do início da lista, mas note que também teremos que aceder ao nó seguinte (“790”), pois teremos que alterar neste o apontador do nó “anterior”, como vou descrever em seguida.

Assim, após aceder ao nó que antecede a posição onde queremos introduzir o novo nó, copiamos o apontador “seguinte” desse nó (que no exemplo tem o valor 1234) para o novo nó (para que este passe a apontar para o nó “790”) e alteramos o apontador “seguinte” do nó “1234” para apontar para o novo nó. Mas como estamos perante uma lista duplamente ligada, teremos também que aceder ao nó “790” e alterar o seu apontador “anterior” (que apontava para o “1234”) de forma a apontar para o novo nó. Já o novo nó (“4220”) deverá também passar a ter o seu apontador “anterior” a apontar para o nó “1234”, mantendo assim a ligação nos dois sentidos.

Não vou para já demonstrar este código. Depois de ler a segunda parte deste artigo, poderá ver exemplos deste caso no artigo “Lista duplamente ligada com classes template“.

Mas como sugestão, convido o leitor a tentar escrever este código!



Na segunda parte, iremos ver como remover nós e dar um exemplo completo que insere nós à cabeça e à cauda, lista os valores dos nós e remove um nó com um dado valor.

Listas duplamente ligadas em C++ (Parte II)

Siga-nos nas redes sociais e esteja a par das nossas novidades no nosso blogue multi-temático Out4Mind!

Este artigo foi escrito de acordo com a antiga grafia.

About Carlos Santos

Frequência em mestrado de Engenharia Electrotécnica e de Computadores. Programador freelancer: Websites, Aplicações Web (JAVA e PHP), J2SE/J2EE, C/C++ e Android. Explicador e formador em informática, matemática e electrotecnia. Formação presencial ou remota através de Skype e Team Viewer. Interesses: Música, áudio, vídeo, ciência, astronomia e mitologia.

Leave a Reply

Your email address will not be published and it is optional.