Using C, first, complete the linked list implementation of the deque. To do this

Question

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 <stdio.h>

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 <assert.h>
#include <stdlib.h>
#include <stdio.h>

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

Explanation / Answer

#include "linkedList.h"
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
// 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)
{
list->size=0;
list->backSentinel=NULL;
list->frontSentinel=NULL;
}
/**
* 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)
{
struct Link* link1=(struct Link*)malloc(sizeof(struct Link));
link1->value=value;
link1->next=link;
link->prev=link1;
list->size+=1;
}
/**
* Removes the given link from the list and
* decrements the list's size.
*/
static void removeLink(struct LinkedList* list, struct Link* link)
{
struct Link* start=list->frontSentinel;
struct Link* previ;
previ=NULL;
while(start!=list->backSentinel)
{
if(start->value==link->value)
{
break;
}
previ=start;
start=start->prev;
}
if(previ!=NULL)
{
previ->prev=link->prev;
link->prev->next=previ;
free(link);
}
if(previ==NULL)
{
list->frontSentinel=link->prev;
free(link);
}
list->size=-1;
}
/**
* 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)
{
struct Link* new=(struct Link*)malloc(sizeof(struct Link));
new->value=value;
new->next=NULL;
new->prev=NULL;
if(list->frontSentinel==NULL)
{
list->frontSentinel=new;
list->backSentinel=new;
}
else
{
list->frontSentinel->next=new;
new->prev=list->frontSentinel;
list->frontSentinel=new;
list->frontSentinel->next=NULL;
}
}
/**
* Adds a new link with the given value to the back of the deque.
*/
void linkedListAddBack(struct LinkedList* list, TYPE value)
{
struct Link* new=(struct Link*)malloc(sizeof(struct Link));
new->value=value;
new->next=NULL;
new->prev=NULL;
if(list->backSentinel==NULL)
{
list->frontSentinel=new;
list->backSentinel=new;
list->backSentinel->next=NULL;
list->backSentinel->prev=NULL;
list->frontSentinel->next=NULL;
list->frontSentinel->prev=NULL;
}
else
{
list->backSentinel->prev=new;
new->next=list->backSentinel;
list->backSentinel=new;
list->backSentinel->prev=NULL;
}
}
/**
* Returns the value of the link at the front of the deque.
*/
TYPE linkedListFront(struct LinkedList* list)
{
return(list->frontSentinel->value);
}
/**
* Returns the value of the link at the back of the deque.
*/
TYPE linkedListBack(struct LinkedList* list)
{
return(list->backSentinel->value);
}
/**
* Removes the link at the front of the deque.
*/
void linkedListRemoveFront(struct LinkedList* list)
{
struct Link* front=list->frontSentinel;
list->frontSentinel=list->frontSentinel->prev;
free(front);
}
/**
* Removes the link at the back of the deque.
*/
void linkedListRemoveBack(struct LinkedList* list)
{
struct Link *rear=list->backSentinel;
list->backSentinel=list->backSentinel->next;
free(rear);
}
/**
* Returns 1 if the deque is empty and 0 otherwise.
*/
int linkedListIsEmpty(struct LinkedList* list)
{
if(list->backSentinel==NULL && list->frontSentinel==NULL)
return 1;
return 0;
}
/**
* Prints the values of the links in the deque from front to back.
*/
void linkedListPrint(struct LinkedList* list)
{
struct Link* start=list->frontSentinel;
printf(" ");
while(start!=NULL)
{
printf("%d->",start->value);
start=start->prev;}
}
/**
* Adds a link with the given value to the bag.
*/
void linkedListAdd(struct LinkedList* list, TYPE value)
{
linkedListAddBack(list,value);
}
/**
* Returns 1 if a link with the value is in the bag and 0 otherwise.
*/
int linkedListContains(struct LinkedList* list, TYPE value)
{
if(list->backSentinel->value==value)
return 1;
return 0;

}
/**
* Removes the first occurrence of a link with the given value.
*/
void linkedListRemove(struct LinkedList* list, TYPE value)
{
struct Link* start=list->frontSentinel;
while(start!=list->backSentinel)
{
if(start->value==value)
{
removeLink(list, start);
break;
}
start=start->prev;
}
}

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.