c++ - 在循环双向链表的第一个节点之前/之后插入的算法是什么？

Question

我一直在使用尾指针构建一个双端队列，我只是想知道如果我使用循环指针，算法是否会相同。在我看来，我不必再跟踪尾指针了，维护和更新列表会更容易。然而，让我感到震惊的是，在第一个节点之前/之后的插入几乎是相同的，因为它是一个圆圈，它不会在第一个节点和之后的节点之间产生不同。我的理解正确吗？如果您可以在这里演示一个示例或显示这些函数的伪代码，那就太好了。

Answer 1

这是一些在头部之前/之后插入节点的代码。如果这就是你要找的。

struct node
{
    int val;
    struct node *prev;
    struct node *next;
};

bool insert_after_head(struct node *head, int val)
{
    if(head == NULL)
        return false;

    struct node *temp = new node;
    if(temp == NULL)
        return false;

    temp->val = val;

    // build new links
    temp->prev = head;
    temp->next = head->next;

    // rebuild old links(watch the order)   
    head->next->prev = temp;
    head->next = temp;

    return true;
}

bool insert_before_head(struct node *head, int val)
{
    if(head == NULL)
        return false;

    struct node *temp = new node;
    if(temp == NULL)
        return false;

    temp->val = val;

    // build new links
    temp->next = head;
    temp->prev = head->prev;

    // rebuild old links(watch the order)
    head->prev->next = temp;
    head->prev = temp;

    return true;
}