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

The smallest element of an array''s index, The smallest element of an array...

The smallest element of an array's index is called its Lower bound.

frequenty count of function, Ask question find frequency count of function...

Ask question find frequency count of function- {for(i=1;i {for(j=1;j {for(k=1;k } } }

Hashing and hash functions, Q. Describe the term hashing. Explain any two u...

Q. Describe the term hashing. Explain any two usually used hash functions. Explain one method of collision resolution.

Algorithm to add an element at the end of linked list, Write an algorithm t...

Write an algorithm to add an element at the end of circular linked list.   Algorithm to Add the Element at the End of Circular Linked List. IINSENDCLL( INFO, LINK, START, A

How do collisions happen during hashing, How do collisions happen during ha...

How do collisions happen during hashing? Usually the key space is much larger than the address space, thus, many keys are mapped to the same address. Assume that two keys K1 an

Compound interest, Write the algorithm for compound interest

Write the algorithm for compound interest

Brute force, Determine the number of character comparisons made by the brut...

Determine the number of character comparisons made by the brute-force algorithm in searching for the pattern GANDHI in the text

Algorithm for stack using array, write an algorithm for stack using array p...

write an algorithm for stack using array performing the operations as insertion ,deletion , display,isempty,isfull.

Program, What is a first-in-first-out data structure ? Write algorithms to...

What is a first-in-first-out data structure ? Write algorithms to perform the following operations on it – create, insertion, deletion, for testing overflow and empty conditions.

Design and implement a software system, In this assignment, you are invited...

In this assignment, you are invited to design and implement a software system for catalogue sale. A catalogue is organised in a tree structure. Each node of the catalogue tree repr

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