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