Page 181 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes return dq[rear];
}
}
}

10.5.2 Linked List Implementation of a Dequeue

Double ended queues are implemented with doubly linked lists.

Notes A doubly link list can traverse in both the directions as it has two pointers namely
left and right. The right pointer points to the next node on the right where as the left
pointer points to the previous node on the left.

Program given below gives the 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: Add at Front 3: Add 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;

174 LOVELY PROFESSIONAL UNIVERSITY