Use the header and other files listed below for problems 1 and 2. Each problem has 3 files that correspond to the problem.

Problem 1, linked list deque and bag implementations.

First, complete the linked list implementation of the deque and bag ADTs in C language. To do this, implement all functions with the // FIXME... comments in linkedList.c (File included below). These functions listed are the ones that need to be fixed. init addLinkBefore removeLink linkedListAddFront linkedListAddBack linkedListFront linkedListBack linkedListRemoveFront linkedListRemoveBack linkedListIsEmpty linkedListPrint linkedListContains linkedListRemove

Problem 2: Circularly Linked List Deque implementation Using the circularList.c (listed below) for this problem, you will implement the Deque ADT with a CircularlyDoublyLinked List with a Sentinel. As you know, the sentinel is a special link, does not contain a meaningful 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. Implement all functions with the // FIXME... comments in circularList.c. init createLink addLinkAfter removeLink circularListAddBack circularListAddFront circularListFront circularListBack circularListRemoveFront circularListRemoveBack circularListDestroy circularListIsEmpty circularListPrint

circularListReverse 6 pts

As usual do not make any modifications to the header files or include any additional headers, and make sure everything compiles and runs. circularList.h

#ifndef CIRCULAR_LIST_H #define CIRCULAR_LIST_H

#ifndef TYPE #define TYPE double #endif

#ifndef LT #define LT(A, B) ((A) < (B)) #endif

#ifndef EQ #define EQ(A, B) ((A) == (B)) #endif

struct CircularList;

struct CircularList* circularListCreate(); void circularListDestroy(struct CircularList* list); void circularListPrint(struct CircularList* list); void circularListReverse(struct CircularList* list);

// Deque interface

void circularListAddFront(struct CircularList* list, TYPE value); void circularListAddBack(struct CircularList* list, TYPE value); TYPE circularListFront(struct CircularList* list); TYPE circularListBack(struct CircularList* list); void circularListRemoveFront(struct CircularList* list); void circularListRemoveBack(struct CircularList* list); int circularListIsEmpty(struct CircularList* list);

#endif

circularList.c

#include #include #include #include "circularList.h"

// Double link struct Link { TYPE value; struct Link * next; struct Link * prev; };

struct CircularList { int size; struct Link* sentinel; };

/** * Allocates the list's sentinel and sets the size to 0. * The sentinel's next and prev should point to the sentinel itself. */ static void init(struct CircularList* list) { // FIXME: you must write this }

/** * Creates a link with the given value and NULL next and prev pointers. */ static struct Link* createLink(TYPE value) { // FIXME: you must write this return NULL; }

/** * Adds a new link with the given value after the given link and * increments the list's size. */ static void addLinkAfter(struct CircularList* list, struct Link* link, TYPE value) { // FIXME: you must write this }

/** * Removes the given link from the list and * decrements the list's size. */ static void removeLink(struct CircularList* list, struct Link* link) { // FIXME: you must write this }

/** * Allocates and initializes a list. */ struct CircularList* circularListCreate() { struct CircularList* list = malloc(sizeof(struct CircularList)); init(list); return list; }

/** * Deallocates every link in the list and frees the list pointer. */ void circularListDestroy(struct CircularList* list) { // FIXME: you must write this }

/** * Adds a new link with the given value to the front of the deque. */ void circularListAddFront(struct CircularList* list, TYPE value) { // FIXME: you must write this }

/** * Adds a new link with the given value to the back of the deque. */ void circularListAddBack(struct CircularList* list, TYPE value) { // FIXME: you must write this }

/** * Returns the value of the link at the front of the deque. */ TYPE circularListFront(struct CircularList* list) { // FIXME: you must write this return 0; }

/** * Returns the value of the link at the back of the deque. */ TYPE circularListBack(struct CircularList* list) { // FIXME: you must write this return 0; }

/** * Removes the link at the front of the deque. */ void circularListRemoveFront(struct CircularList* list) { // FIXME: you must write this }

/** * Removes the link at the back of the deque. */ void circularListRemoveBack(struct CircularList* list) { // FIXME: you must write this }

/** * Returns 1 if the deque is empty and 0 otherwise. */ int circularListIsEmpty(struct CircularList* list) { // FIXME: you must write this return 0; }

/** * Prints the values of the links in the deque from front to back. */ void circularListPrint(struct CircularList* list) { // FIXME: you must write this }

/** * Reverses the deque. */ void circularListReverse(struct CircularList* list) { // FIXME: you must write this }

circularListMain.c

#include "circularList.h" #include

int main() { struct CircularList* deque = circularListCreate(); circularListAddBack(deque, (TYPE)1); circularListAddBack(deque, (TYPE)2); circularListAddBack(deque, (TYPE)3); circularListAddFront(deque, (TYPE)4); circularListAddFront(deque, (TYPE)5); circularListAddFront(deque, (TYPE)6); circularListPrint(deque); printf("%g ", circularListFront(deque)); printf("%g ", circularListBack(deque)); circularListRemoveFront(deque); circularListRemoveBack(deque); circularListPrint(deque); circularListReverse(deque); circularListPrint(deque); circularListDestroy(deque); return 0; }

linkedList.h

#ifndef LINKED_LIST_H #define LINKED_LIST_H

#ifndef TYPE #define TYPE int #endif

#ifndef LT #define LT(A, B) ((A) < (B)) #endif

#ifndef EQ #define EQ(A, B) ((A) == (B)) #endif

struct LinkedList;

struct LinkedList* linkedListCreate(); void linkedListDestroy(struct LinkedList* list); void linkedListPrint(struct LinkedList* list);

// Deque interface

int linkedListIsEmpty(struct LinkedList* list); void linkedListAddFront(struct LinkedList* list, TYPE value); void linkedListAddBack(struct LinkedList* list, TYPE value); TYPE linkedListFront(struct LinkedList* list); TYPE linkedListBack(struct LinkedList* list); void linkedListRemoveFront(struct LinkedList* list); void linkedListRemoveBack(struct LinkedList* list);

// Bag interface

void linkedListAdd(struct LinkedList* list, TYPE value); int linkedListContains(struct LinkedList* list, TYPE value); void linkedListRemove(struct LinkedList* list, TYPE value);

#endif

linkedList.c

#include "linkedList.h" #include #include #include

// Double link struct Link { TYPE value; struct Link* next; struct Link* prev; };

// Double linked list with front and back sentinels struct LinkedList { int size; struct Link* frontSentinel; struct Link* backSentinel; };

/** * Allocates the list's sentinel and sets the size to 0. * The sentinels' next and prev should point to eachother or NULL * as appropriate. */ static void init(struct LinkedList* list) { // FIXME: you must write this }

/** * Adds a new link with the given value before the given link and * increments the list's size. */ static void addLinkBefore(struct LinkedList* list, struct Link* link, TYPE value) { // FIXME: you must write this }

/** * Removes the given link from the list and * decrements the list's size. */ static void removeLink(struct LinkedList* list, struct Link* link) { // FIXME: you must write this }

/** * Allocates and initializes a list. */ struct LinkedList* linkedListCreate() { struct LinkedList* newDeque = malloc(sizeof(struct LinkedList)); init(newDeque); return newDeque; }

/** * Deallocates every link in the list including the sentinels, * and frees the list itself. */ void linkedListDestroy(struct LinkedList* list) { while (!linkedListIsEmpty(list)) { linkedListRemoveFront(list); } free(list->frontSentinel); free(list->backSentinel); free(list); }

/** * Adds a new link with the given value to the front of the deque. */ void linkedListAddFront(struct LinkedList* list, TYPE value) { // FIXME: you must write this }

/** * Adds a new link with the given value to the back of the deque. */ void linkedListAddBack(struct LinkedList* list, TYPE value) { // FIXME: you must write this }

/** * Returns the value of the link at the front of the deque. */ TYPE linkedListFront(struct LinkedList* list) { // FIXME: you must write this }

/** * Returns the value of the link at the back of the deque. */ TYPE linkedListBack(struct LinkedList* list) { // FIXME: you must write this }

/** * Removes the link at the front of the deque. */ void linkedListRemoveFront(struct LinkedList* list) { // FIXME: you must write this }

/** * Removes the link at the back of the deque. */ void linkedListRemoveBack(struct LinkedList* list) { // FIXME: you must write this }

/** * Returns 1 if the deque is empty and 0 otherwise. */ int linkedListIsEmpty(struct LinkedList* list) { // FIXME: you must write this }

/** * Prints the values of the links in the deque from front to back. */ void linkedListPrint(struct LinkedList* list) { // FIXME: you must write this }

/** * Adds a link with the given value to the bag. */ void linkedListAdd(struct LinkedList* list, TYPE value) { // FIXME: you must write this }

/** * Returns 1 if a link with the value is in the bag and 0 otherwise. */ int linkedListContains(struct LinkedList* list, TYPE value) { // FIXME: you must write this }

/** * Removes the first occurrence of a link with the given value. */ void linkedListRemove(struct LinkedList* list, TYPE value) { // FIXME: you must write this }

linkedListMain.c

#include "linkedList.h" #include

int main(){ struct LinkedList* l = linkedListCreate(); linkedListAddFront(l, (TYPE)1); linkedListAddBack(l, (TYPE)2); linkedListAddBack(l, (TYPE)3); linkedListAddFront(l, (TYPE)4); linkedListAddFront(l, (TYPE)5); linkedListAddBack(l, (TYPE)6); linkedListPrint(l); printf("%i ", linkedListFront(l)); printf("%i ", linkedListBack(l)); linkedListRemoveFront(l); linkedListRemoveBack(l); linkedListPrint(l); /* BAG */ struct LinkedList* k = linkedListCreate(); linkedListAdd (k, (TYPE)10); linkedListAdd (k, (TYPE)11); linkedListAdd (k, (TYPE)13); linkedListAdd(k, (TYPE)14); linkedListRemove(k, (TYPE)11); linkedListPrint(k); return 0; }