linked lists Implementation

linked lists Implementation:

Linked lists can be used for implementing queues. We plan to maintain a dummy node at the beginning and two pointers, the first pointing to this dummy node and the second pointing to the last element. Both insertion and deletion are easy at the beginning. Insertion is easy at the end, but deletion is difficult at the end, since we have to move the pointer at the end one step back and there is no way other than traversing the entire list in order to trace the new end. So the natural choice is to take the beginning of the linked list as the front of the queue and the end of the list as the back of the queue.

The corresponding implementation is detailed below: typedefstruct _node {

char element;

struct _node *next;

} node; typedefstruct { node *front; node *back;

} queue; queueinit ()

{

queue Q;

/* Create the dummy node */

Q.front = (node *)malloc(sizeof(node)); Q.front -> element = ' ';

Q.front -> next = NULL; Q.back = Q.front;

return Q;

}

intisEmpty ( queue Q )

{

return (Q.front == Q.back);

}

intisFull ( queue Q )

{

return 0;

}

char front ( queue Q )

{

if (isEmpty(Q)) {

fprintf(stderr,"front: Queue is empty\n"); return '\0';

}

returnQ.front -> element;

}

queueenqueue ( queue Q , char ch )

{

node *C;

if (isFull(Q)) {

fprintf(stderr,"enqueue: Queue is full\n"); return Q;

}

/* Create new node */

C = (node *)malloc(sizeof(node));

C -> element = ch;

C -> next = NULL;

/* Adjust the back of queue */

Q.back -> next = C;

Q.back = C; return Q;

}

queuedequeue ( queue Q )

{

if (isEmpty(Q)) {

fprintf(stderr,"dequeue: Queue is empty\n"); return Q;

}

/* Make the front of the queue the new dummy node */

Q.front = Q.front -> next;

Q.front -> element = '\0'; return Q;

}

void print ( queue Q )

{

node *G;

G = Q.front -> next; while (G != NULL) { printf("%c", G -> element); G = G -> next;

}

}

And here is the program with a main() identical to that for the array implementation.