双方向リスト実装編 step 1 (paizaランク B 相当)

N 個の要素からなる数列 A が与えられます。 A のすべての要素を順に双方向リストの末尾へ追加し、双方向リストのデータをすべて出力してください。

双方向リストとは、片方向リストと違い、次のノードだけではなく前のノードのインデックスも保持するリスト構造です。



双方向リストでは主に 4 つの変数・配列を用意する必要があります。



1. ノードの値を保持する配列( value )
2. 次のノードのインデックスを保持する配列( next_ptr )
3. 前のノードのインデックスを保持する配列( prev_ptr )
4. value に要素が入っていないもっとも小さいインデックス( empty_min_index )

また、双方向リストの末尾に要素 X を追加するには下記の 4 つの処理をおこなう必要があります。

1. 配列 value 変数の empty_min_idx 番目に要素を代入
2. 配列 next_ptr を変更
3. 配列 prev_ptr を変更
4. 変数 empty_min_idx を変更

双方向リストの要素を出力する際は配列 value をそのまま出力するのではなく、双方向リストの先頭から順に配列 next_ptr の値をたどって出力しましょう。