Linked list - easy

Which of the following is suitable data structure for implementing queues

  1. Singly linked list
  2. Circular linked list
  3. Doubly linked list
  4. None of these 
4Comments
sanjay @sanjayrao
22 Oct 2017 08:54 am

I think it should be circular linked list

hemanth @hemanth269
25 Oct 2017 12:06 pm

single linked list is enough to do enqueue and dequeue

store two pointers 1)at starting and 2) at ending

to insert into queue make a node and insert at end and make the inserted node as end

to pop or dequeue  from queue  print start node value and  free start node  and  make start node as start -> next  to delete it

 

single linked list is enough to do both enqueue and dequeue  

B. HARI TEJA @hariteja
27 Oct 2017 01:49 am

in queues you just need to operate on two positions front and rear and for that single linkedlist is enough, by setting two pointers one at the starting node(dequeue here) another at the last node(enqueue here).

Niket Gangwar @niket151194
29 Oct 2017 08:51 am

Question is about suitable linked list that can be used...

If we observe closely than we will find that with singly linked list if we try to implement queue then we need two external pointers(front and rear), front for dequeue and rear for enqueue... and also we are wasting the last node's 'next' pointer as it is made NULL.

But if we use circular linked list then we can use the last node's pointer to point to the first node(vaguely calling it first as circular list ),thus efficient use of memory and unlike SLL we can use only one external pointer pointing to the last node and this way queue can be implemented ( try it by yourself to check its validity). 

So circular linked list will be more suitable(efficient) in terms of memory usage . Thus Circular Linked List must be the answer....

Source :- Tenenbaum ,DSUC 2nd edition pg no. 229  or GATE 2004 Question.