AOJ 双方向連結リストで苦しむ

AizuOnlineJudge(AOJ)でアルゴリズムに入りましたが、だんだんと難しくなり、進むペースが遅くなってきました。それでもWeb上のヒントだけで何とか説いてきましたが、ALDS1_3_C でつまずきました。

StackやQueueと同じように配列でプログラムを組んで実行すると、10個目でタイムアウトで引っかかってしまいます。配列に挿入するときや削除するときには1個ずつずらすことをやっていたので、時間がかかりすぎたようです。そのプログラムがこれ。

https://github.com/lingmujianshi/AizuOnlineJudge/blob/master/ALDS1/ALDS1_3_C/ALDS1_3_C_timeout.cpp

他の人が解いた回答を見ましたが全く理解できませんでした。双方向連結リスト？番兵？わからない言葉ばかりです。

そこでとうとうこの本を買ってしまいました。

本を見るとズバリと回答が書いてありました。双方向連結リストは自分の前の要素と次の要素へそれぞれのポインタを持つ構造体で番兵はリストの先頭を指す特別なノードで設置することで簡略化できるとのこと。

サンプルを丸写しし、投稿したら問題なく通りましたが、実を言うとコードを全然理解できませんでした。Visual Studio Codeのデバッグ機能を使ってみてみると、Node構造体の中身がぜんぜん表示されませんでした。Classを作ると確認する事ができました。サンプルはmallocを使っていたので、せっかくなのでnewを使って書き直しました。そのコードがこちら。

2つ目を追加したときの流れを書いてみたらやっと理解することができました。

    void insert(int key)
    {
        Node *x = new Node();
        x->key = key;
        // 番兵の直後に要素を追加
        x->next = nil->next;
        nil->next->prev = x;
        nil->next = x;
        x->prev = nil;
    }

https://github.com/lingmujianshi/AizuOnlineJudge/blob/master/ALDS1/ALDS1_3_C/main.cpp#L32-L41