Question
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.
Solution Preview
This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.
#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);
}...