Implementation of the Deque ADT Using a Circularly Linked List

Implementation of the Deque ADT using a Circularly linked list.
For this problem, you will implement the Deque ADT with a Circularly -­‐ Doubly -­‐ Linked List with a Sentinel.
As you know, the sentinel is a special link, does not contain a value, and should not be removed.
Using a sentinel makes some linked list operations easier and cleaner in implementation.
This list is circular, meaning the end points back to the beginning, thus one sentinel suffices.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <float.h>
#include "cirListDeque.h"

/* Double Link Struture */
struct DLink {
TYPE value;/* value of the link */
struct DLink * next;/* pointer to the next link */
struct DLink * prev;/* pointer to the previous link */
};

# define TYPE_SENTINEL_VALUE DBL_MAX


/* ************************************************************************
Deque ADT based on Circularly-Doubly-Linked List WITH Sentinel
************************************************************************ */

struct cirListDeque {
int size;/* number of links in the deque */
struct DLink *Sentinel; /* pointer to the sentinel */
};
/* internal functions prototypes */
struct DLink* _createLink (TYPE val);
void _addLinkAfter(struct cirListDeque *q, struct DLink *lnk, TYPE v);
void _removeLink(struct cirListDeque *q, struct DLink *lnk);



/* ************************************************************************
Deque Functions
************************************************************************ */

/* Initialize deque.

param: q pointer to the deque
pre: q is not null
post: q->Sentinel is allocated and q->size equals zero
*/
void _initCirListDeque (struct cirListDeque *q)
{
/* FIXME: you must write this */
assert( q != NULL);
q->size = 0;
q->Sentinel = (struct DLink *) malloc(sizeof(struct DLink));
q->Sentinel->next = q->Sentinel;
q->Sentinel->prev = q->Sentinel;
}

/*
create a new circular list deque

*/

struct cirListDeque *createCirListDeque()
{
struct cirListDeque *newCL = malloc(sizeof(struct cirListDeque));
_initCirListDeque(newCL);
return(newCL);
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution