Using C, first, complete the linked list implementation of the deque. To do this, implement all functions with the // FIXME... comments in linkedList.c . Files below.

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

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; }

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 }