Linked list implementation of a dequeue, Data Structure & Algorithms

Assignment Help:

Double ended queues are implemented along doubly linked lists.

A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and right pointers. The right pointer points to the next node at the right while the left pointer points to the previous node at the left.  Program 9 described the linked list implementation of a Dequeue.

Program 9 : Linked list implementation of a Dequeue

# include "stdio.h"

#define NULL 0

struct dq {

int info;

int *left;

int *right;

};

typedef struct dq *dqptr;

dqptr p, tp;

dqptr head;

dqptr tail;

main()

{

int choice, I, x;

dqptr n;

dqptr getnode();

printf("\n Enter 1: Start 2 : Insertion at Front 3 : Insertion at Rear 4: Delete at Front 5: Delete at Back");

while (1)

{

printf("\n 1: Start 2 : Add at Front 3 : Add at Back 4: Delete at Front 5: Delete at Back 6 : exit");

scanf("%d", &choice);

switch (choice)

{

case 1:

create_list();

break;

case 2:

eq_front();

break;

case 3:

eq_back();

break;

case 4:

dq_front();

break;

case 5:

 

dq_back();

break;

case 6 :

exit(6);

}

}

}

create_list()

{

int I, x;

dqptr t;

p = getnode();

tp = p;

p->left = getnode();

p->info = 10;

p_right = getnode();

return;

}

dqptr getnode()

{

p = (dqptr) malloc(sizeof(struct dq));

return p;

}

dq_empty(dq q)

{

return q->head = = NULL;

}

eq_front(dq q, void *info)

{

if (dq_empty(q))

q->head = q->tail = dcons(info, NULL, NULL);

else

{

q-> head -> left =dcons(info, NULL, NULL);

q->head -> left ->right = q->head;

q ->head = q->head ->left;

}

}

eq_back(dq q, void *info)

{

if (dq_empty(q))

q->head = q->tail = dcons(info, NULL, NULL)

else

{

q-> tail -> right =dcons(info, NULL, NULL);

q->tail -> right -> left = q->tail;

q ->tail  = q->tail ->right;

}

}

dq_front(dq q)

{

if dq is not empty

{

dq tp = q-> head;

void *info = tp -> info;

q ->head = q->head-> right;

free(tp);

if (q->head = = NULL)

q -> tail = NULL;

else

q -> head -> left = NULL;

return info;

}

}

dq_back(dq q)

{

if (q!=NULL)

{

dq tp = q-> tail;

*info = tp -> info;

q ->tail = q->tail-> left;

free(tp);

if (q->tail = = NULL)

q -> head = NULL;

else

q -> tail -> right = NULL;

return info;

}

}


Related Discussions:- Linked list implementation of a dequeue

Various passes of bubble sort, Q. Show the various passes of bubble sort on...

Q. Show the various passes of bubble sort on the unsorted given list 11, 15, 2, 13, 6           Ans: The given data is as follows:- Pass 1:-     11   15   2     13

Explain how two dimensional arrays are represented in memory, Explain how t...

Explain how two dimensional arrays are represented in memory. Representation of two-dimensional arrays in memory:- Let grades be a 2-D array as grades [3][4]. The array will

Polynomials, Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8...

Polynomials like  5x 4    +  2x 3    +  7x 2     +  10x  -  8  can  be  represented by using arrays. Arithmetic operations such as addition & multiplication of polynomials are com

Frequency count, what is frequency count with examble

what is frequency count with examble

Mathematical-model with a collection of operations, A mathematical-model wi...

A mathematical-model with a collection of operations described on that model is known as??? Abstract Data Type

Sequential search of a list is preferred over binary search, What are the c...

What are the conditions under which sequential search of a list is preferred over binary search? Sequential Search is a preferred over binary search when the list is unordered

Program, insertion and deletion in a tree

insertion and deletion in a tree

Algorithm to sort a given list by quick sort method, Q. Write down an algor...

Q. Write down an algorithm to sort a given list by making use of Quick sort method. Describe the behaviour of Quick sort when input given to us is already sorted.

Green computing, In the present scenario of global warming, the computer ha...

In the present scenario of global warming, the computer hard ware and software are also contributing for the increase in the temperature in the environment and contributing for the

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd