What is the difference between simply-chained and double-chained list?

Question

I’m having a hard time understanding the functioning and difference of a simply-chained list and a double-chained list, the two seem to have the same purpose and functioning. I know that both are used to store data in list formats, but what is the simply-chained list and the double-chained list? And what are its applicability?

Follow an example of a double-chained list to illustrate my doubt, which was assembled at my college:

#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);
    }
}

Answer 1

What are?

Both work with data independent nodes. These nodes have the element value and a pointer to the next element in the list. Since they are not in continuous sequence in memory (or other medium), it is easy to insert and remove an element by simply changing the pointer of the element immediately prior to the position where the element in question is being manipulated.

The linked (chained) lists, in general, have the ability to insert and remove at the tip (one or both, in the case of the double) very quickly ( O(1) ). They are usually bad for insertion and removal in the middle or access needs to occur at any point ( O(N) ). The insertion or removal itself is fast as well, the problem is that to get to the position where the operation will be executed it has linear complexity. And almost always this is necessary.

On insertion the new element receives the pointer that was in the previous element and the previous one receives the pointer to the new element.

At removal it is sufficient to receive the pointer contained in the element to be removed.

Comparing to other structures

In a continuous sequential structure these operations can only be performed by reconstructing the entire data list (although it is possible to perform some optimizations). Obviously this is expensive.

Today linked lists are rarely used. Usually there are more efficient structures for most cases (cells, trees, hashes, even simple vector, although eventually some of these structures can use the linked list in addition). It is rare to have a requirement that a list meet well. They only have one strength for a very specific situation and a huge weakness.

Its use can be interesting when the most common case of reading is to go through sequentially the whole list or a good part of it and when in writing there is usually only append data (or prepend in the case of the double). But in this case a array or a battery is usually more suitable.

Note that linked lists often have some sort of data classification, so it is important for nodes to be independent. If classification is not required, a hash (without order) or a array (ordained).

Understand that a classified structure is one that has a specific order according to the value of the elements. In the ordered structure the elements are arranged in the order in which they arrive. And in the structure without order, the elements are arranged in unspecified order.

In most cases where classification is required, a tree usually solves better. All operations can be performed in time O(logN), which is very close to O(1), that the linked list, in practice, can not achieve in any individual operation, without external assistance or when all the elements are covered.

A tree bears resemblance to a linked list but can navigate through the elements by discarding half of the list at each step. This has an absurd impact, especially on large volumes of data.

With small data volume almost all data structures approach performance and any one can be used without compromising the result.

Has a table showing the various commitments of each data structure. It’s not as complete as it could be, but it already helps. Too bad it can fool the layman since it simplifies some things and may give wrong idea in some more specific cases.

Examples of use

Some cases of free list or sparse stack (does not continue) can benefit from this. Operating systems often have some interesting use cases. An example can be found in that reply.

Double chained list

It can be traversed on both sides, meaning you can start at the head or tail of the list and walk from knot to knot. You can choose which is probably the most efficient way. To achieve this goal each knot must have a point to the next knot and another to the previous one. She usually has, in practice, better performance in all operations, even if it is insignificant. You may have more memory consumption (you can optimize this, but there are drawbacks too).

Simply chained list

You can only go through one side forcing you to start from the head. The nodes just need to point to the next knot. It is more memory-efficient and a little less complex.

Images of Wikipedia.

Answer 2

I guess that’s how it would be summed up:

Encadeamento Simples - Walks only in one direction, can’t return.

Encadeamento Duplo - You have the references going back and forth, as you go through a list you can go back and forth through the objects.

It doesn’t get any simpler.

And as for the speed we will leave to discuss when arriving in the trees, hash and graphs, each with its advantages and disadvantages. For simple jobs, use same list.

Answer 3

The difference is that in a simply chained list each node in the list has a pointer to the next node:

Already in a doubly chained list each node in the list has a pointer to both the next node and the previous node:

The great advantage of chained lists is the speed of inserting and removing new nodes, which occurs because the nodes do not need to be stored sequentially in memory. See for example the first image (the simply chained list), each node has a value and a pointer to the next node, the first node could be at the memory position "1024", the second could be at the position "512" and the third at the position "5096", so if you say you need to add a new node with the value "70" and it needs to be in the second position, you just need to change the pointer of the first node to point to the new node, and in this new node you would place the address of the previous pointer of the first node. If you need to delete the node with the value "37" all you would need to do is change the pointer of the previous node ("99") so that it points to the node that is in front of "37", the tail of the list in the case of the image.

Now compare that with using a simple vector that contains the same values, [12, 99, 37], so that you can add a new value to that vector, say again "70" at the second position, you would need to allocate a new memory space, move the values 99 and 37 one position forward, only then can add the new value. For removal the problem is similar, in case you want to remove the first value you would need to move all values forward one position back.

As to the advantage of double-chained lists over simply chained ones, in them you can either scroll through the list from the beginning or from the end, in any node that is can follow any of the paths.

The applicability of both are numerous, I guarantee that you programming eventually will find a problem where one or the other is a great solution. It may not be the best solution, but as it is a simple and easy to implement data structure you will no doubt want to understand and use.

In fact it is not so good in some cases, since to insert or remove an element in the middle you have to get to the site, and to go through the list you have to go through all the items until you get there. If you are already in the desired place, great, it will be fast, otherwise you will go through the entire list (on average it will be linear complexity divided by 2 since there are cases you will find before you go through the end. So in most cases a list is useful a tree is even better.