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