What do you mean by circular list? Differentiate between stack as a circular list and Queue as a circular list.

Answers

This answer is not selected as best answer. This answer may not be sufficient for exam.

Your limit has been exceed. We have implemented this system because, We got difficulty on managing our servers. Please donate some amount to remove this limit.

Quota: 0 / 30

Donate

Circular linked list is a sequence of elements in which every element has link to its next element in the sequence and the last element has a link to the first element in the sequence.

Circular linked lists can be used to help the traverse the same list again and again if needed. A circular list is very similar to the linear list where in the circular list the pointer of the last node points not NULL but the first node.

Example:

User Loaded Image | CSIT Guide

Circular list has no end.

Stack as a circular List

To implement a stack in a circular linked list, let pstack be a pointer to the last node of a circular list. Actually there is no any end of a list but for convention let us assume that the first node(rightmost node of a list) is the top of the stack.

An empty stack is represented by a null list.

The structure for the circular linked list implementation of stack is:

struct node
{

    int info;
    struct node *next;

};

typedef struct node NodeType;

NodeType *pstack=NULL;

PUSH function:

void PUSH(int item)
{

    NodeType newnode;

    newnode=(NodeType*)malloc(sizeof(NodeType));

    newnode->info=item;

    if(pstack==NULL)
    {
        pstack=newnode;
        pstack->next=pstack;
    }
    else
    {
        newnode->next=pstack->next;
        pstack->next=newnode;
    }
}

POP function:

void POP()
{

    NodeType *temp;

    if(pstack==NULL)
    {
        printf(“Stack underflow\n');
        exit(1);
    }
    else if(pstack->next==pstack) //for only one node
    {
        printf(“poped item=%d”, pstack->info);
        pstack=NULL;
    }
    else
    {
        temp=pstack->next;
        pstack->next=temp->next;
        printf(“poped item=%d”, temp->info);
        free(temp);
    }
}

Queue as a circular List

By using a circular list, a queue may be specified by a single pointer q to that list. node(q) is the rear of the queue and the following node is its front.

Insertion function:

void insert(int item)
{

    NodeType *nnode;

    nnode=( NodeType *)malloc(sizeof(NodeType));

    nnode->info=item;

    if(pq==NULL)
          pq=nnode;
    else
    {
        nnode->next=pq->next;
        pq->next=nnode;
        pq=nnode;
    }
}

Deletion function:

void delet(int item)
{

    NodeType *temp;

    if(pq==NULL)
    {
        printf(“void deletion\n”);
        exit(1);
    }
    else if(pq->next==pq)
    {
        printf(“poped item=%d”, pq->info);
        pq=NULL;
    }
    else
    {
        temp=pq->next;
        pq->next=temp->next;
        printf(“poped item=%d”, temp->info);
        free(temp);
    }
}
If you found any type of error on the answer then please mention on the comment or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .