Implementation of queue by using a single linked list, Data Structure & Algorithms

Q. Perform implementation of a queue using a singly linked list L. The operations INSER and DELETE should take O (1) time.                                                                           

Ans:

Implementation of queue by using a singly linked list:

When implement a queue as a single liked list, a queue q consists of a list and two pointers, q.front and the q.rear.

inserting an element is stated below:

insert(q,x)

{

p=getnode(); info(p) = x; next(p) = null; if(q.rear == null)

q.front = p;

else

next(q.rear) = p;

q.rear = p;

}

deletion is stated below:

remove(q)

{

if(empty(q))

{

printf("queue overflow");

exit(1);

}

p=q.front; x=info(p); q.front=next(p); if(q.front == null) q.rear = null; freenode(p); return(x);

}

Posted Date: 7/10/2012 3:53:23 AM | Location : United States







Related Discussions:- Implementation of queue by using a single linked list, Assignment Help, Ask Question on Implementation of queue by using a single linked list, Get Answer, Expert's Help, Implementation of queue by using a single linked list Discussions

Write discussion on Implementation of queue by using a single linked list
Your posts are moderated
Related Questions
Example 1:  Following are Simple sequence of statements Statement 1;  Statement 2; ... ... Statement k; The entire time can be found out through adding the times for

A driver takes shortest possible route to attain destination. The problem which we will discuss here is similar to this type of finding shortest route in any specific graph. The gr

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

advanatges of dynamic data structure in programming

In what ways we can get the context sensitive F1 help on a field?' Data element documentation. Data element additional text in screen painter. Using the process on help r

As we have seen, as the traversal mechanisms were intrinsically recursive, the implementation was also easy through a recursive procedure. Though, in the case of a non-recursive me

Linked List  A linked list is a linear collection of data elements called nodes. The linear order is given by pointer. Every node is divided into 2 or more parts.

important points on asymptotic notation to remember

Best Case: If the list is sorted already then A[i] T (n) = c1n + c2 (n -1) + c3(n -1) + c4 (n -1)  = O (n), which indicates that the time complexity is linear. Worst Case:

Your program should include three components selling, buying and managing for the use of sellers, buyers and the Manager, respectively. Provide a menu for a user to enter each comp