c++ - 双端队列 : is this a sound "add to front" implementation?

Question

我正在致力于将双端队列实现为双向链表(用于个人充实)，我想知道是否有人介意看一下我的 PushFront 函数，看看我是否在正确的轨道上。它本身应该是不言自明的(我希望)。

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->next = tail;
        temp->last = head;
    } else {
        temp->next = head->next;
        temp->last = head;
        head->next->last = temp;
        head->next = temp;
    }
}

我的想法是将我的头部和尾部哨兵保留在末端，这在我看来是避免边缘情况的最佳方式。

编辑:为避免混淆，我知道标准库中已为我完成了这项工作。我这样做是为了自学一些关于这门语言的知识。

编辑: 看来我明白了。现在一个有趣的问题:

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

Answer 1

关于哨兵，您只需要其中一个包含列表的next(第一个)和last 指针。如果在初始化时让指针指向哨兵值，则不需要考虑链表为空的特殊情况。

关于第二个问题，从列表中弹出，你只需要保留一个指向节点的指针并在从函数返回之前对其调用delete。

此外，你可能要考虑划分学习的问题:使用智能指针来管理你的资源并学习算法，然后学习内存管理(反之亦然)