Reversing a circular deque without a sentinel

Question

Hey Stackoverflow I'm working on my homework and I'm trying to reverse a circular-linked deque without a sentinel. Here are my data structures:

struct DLink {

 TYPE value;

 struct DLink * next;

 struct DLink * prev;
};

struct cirListDeque {

 int size;
 struct DLink *back;
};

Here's my approach to reversing the deque:

void reverseCirListDeque(struct cirListDeque* q) {

struct DLink* current;

struct DLink* temp;



temp = q->back->next;

q->back->next = q->back->prev;

q->back->prev = temp;



current = q->back->next;

while(current != q->back) {

    temp = current->next;

    current->next = current->prev;

    current->prev = temp;



    current = current->next;

}

}

However when I run it and put values 1, 2 and 3 on it (TYPE is just a alias for int in this case) and reverse it I get 2, 1, 3. Does anyone have any ideas as to what I may be doing wrong?

Thanks in advance.

Answer 1

current = q->back->next;

while(current != q->back->next)
{
    /* This code will never run, cause you guaranteed right before the while
     * that current == q->back->next .
     */
}

Update: What you need to do now, once you've reversed all the pointers (which seems to work now, judging by your results), is set your "back" pointer to back->prev.

Answer 2

Whenever working with abstract data types -- lists, queues, deques, etc., whenever pointers are involved, it really helps to draw out your data structure and its pointers into a diagram on paper. Label everything. Then code what you see. It really makes it a lot easier. I've not used deques since college, but make sure that you are not confusing prev, next, and back, as that could be the problem. Also be sure to check for null pointers before dereferencing them.

Hopefully this helps without directly giving away the answer. Your professor may appreciate that. ;-)

Answer 3

Not a direct answer to your problem, but back in school, I found the Data Display Debugger, to be an invaluable to for debugging problems like this.

Answer 4

The easiest and fastest way to do this would be to only change your interpretation of the direction of the queue.

The direction would be stored in the cirListDeque and your moving from node to node would be done with knowledge of the queue's current direction.