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 */


/* ************************************************************************
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));

By purchasing this solution you'll be able to access the following files:

50% discount

$50.00 $25.00
for this solution

or FREE if you
register a new account!

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.

Upload a file
Continue without uploading

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