Question
#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)
#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
#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) {
struct Link * front = (struct Link*)malloc(sizeof(struct Link));
assert(front != 0);
struct Link * back = (struct Link*)malloc(sizeof(struct Link));
assert(back != 0);
front->prev = back;
front->next = NULL;
back->prev = NULL;
back->next = front;
list->frontSentinel = front;
list->backSentinel = back;
list->size = 0;
}
/**
* 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)
{
// Create new link
struct Link * newLink = (struct Link*)malloc(sizeof(struct Link));
// Save previous link
struct Link * behindNewLink;
behindNewLink = link->prev;
// Assign pointer to newLink
link->prev = newLink;
behindNewLink->next = newLink;
// Assign pointers from newLink
newLink->prev = behindNewLink;
newLink->next = link;
// Add value to newLink
newLink->value = value;
// Increment size
list->size++;
}
/**
* Removes the given link from the list and
* decrements the list's size.
*/
static void removeLink(struct LinkedList* list, struct Link* link)
{
assert(list->size != 0);
struct Link * deleteMe = link;
struct Link * beforeDeleteMe = link->prev;
struct Link * afterDeleteMe = link->next;
// Reassign pointers of links before and after deleteMe
beforeDeleteMe->next = afterDeleteMe;
afterDeleteMe->prev = beforeDeleteMe;
// Clear pointers and delete link
deleteMe->next = NULL;
deleteMe->prev = NULL;
free(deleteMe);
// Decrement size
list->size--;
}
/**
* 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)
{
// Checked!
struct Link * newLink = (struct Link *)malloc(sizeof(struct Link));
struct Link * prevFront;
prevFront = (list->frontSentinel)->prev;
// Assign prev of front sentinel && next of link before front sentinel
prevFront->next = newLink;
(list->frontSentinel)->prev = newLink;
// Assign front and prev of newLink
newLink->next = list->frontSentinel;
newLink->prev = prevFront;
// Assign value to new link
newLink->value = value;
// Increment size of linked list
list->size++;
}
/**
* Adds a new link with the given value to the back of the deque.
*/
void linkedListAddBack(struct LinkedList* list, TYPE value)
{
struct Link * newLink = (struct Link *)malloc(sizeof(struct Link));
struct Link * prevBack;
prevBack = (list->backSentinel)->next;
// Assign next of back sentinel && prev of link after back sentinel
prevBack->prev = newLink;
(list->backSentinel)->next = newLink;
// Assign front and prev of newLink
newLink->prev = list->backSentinel;
newLink->next = prevBack;
// Assign value to new link
newLink->value = value;
// Increment size of linked list
list->size++;
}
/**
* Returns the value of the link at the front of the deque.
*/
TYPE linkedListFront(struct LinkedList* list)
{
assert(list->size != 0);
return list->backSentinel->next->value;
}
/**
* Returns the value of the link at the back of the deque.
*/
TYPE linkedListBack(struct LinkedList* list)
{
assert(list->size != 0);
return list->frontSentinel->prev->value;
}
/**
* Removes the link at the front of the deque.
*/
void linkedListRemoveFront(struct LinkedList* list)
{
assert(list->size != 0);
// Link to Delete
struct Link * deleteMe;
deleteMe = list->frontSentinel->prev;
// New link at front
struct Link * newFront;
newFront = list->frontSentinel->prev->prev;
// Reassign front-sentinel prev and newFront next to each other
newFront->next = list->frontSentinel;
list->frontSentinel->prev = newFront;
// Deallocate memory for delete node
deleteMe->prev = NULL;
deleteMe->next = NULL;
free(deleteMe);
deleteMe = NULL;
// Decrement size of linked list
list->size--;
}
/**
* Removes the link at the back of the deque.
*/
void linkedListRemoveBack(struct LinkedList* list)
{
assert(list->size != 0);
// Link to Delete
struct Link * deleteMe;
deleteMe = list->backSentinel->next;
// New link in back
struct Link * newBack;
newBack = list->backSentinel->next->next;
// Reassign back-sentinel next and newBack prev to each other
newBack->prev = list->backSentinel;
list->backSentinel->next = newBack;
// Remove pointers and delete link
deleteMe->next = NULL;
deleteMe->prev = NULL;
free(deleteMe);
deleteMe = NULL;
// Decrement size of linked list
list->size--;
}
/**
* Returns 1 if the deque is empty and 0 otherwise.
*/
int linkedListIsEmpty(struct LinkedList* list)
{
if (list->size == 0) {
return 1;
}
else {
return 0;
}
}
/**
* Prints the values of the links in the deque from front to back.
*/
void linkedListPrint(struct LinkedList* list)
{
assert(list->size != 0);
struct Link * printVal = list->frontSentinel->prev;
do {
printf(" %d ", printVal->value);
printVal = printVal->prev;
} while (printVal->prev != 0);
}
/**
* 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)
{
assert(list->size != 0);
struct Link * currLink = list->frontSentinel->prev;
do {
if (currLink->value == value) {
return 1;
}
currLink = currLink->prev;
} while (currLink->prev != 0);
return 0;
}
/**
* Removes the first occurrence of a link with the given value.
*/
void linkedListRemove(struct LinkedList* list, TYPE value)
{
assert(list->size != 0);
assert(linkedListContains(list, value));
struct Link * currLink = list->frontSentinel->prev;
do {
if (currLink->value == value) {
currLink->next->prev = currLink->prev;
currLink->prev->next = currLink->next;
currLink->next = NULL;
currLink->prev = NULL;
free(currLink);
//Decrement size
list->size--;
return;
}
currLink = currLink->prev;
} while (currLink != 0);
}
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);
linkedListDestroy(k);
return 0;
}
when I try to compile, it shows that "error invalid conversion from void to LinkedList {-fpermissive} struct linedlist* newDeque=malloc(sizeof(struct LinkedList))"
how i can change it?
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started