Double-Ended Queue - Have I over-engineered it again?

Question

I'm working on an implementation of the Double-Ended Queue as a Doubly-Linked List (for personal enrichment), and I was wondering if anyone minded taking a look at my Constructor/Destructor and Empty functions to see if I'm on the right track. It should be self-explanatory enough on it's own (I hope).

 DeQueue::DeQueue() {
 // set up the sentinels
 head = new QueueItem();
 tail = new QueueItem();
 head->next = tail;
 tail->last = head;
 head->data = NULL;
 tail->data = NULL;
 tail->next = head->last = NULL;
 }
 DeQueue::~DeQueue() {
 QueueItem* current = head;
 QueueItem* next;
 current = current->next;
 for (;current != tail; current = current->next){
 delete current->last;
 }
 delete current;
 }
 bool DeQueue::Empty() {
 return tail->last == head;
 }

The idea is that the two head and tail sentinels will always remain at the ends, so the easiest way to check if it is empty is to determine if head points to tail or vice versa. Also, in my destructor, I start at the tail and delete everything from there back, sentinels included. Any suggestions?

EDIT: The destructor now moves forward one node, deletes what's behind it, then moves on. Sound like a better approach?

Answer 1

I would make it so that you only have one sentanal.

Then the list is empty when head and tail point at the same object.

DeQueue::DeQueue()
 // set up the sentinels
 : head(new QueueItem()) // prefer to use initialize list.
 , tail(head) // Make sure your declarations are in the correct order.
{
 head->next = head; // Circular linked list.
 head->last = head;
 head->data = NULL; // No data in the fake node.
}

Your delete loop does not actually move:

while(current->next != head)
{
 delete current->next; // your deleting the element
 // But not moving the the current item
 // So the loop will not exit.
}
DeQueue::~DeQueue()
{
 // Delete from the head.
 // Just slowly loop over the nodes deleting them as you go
 while(head != tail)
 {
 QueueItem* old = head;
 head = head->next;
 delete old;
 }
 // Delete the sentanal object created in the constructor.
 delete tail;
}
// Simplify empty.
bool DeQueue::Empty()
{
 return tail == head;
}

• wtfsven: Thanks, I didn't even realize that. I think I'll stick with the dual sentinels for now (I'm a bit brain-dead at the moment) but how about this for the destructor? (check original post)
• Loki Astari: @wtfsven: Your destructor now works. But you should still use the initializaer list in your constructor.
• dma: +1 for initializer lists. Also, the QueueItem should set data to NULL in its constructor, so you don't need to worry about doing that in DeQueue.
• Loki Astari: @dominic: That depends. QueueItem may be a plain old POD type so adding a constructor will change its layout and some gurantees. Also if QueueItem is fully contained as a private member class of DeQueue then being so strict on its construction may not be beneficial when DeQueue is going to manage all its interactions anyway.