Este código é uma lista ligada circular [fechada

Question

O código a seguir foi dado em nossa escola como uma amostra para a LinkList Circular e disse a cada aluno para construir uma versão própria do Circular LinkedList.

Minha pergunta é: o código a seguir é realmente uma lista de link circular?

// Program of circular linked list
#include <stdio.h>
#include <malloc.h>

struct node
{
    int info;
    struct node *link;
}*last;

main()
{
    int choice,n,m,po,i;
    last=NULL;
    while(1)
    {
        printf("1.Create List\n");
        printf("2.Add at begining\n");
        printf("3.Add after \n");
        printf("4.Delete\n");
        printf("5.Display\n");
        printf("6.Quit\n");
        printf("Enter your choice : ");
        scanf("%d",&choice);

        switch(choice)
        {
         case 1:
            printf("How many nodes you want : ");
            scanf("%d",&n);
            for(i=0; i < n;i++)
            {
                printf("Enter the element : ");
                scanf("%d",&m);
                create_list(m);
            }
            break;
         case 2:
            printf("Enter the element : ");
            scanf("%d",&m);
            addatbeg(m);
            break;
         case 3:
            printf("Enter the element : ");
            scanf("%d",&m);
            printf("Enter the position after which this element is inserted : ");
            scanf("%d",&po);
            addafter(m,po);
            break;
         case 4:
            if(last == NULL)
            {
                printf("List underflow\n");
                continue;
            }
            printf("Enter the number for deletion : ");
            scanf("%d",&m);
            del(m);
            break;
         case 5:
            display();
            break;
         case 6:
            exit(0);
         default:
            printf("Wrong choice\n");
        }/*End of switch*/
    }/*End of while*/
}/*End of main()*/

create_list(int num)
{
    struct node *q,*tmp;
    tmp= malloc(sizeof(struct node));
    tmp->info = num;

    if(last == NULL)
    {
        last = tmp;
        tmp->link = last;
    }
    else
    {
        tmp->link = last->link; /*added at the end of list*/
        last->link = tmp;
        last = tmp;
    }
}/*End of create_list()*/

addatbeg(int num)
{
    struct node *tmp;
    tmp = malloc(sizeof(struct node));
    tmp->info = num;
    tmp->link = last->link;
    last->link = tmp;
}/*End of addatbeg()*/

addafter(int num,int pos)
{

    struct node *tmp,*q;
    int i;
    q = last->link;
    for(i=0; i < pos-1; i++)
    {
        q = q->link;
        if(q == last->link)
        {
            printf("There are less than %d elements\n",pos);
            return;
        }
    }/*End of for*/
    tmp = malloc(sizeof(struct node) );
    tmp->link = q->link;
    tmp->info = num;
    q->link = tmp;
    if(q==last)    /*Element inserted at the end*/
        last=tmp;
}/*End of addafter()*/

del(int num)
{
    struct node *tmp,*q;
    if( last->link == last && last->info == num)  /*Only one element*/
    {
        tmp = last;
        last = NULL;
        free(tmp);
        return;
    }
    q = last->link;
    if(q->info == num)
    {
        tmp = q;
        last->link = q->link;
        free(tmp);
        return;
    }
    while(q->link != last)
    {
        if(q->link->info == num)     /*Element deleted in between*/
        {
            tmp = q->link;
            q->link = tmp->link;
            free(tmp);
            printf("%d deleted\n",num);
            return;
        }
        q = q->link;
    }/*End of while*/
    if(q->link->info == num)    /*Last element deleted q->link=last*/
    {
        tmp = q->link;
        q->link = last->link;
        free(tmp);
        last = q;
        return;
    }
    printf("Element %d not found\n",num);
}/*End of del()*/

display()
{
    struct node *q;
    if(last == NULL)
    {
        printf("List is empty\n");
        return;
    }
    q = last->link;
    printf("List is :\n");
    while(q != last)
    {
        printf("%d ", q->info);
        q = q->link;
    }
    printf("%d\n",last->info);
}/*End of display()*/

A razão pela qual eu não estou concordando é porque NULL é usado para verificar o último nó na lista.

Answer 1

Sim, o código implementa um Lista ligada circular

A variável última é apenas nula no início, depois de adicionar o primeiro elemento, o link indicará para si mesmo. Veja a função CreateList.

As listas não circulares sempre têm os últimos elementos, o próximo ponteiro definido como nulo para indicar o final da lista.

EDIT: Desculpe, não posso fazer arte ASCII com meu iPad.

Start:
last=NULL

call createlist( 12 )
Result: Last(12) -> Last

call addatbeg( 15 )

Result:
tmp( 15 ) -> Last( 12 -)
 ^                 |
 |                 |
 +----<-------<----+

Para entender como esses ponteiros funcionam, eu recomendaria desenhar um diagrama simples com base nas instruções do código. Espero que isto ajude.

Answer 2

Não escrutinei em detalhes, mas parece que é realmente uma lista vinculada. Quanto a a Lista ligada circular, Eu não encontrei isso antes.

A verificação para NULL está testando se o nó tem um próximo nó. Se não (nulo), é o último nó.