13

Estou tendo uma dificuldade em entender o funcionamento e a diferença de uma lista simplesmente-encadeada e uma lista duplamente-encadeada, as duas parecem ter a mesma finalidade e o mesmo funcionamento. Eu sei que as duas são utilizadas para guarda dados em formatos de listas, porem o que é a lista simplesmente-encadeada e a lista duplamente-encadeada? E quais são suas aplicabilidade?

Segue um exemplo de uma lista duplamente-encadeada para ilustrar minha duvida, que foi montada na minha faculdade:

#include <stdio.h>
#include <stdio_ext.h>
#include <stdlib.h>

struct NO
{
    int info;
    struct NO *proxima;
    struct NO *anterior;
};

void inserir(int);
void remover(int);
void imprime(void);
void inicializar(void);

struct NO *p, *auxiliar;

int cont;

int main(void)
{
    int opcao, valor;

    inicializar();

    do
    {
        printf("\n1 - Inserir");
        printf("\n2 - Remover");
        printf("\n3 - Imprimir");
        printf("\n4 - Sair");
        printf("\nOpcao: ");
        scanf("%d", &opcao);
        __fpurge(stdin);

        switch(opcao)
        {
            case 1:
                //Inserir
                printf("\nValor: ");
                scanf("%d", &valor);
                __fpurge(stdin);
                inserir(valor);

                break;
            case 2:
                //Remover.
                printf("\nValor: ");
                scanf("%d", &valor);
                __fpurge(stdin);

                remover(valor);
                break;
            case 3:
                //Imprimir.
                imprime();
                break;
        }
    }
    while ((opcao >= 1) && (opcao <= 3));

    free(p);

    return 0;
}

void inicializar()
{
    p = NULL;
    auxiliar = NULL;
    cont = 0;
}

void inserir(int valor)
{
    if (cont == 0) /*Primeiro NÓ*/
    {
        /*Aloca o primeiro NÓ*/
        p = (struct NO *) malloc( sizeof(struct NO));
        auxiliar = p;
        p->info = valor;
        p->proxima = NULL;
        p->anterior = NULL;

        cont++;
    }
    else
    {
        auxiliar->proxima = (struct NO *) malloc(sizeof(struct NO));
        auxiliar->proxima->anterior = auxiliar;
        auxiliar = auxiliar->proxima;
        auxiliar->info = valor;
        auxiliar->proxima = NULL;

        cont++;
    }
}

void imprime()
{
    struct NO * imp;
    imp = p;

    if (cont == 0)
    {
        printf("\nLista vazia!");
    }
    else
    {
        while (imp != NULL)
        {
            printf("%d ", imp->info);
            imp = imp->proxima;
        }

        printf("\nQuantidade de elementos: %d", cont);
    }
}

void remover(int valor)
{
    struct NO * navega;
    navega = p;

    if (cont == 0)
    {
        printf("\nLista vazia!");
    }
    else
    {
        while (navega != NULL)
        {
            if (navega->info == valor)
            {
                if ((navega->anterior == NULL) && (navega->proxima == NULL))
                {
                    free(navega);
                    auxiliar = navega = p = NULL;

                    cont--;

                    break;
                }
                if ((navega->anterior == NULL) && (navega->proxima != NULL))
                {
                    p = p->proxima;
                    free(navega);
                    p->anterior = NULL;
                    navega = p;

                    cont--;

                    break;
                }
                if ((navega->anterior != NULL) && (navega->proxima != NULL))
                {
                    navega->anterior->proxima = navega->proxima;
                    navega->proxima->anterior = navega->anterior;
                    free(navega);
                    navega = p;

                    cont--;

                    break;
                }
                if ((navega->anterior != NULL) && (navega->proxima == NULL))
                {
                    auxiliar = auxiliar->anterior;
                    free(navega);
                    auxiliar->proxima = NULL;
                    navega = p;

                    cont--;

                    break;
                }
            }
            else
            {
                navega = navega->proxima;
            }
        }

        printf("\nQuantidade de elementos: %d", cont);
    }
}

3 Respostas 3

17

O que são?

Ambas funcionam com nós independentes de dados. Estes nós possuem o valor do elemento e um apontador para o próximo elemento da lista. Como eles não estão em sequência contínua na memória (ou outro meio), é possível facilmente inserir e remover um elemento bastando mudar o apontador do elemento imediatamente anterior à posição onde o elemento em questão está sendo manipulado.

As listas ligadas (encadeadas), em geral, possuem capacidade de inserção e remoção na ponta (uma delas ou nas duas, no caso da dupla) de forma muito rápida ( O(1) ). Elas costumam ser ruins para inserção e remoção no meio ou o acesso precisa ocorrer em um ponto qualquer ( O(N) ). A inserção ou remoção em si é rápida também, o problema é que para chegar na posição onde a operação será executada ela tem complexidade linear. E quase sempre isto é necessário.

Na inserção o novo elemento recebe o apontador que estava no elemento anterior e o anterior recebe o ponteiro para o novo elemento.

Na remoção basta o elemento anterior receber o apontador contido no elemento a ser removido.

Comparando com outras estruturas

Em uma estrutura sequencial continua estas operações só podem ser realizadas reconstruindo toda a lista de dados (ainda que seja possível realizar algumas otimizações). Obviamente isto custa caro.

Hoje as listas ligadas raramente são usadas. Normalmente existem estruturas mais eficientes para a maioria dos casos (pilhas, árvores, hashes, até mesmo vetor simples, ainda que eventualmente algumas destas estruturas possam usar a lista ligada complementarmente). É raro ter um requisito que uma lista atenda bem. Elas só possuem um ponto forte para uma situação muito específica e um enorme ponto fraco.

O seu uso pode ser interessante quando o caso mais comum de leitura é percorrer sequencialmente toda lista ou boa parte dela e quando na escrita normalmente só há append de dados (ou prepend no caso da dupla). Mas neste caso um array ou uma pilha costuma ser mais adequado.

Note que as listas ligadas costumam ter alguma classificação de dados, por isto é importante os nós serem independentes. Se a classificação não é necessária, pode-se optar por uma estrutura de hash (sem ordem) ou um array (ordenado).

Entenda que uma estrutura classificada é aquela que possui um ordem específica de acordo com o valor dos elementos. Na estrutura ordenada os elementos são dispostos na ordem em que eles chegam. E na estrutura sem ordem, os elementos são dispostos em ordem não determinada.

Na maior parte dos casos onde a classificação é necessária, uma árvore costuma resolver melhor. Todas operações podem ser realizadas em tempo O(logN), que é muito próximo do O(1), que a lista ligada, na prática, não consegue alcançar em nenhuma operação individual, sem auxílio externo ou quando todos os elementos são percorridos.

Uma árvore guarda semelhança com uma lista ligada mas consegue navegar pelos elementos descartando metade da lista a cada passo dado. Isto tem um impacto absurdo, especialmente em grandes volumes de dados.

Com pequeno volume de dados quase todas estruturas de dados se aproximam em desempenho e qualquer uma pode ser usada sem comprometer o resultado.

Tem uma tabela mostrado os vários compromissos de cada estrutura de dados. Ela não é tão completa quanto poderia, mas já ajuda. Pena que pode enganar o leigo já que ela simplifica algumas coisas e pode dar ideia errada em alguns casos mais específicos.

Exemplos de uso

Alguns casos de free list ou pilha esparsa (não continua) podem se beneficiar disto. Os sistemas operacionais costumam ter alguns casos de uso interessantes. Um exemplo pode ser encontrado nessa resposta.

Lista duplamente encadeada

Pode ser percorrida pelos dois lados, ou seja, você pode começar pela cabeça ou pelo rabo da lista e andando de nó em nó. Pode escolher qual é o provável caminho mais eficiente. Para alcançar este objetivo cada nó deve possuir um apontamento para o próximo nó e outro para o anterior. Ela costuma ter, na prática melhor performance em todas operações, ainda que seja irrisório. Pode ter maior consumo de memória (tem como otimizar isto, mas há desvantagens também).

Double Linked List

Lista simplesmente encadeada

Só dá para percorrer de um lado obrigando começar pela cabeça. Os nós só precisam apontar para o próximo nó. Ela é mais eficiente em consumo de memória e um pouco menos complexa.

Single Linked List

Imagens da Wikipedia.

Coloquei no GitHub para referência futura.

5

A diferença é que em uma lista simplesmente encadeada cada nó da lista possui um ponteiro para o próximo nó:

Indicação dos ponteiros ligando cada nó

Já em uma lista duplamente encadeada cada nó da lista possui um ponteiro tanto para o próximo nó quanto para o nó anterior:

Mostrando os ponteiros ligando para um lado e para outro no nó

A grande vantagem de listas encadeadas está na velocidade de inserção e remoção de novos nós, o que ocorre porque os nós não precisam ser armazenados sequencialmente em memória. Veja como exemplo a primeira imagem (a lista simplesmente encadeada), cada nó possui um valor e um ponteiro para o próximo nó, o primeiro nó poderia estar na posição de memória "1024", já o segundo poderia estar na posição "512" e o terceiro na posição "5096", sendo assim caso você digamos precise adicionar um novo nó com o valor "70" e ele precise estar na segunda posição, seria necessário apenas alterar o ponteiro do primeiro nó para que aponte para o novo nó, e neste novo nó você colocaria o endereço do ponteiro anterior do primeiro nó. Caso você precise apagar o nó com o valor "37" tudo que precisaria fazer é alterar o ponteiro do nó anterior ("99") para que aponte para o nó que está a frente de "37", a cauda da lista no caso da imagem.

Agora compare isso com a utilização de um vetor simples que contêm os mesmos valores, [12, 99, 37], para que você possa adicionar um novo valor nesse vetor, digamos novamente "70" na segunda posição, seria preciso alocar uma novo espaço de memória, mover os valores 99 e 37 uma posição a frente, para só então poder adicionar o novo valor. Para remoção o problema é similar, caso você queira remover o primeiro valor seria necessário mover todos os valores à frente uma posição atrás.

Quanto à vantagem de listas duplamente encadeadas sobre as simplesmente encadeadas, nelas você pode tanto percorrer a lista a partir do início quanto a partir do fim, em qualquer nó que esteja pode seguir quaisquer um dos caminhos.

As aplicabilidades de ambas são inúmeras, garanto que você programando eventualmente vai encontrar um problema em que uma ou outra seja uma ótima solução. Possivelmente não vá ser a melhor solução, mas como é uma estrutura de dados simples e de fácil implementação você sem dúvida vai querer compreender e saber utilizar.

Na verdade não é tão bom assim em alguns casos, já que para inserir ou remover um elemento no meio você tem que chegar no local, e para percorrer a lista tem que passar por todos os itens até chegar ali. Se já estiver no local desejado, ótimo, será rápido, caso contrário percorrer toda lista (em média será complexidade linear dividido por 2 já que há casos que achará antes de ir até o fim. Por isso na maioria dos casos que uma lista é útil uma árvore é melhor ainda.

5

Acho que resumindo seria assim:

Encadeamento Simples - Anda somente em um sentido, não consegue retornar.

Encadeamento Duplo - Você tem as referencias tanto indo como voltando, ao percorrer uma lista você pode avançar e retornar pelos objetos.

Mais simples que isso não fica.

E quanto a velocidade vamos deixar para discutir quando chegar nas arvores, hash e grafos, cada um com suas vantagens e desvantagens. Para trabalhos simples, use lista mesmo.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .