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

Create a binary tree , Create a class "box" that will contain a random inte...

Create a class "box" that will contain a random integer value v such that O

Depth-First Traversal, With the help of a program and a numerical example e...

With the help of a program and a numerical example explain the Depth First Traversal of a tree.

Data searching, In file access: what is the difference between serial, seq...

In file access: what is the difference between serial, sequential and indexed sequential searching

Explain insertion sort, Q. Explain the insertion sort with a proper algorit...

Q. Explain the insertion sort with a proper algorithm. What is the complication of insertion sort in the worst case?

Complexity classes, Complexity classes All decision problems fall in se...

Complexity classes All decision problems fall in sets of comparable complexity, called as complexity classes. The complexity class P is the set of decision problems which ca

Polynomials - represented by using arrays, /* the program accepts two polyn...

/* the program accepts two polynomials as a input & prints the resultant polynomial because of the addition of input polynomials*/ #include void main() { int poly1[6][

Multiple stacks, how multiple stacks can be implemented using one dimension...

how multiple stacks can be implemented using one dimensional array

Relative and direct files, Each data record contains a fixed place in a rel...

Each data record contains a fixed place in a relative file. Each record ought to have associated with it in integer key value which will help identify this slot. Therefore, this ke

Define a tree and list its properties, QUESTION (a) Define a tree and l...

QUESTION (a) Define a tree and list its properties. (b) By showing all your workings, draw the spanning tree for the following graph based on the Breadth-First-Search algori

Functions for inserting and deleting at either end of deque, Q. Devise a re...

Q. Devise a representation for a given list where insertions and deletions can be made at both the ends. Such a structure is called Deque (which means Double ended queue). Write fu

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