Dynamic Linked Lists as Queues in C

When Dynamic Linked Lists are represented as Queues, the first node represents front of queue given by q.front and last node represents the rear of the queue given by q.rear where q.front and q.rear are pointers. Thus Qinsert(q,x) and Qdelete(q) could be implemented as below –

Qinsert(q,x){
    p = getnode();
    info(p) = x;
    next(p) = null;
    if(q.rear == null)
       q.front = p;
    else
       q.rear = p;
}

Qdelete(q){
  if(empty(q)){
      error message;
      exit(1);
  }
  p = q.front;
  x = info(p);
  q.front = next(p);
  
  if(q.front == null)/*last element is removed*/
      q.rear = null;
  freenode(p);
  return(x);/*stored for further viewing of deleted item*/
}

One of the disadvantages of using Linked List as stack or Queue is the increase in the time taken to manage the lists. An advantage is that all stacks and queues of a program have access to the same free list of nodes.

Add a Comment

Your email address will not be published. Required fields are marked *