Data Structures and Algorithms - Old Questions
2. What do you mean by circular list? Differentiate between stack as a circular list and Queue as a circular list.
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:
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);
}
}