I am doing a Circular Linked List Deque assignment in C. The code runs fine and the outputs are as expected, but for some reason after the circularListReverse()
void circularListReverse(struct CircularList* list)
{
assert(!circularListIsEmpty(list));
struct Link *curLink;
struct Link *tempLink;
curLink = list->sentinel;
do {
tempLink = curLink->next;
curLink->next = curLink->prev;
curLink->prev = tempLink;
curLink = tempLink;
} while (curLink != list->sentinel);
}
is called on the list, the circularListPrint()
void circularListPrint(struct CircularList* list)
{
assert(!circularListIsEmpty(list));
struct Link *newLink = list->sentinel->next;
while(newLink != list->sentinel) {
printf("%g ", newLink->value);
newLink = newLink->next;
}
printf("\n"); //This prints, so it exits the loop
}
function hangs after it prints all of the expected results. After troubleshooting for hours I have found that the program exits the while loop which does the printing, but does not exit the function. This function DOES work properly before the reverse function is called. Why is it hanging?
Below is the driver:
#include "circularList.h"
#include <stdio.h>
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); //Works fine
printf("%g\n", circularListFront(deque));
printf("%g\n", circularListBack(deque));
circularListRemoveFront(deque);
circularListRemoveBack(deque);
circularListPrint(deque);
circularListReverse(deque);
circularListPrint(deque); //HANGS
//Debug
printf("\nEnd of print\n"); //This does NOT print, so function never exits
circularListDestroy(deque);
return 0;
}
List and Link structures:
struct Link
{
TYPE value;
struct Link * next;
struct Link * prev;
};
struct CircularList
{
int size;
struct Link* sentinel;
};
Add functions:
static void addLinkAfter(struct CircularList* list, struct Link* link, TYPE value)
{
assert(link != NULL);
struct Link *newLink = createLink(value);
newLink->prev = link;
newLink->next = link->next;
newLink->next->prev = newLink;
link->next = newLink;
list->size++;
}
/**
* Adds a new link with the given value to the front of the deque.
*/
void circularListAddFront(struct CircularList* list, TYPE value)
{
assert(list != NULL);
addLinkAfter(list, list->sentinel, value);
}
/**
* Adds a new link with the given value to the back of the deque.
*/
void circularListAddBack(struct CircularList* list, TYPE value)
{
assert(list != NULL);
addLinkAfter(list, list->sentinel->prev, value);
}
Create Circular List:
/**
* Allocates and initializes a list.
*/
struct CircularList* circularListCreate()
{
struct CircularList* list = malloc(sizeof(struct CircularList));
init(list);
return list;
}
/**
* 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)
{
assert(list != 0);
list->sentinel = (struct Link *)malloc(sizeof(struct Link));
assert(list->sentinel != 0);
list->sentinel->next = list->sentinel;
list->sentinel->prev = list->sentinel;
list->size = 0;
list->sentinel->value = 0;
}
Removes:
static void removeLink(struct CircularList* list, struct Link* link)
{
// FIXME: you must write this
assert(!circularListIsEmpty(list));
assert(link != NULL);
link->prev->next = link->next;
link->next->prev = link->prev;
free(link);
list->size--;
}
/**
* Removes the link at the front of the deque.
*/
void circularListRemoveFront(struct CircularList* list)
{
assert(!circularListIsEmpty(list));
removeLink(list, list->sentinel->next);
}
/**
* Removes the link at the back of the deque.
*/
void circularListRemoveBack(struct CircularList* list)
{
assert(!circularListIsEmpty(list));
removeLink(list, list->sentinel->prev);
}
The output is
6 5 4 1 2 3
6
3
5 4 1 2
2 1 4 5
//Cursor sits here and program doesn't exit
Can't reproduce. This code works fine (fixing memory leaks left as the reader's exercise). This code doesn't execute circularListRemoveFront and circularListRemoveBack (because you didn't paste their code), therefore it is likely one or both of them may be the culprit.
My code differs with circularListCreate implementation (there was no code of it pasted initially) but this is unlikely to be the issue.
EDIT:
Added circularListRemoveBack and circularListRemoveFront after you pasted their code. Code works, you must have some local issue. Please copy, paste and compile, try if it works.
output is:
6 5 4 1 2 3
5 4 1 2
2 1 4 5
#include <stdio.h>
#include <stdlib.h>
#define TYPE double
struct Link
{
double value;
struct Link * next;
struct Link * prev;
};
struct CircularList
{
int size;
struct Link* sentinel;
};
void circularListReverse(struct CircularList* list)
{
struct Link *curLink;
struct Link *tempLink;
curLink = list->sentinel;
do {
tempLink = curLink->next;
curLink->next = curLink->prev;
curLink->prev = tempLink;
curLink = tempLink;
} while (curLink != list->sentinel);
}
void circularListPrint(struct CircularList* list)
{
struct Link *newLink = list->sentinel->next;
while(newLink != list->sentinel) {
printf("%g ", newLink->value);
newLink = newLink->next;
}
printf("\n"); //This prints, so it exits the loop
}
struct Link* createLink(TYPE value)
{
struct Link *l = malloc(sizeof(struct Link));
l->value = value;
return l;
}
static void addLinkAfter(struct CircularList* list, struct Link* link, TYPE value)
{
struct Link *newLink = createLink(value);
newLink->prev = link;
newLink->next = link->next;
newLink->next->prev = newLink;
link->next = newLink;
list->size++;
}
/**
* Adds a new link with the given value to the front of the deque.
*/
void circularListAddFront(struct CircularList* list, TYPE value)
{
addLinkAfter(list, list->sentinel, value);
}
/**
* Adds a new link with the given value to the back of the deque.
*/
void circularListAddBack(struct CircularList* list, TYPE value)
{
addLinkAfter(list, list->sentinel->prev, value);
}
static void removeLink(struct CircularList *list, struct Link *link)
{
link->prev->next = link->next;
link->next->prev = link->prev;
free(link);
list->size--;
}
void circularListRemoveBack(struct CircularList* list)
{
removeLink(list, list->sentinel->prev);
}
void circularListRemoveFront(struct CircularList* list)
{
removeLink(list, list->sentinel->next);
}
struct CircularList* create()
{
struct CircularList *l = malloc(sizeof(*l));
l->sentinel = malloc(sizeof(*l->sentinel));
l->sentinel->prev = l->sentinel->next = l->sentinel;
l->size = l->sentinel->value = 0;
}
int main(void) {
struct CircularList* deque = create();
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); //Works fine
circularListRemoveFront(deque);
circularListRemoveBack(deque);
circularListPrint(deque);
circularListReverse(deque);
circularListPrint(deque); //HANGS
//Debug
printf("\nEnd of print\n"); //This does NOT print, so function never exits
return 0;
}