QuestionQuestion

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.

Solution PreviewSolution 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);
}...
$50.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats