Double-Ended Queue: is this a sound "add to front" implementation?

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 PushFront function to see if I'm on the right track. It should be self-explanatory enough on it's own (I hope).

void DeQueue::PushFront(void* item) {
    QueueItem* temp = new QueueItem();
    temp->data = item;
    // Insert the item between the head and the head's next item.
    if (Empty()) {
        head->next = temp;
        tail->last = temp;
        temp-&g开发者_开发百科t;next = tail;
        temp->last = head;
    } else {
        temp->next = head->next;
        temp->last = head;
        head->next->last = temp;
        head->next = temp;
    }
}

The idea is that my head and tail sentinels are kept at the ends, which seems to me to be the best way to avoid edge cases.

EDIT: To avoid any confusion, I know this has been done for me in the Standard Library. I'm doing this as a way to teach myself a few things about the language.

EDIT: It seems I've got the idea. Now an interesting problem:

void* DeQueue::PopFront() {
    if (Empty()) return NULL;  // should throw exception instead.
    void* temp = head->next->data;
    head->next->next->last = head;
    head->next = head->next->next;
    // now my node is gone... How do i free the memory
    // of something I've lost the reference to?
    return temp;
}

---

About the sentinels, you only need one of them that will contain the next (first) and last pointers of the list. If you make the pointers refer to the sentinel value during initialization, then you do not need to consider an special case when the list is empty.

About the second question, of pop-ing out of the list, you just need to keep a pointer to the node and call delete on it before returning from the function.

Additionally, you might want to consider dividing the problem of learning: use smart pointers to manage your resources and learn the algorithms, then learn memory management (or vice versa)

---

Answer to second edit: You can't. You'll have to retain a reference to it.

void* DeQueue::PopFront() {
    if (Empty()) 
        throw logic_error("stack is empty");

    QueueItem* deleteme = head->next; //get node
    void* temp = deleteme->data;

    deleteme->next->last = head;
    head->next = deleteme->next;

    delete deleteme; //delete node
    return temp;
}

---

Seems with this

if (Empty()) {
    head->next = temp;
    tail->last = temp;
    temp->next = tail;
    temp->last = head;

you presume that head and tail already point to something when the queue is empty?