AOJ ALDS1 3_C（Doubly Linked List）を解く

Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の3_C問題をC++で解いてみました。

ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#3「基本データ構造」では、スタック、キュー、リストを学びます。

問題（3_C: Doubly Linked List）

問題はリンク先をご覧ください。

AOJ ALDS1 3_C問題: Doubly Linked List

双方向リストについて学びます。

リストについて

リストは、単方向でも双方向でも、途中の要素の追加と削除が効率よくできます。

基本的な考え方は、以下で定義する構造体nodeのnextとprevを操作して、追加と削除を実現します。自己参照する構造体になっていますが、CやC++のタグ（この場合はnode）は書いた直後から有効になるため、この書き方ができます（一般の変数は変数定義が終わるセミコロンの直後から有効になります）。

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

ただし、リストの実装は手間に感じたため、標準ライブラリの実装を使うことにします。

C++ プログラム例（ALDS1 3_C）

標準ライブラリ list を使う。

「プログラミング応用」（ITP2）の1_C問題で、標準ライブラリとして実装されている listを紹介しました。

リストは、配列やvectorコンテナと異なり、任意の場所にアクセスできません。初期イテレータを begin で取得して、たどっていきます（25、34行目）。問題の制約に「delete 命令の回数は 20 を超えない」とあり、この実装でも間に合います。

list コンテナのメソッド呼び出しは背景行を変更しておきます。より詳しい解説は上記の紹介記事をご覧ください。

#include <iostream>
#include <list>
using namespace std;

int main()
{
	int n;
	cin >> n;

	list<int> L;
	for (int i = 0; i < n; ++i) {
		string command;
		cin >> command;
		if (command == "insert") {
			int x;
			cin >> x;
			L.push_front(x);
		} else if (command == "deleteFirst") {
			L.pop_front();
		} else if (command == "deleteLast") {
			L.pop_back();
		} else if (command == "delete") {
			int x;
			cin >> x;
			for (list<int>::iterator it = L.begin(); it != L.end(); ++it) {
				if (*it == x) {
					L.erase(it);
					break;
				}
			}
		}
	}

	for (list<int>::iterator it = L.begin(); it != L.end(); ++it) {
		if (it != L.begin()) {
			cout << " ";
		}
		cout << *it;
	}
	cout << endl;

	return 0;
}

上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。

最後に

双方向リストについては、イメージはできていましたが手間に感じました。そのため標準ライブラリを使ってプログラムを書きました。

引き続き、ALDS1 の問題を紹介していきます。